제5장 트리 - 리스트 표현방법

소개글

2. [프로그래밍 프로젝트] 트리는 리스트 표현방법을 이용하여 표현하고 노드 구조는 다음과 같다고 가정한다.

tag = TRUE/FALSE | dlink / data | link

tag는 노드가 링크노드인 경우 TRUE의 값을 가지며, 노드가 데이터 노드인 경우는 FALSE의 값을 갖는 필드이다. 그림 5.53 은 예제 트리와 위의 노드 구조를 가지는 표현을 보이고 있다. 이 트리는 리스트로 다음과 같다.

A ( B ( E ( H , I ( J , K ) ), F ) , C ( G ) , D )

그림 5.53(b)와 같이 트리가 표현된다고 가정할 때 다음 함수를 작성하라.

(a) 리스트를 입력으로 받아 리스트에 해당하는 트리를 생성한다.
(b) 트리를 복사한다.
(c) 두 트리의 동일성을 검사한다.
(d) 트리를 삭제한다.
(e) 리스트 표현으로 트리를 출력한다.

1) 거의 line by line 으로 상세한 주석을 달아놨습니다.
2) e)의 출력은 level-order traversal로 출력 했습니다.

컴파일 실행환경

vc++ 6.0

본문내용

#include <stdio.h>
#include <string.h>
#include <ctype.h> // isspace를 쓰기 위해서.
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

#define MAX_STACK_SIZE 128 // 최대 스택 사이즈
#define MAX_STRING 256 // 최대 문자열 길이
#define MAX_QUEUE_SIZE 128 // 최대 큐 사이즈

#define DLINK 1 // dlink 가 링크 일 경우
#define DATA 0 // dlink 가 데이터 일 경우

// data type , 스택이나 큐에 집어 넣는 데이터를 구분.
enum _data_type{ TYPE_CHAR , TYPE_PNODE };

// 사용자 정의 변수 및 구조체
typedef int bool;
typedef struct _NODE *PNODE; // 노드 포인터
typedef struct _NODE // 노드 구조체
{
// 해당 노드가 링크노드 일 경우 true , 데이터노드 일경우 false
int tag;
PNODE dlink; // 데이터 링크
PNODE link; // 링크
} NODE ;
//////////////////////////////////////////////////////////////////////////
// global Variable

char g_str_tree[MAX_STRING] = {0}; // 트리의 표현을 저장하는 전역 문자열

/************************************************************************
* Function Prototype Declare
*************************************************************************/
// Main Function
void printMenu ( void ); // 메뉴를 출력.
bool Menu_Create ( PNODE* pRoot);// 트리 생성
PNODE Menu_Copy ( PNODE pRoot); // 트리를 카피.
void Menu_Delete ( PNODE pRoot); // 트리를 삭제.
void Menu_Print ( PNODE pRoot); // 트리를 출력.

// 복제된 트리와 비교
void Menu_IsSame ( PNODE pRoot , PNODE pCopyRoot);

압축파일 내 파일목록

Problem_02_List_Tree/
Problem_02_List_Tree/Problem_02_List_Tree.dsp
Problem_02_List_Tree/Problem_02_List_Tree.dsw
Problem_02_List_Tree/Problem_02_List_Tree.ncb
Problem_02_List_Tree/Problem_02_List_Tree.opt
Problem_02_List_Tree/Problem_02_List_Tree.positions
Problem_02_List_Tree/tree.c

참고 자료

없음