C, 이진트리 구현 소스

<출처: 마이크로소프트웨어>

 

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

 

int parser( char *p, char *argv[], int maxargc )
{
 int argc = 0;

 while ( *p )
 {
  while ( *p && isspace( *p ) ) p++;

  if ( ! *p ) return( argc );
  argv[argc++] = p++;

  while ( *p && !isspace( *p ) ) p++;
  if( *p ) *p++ = 0;

  if ( argc >= maxargc ) return( argc );
 }
 return ( argc );
}

 

typedef struct b_node_tag {
 struct b_node_tag * leftchild; /* 좌 하위 트리 */
 char data; /* 노드의 데이터 */
 struct b_node_tag * rightchild; /* 우 하위 트리 */
} b_node;

int print_data(char data)
{
 printf("%c ", data);
 return 1;
}

 

/* 전위 순회법 */
int preorder(b_node *tree)
{
 if(tree == NULL)
  return 0;
 print_data(tree->data); /* 먼저 자신을 방문한다. */
 preorder(tree->leftchild); /* 좌 하위 트리를 전위 순회법으로 순회한다. */
 preorder(tree->rightchild); /* 우 하위 트리를 전위 순회법으로 순회한다. */
 return 1;
}

int inorder(b_node *tree)
{
 if(tree == NULL)
  return 0;
 inorder(tree->leftchild); /* 먼저 좌 하위 트리를 중위 순회법으로 순회한다. */
 print_data(tree->data); /* 자신을 방문한다 */
 inorder(tree->rightchild); /* 우 하위 트리를 중위 순회법으로 순회한다. */
 return 1;
}

int postorder(b_node *tree)
{
 if(tree == NULL)
  return 0;
 postorder(tree->leftchild); /* 먼저 좌 하위 트리를 후위 순회법으로 방문한다. */
 postorder(tree->rightchild); /* 우 하위 트리도 후위 순회법으로 방문한다. */
 print_data(tree->data); /* 그런 다음 자신을 방문한다 */
 return 1;
}

 

b_node *make_node(char data)
{
 b_node *node;
 node = (b_node *)malloc(sizeof(b_node));
 node->data = data; /* 데이터를 추가시킨다. */
 node->leftchild = NULL; /* 좌 하위 트리는 없다. */
 node->rightchild = NULL; /* 우 하위 트리도 아직 없다. */
 return node;
}

 

/* 트리 전체를 생성한다. */
/* 이 부분을 수정하여 자신이 원하는 모습으로 만들어서 시험해 볼 수도 있다. */
b_node *make_tree()
{
 b_node *tree;

 tree = make_node( 'A');
 tree->leftchild = make_node('B');
 tree->rightchild = make_node('C');
 tree->leftchild->leftchild = make_node('D');
 tree->leftchild->rightchild = make_node('E');
 tree->rightchild->leftchild = make_node('F');
 tree->rightchild->rightchild = make_node('G');
 return tree;
}

 

/* 프로그램을 수행하고 난 다음 모든 메모리를 반환한다. */
/* 이 과정도 재귀 호출법을 이용하여 구현한다. */
/* malloc을 이용하여 메모리를 동적으로 할당했을 경우에는 항상 그 메모리가
제대로 반환 되는지를 검사해야 한다. 매우 중요한 일이다. */
int free_all_tree(b_node *tree)
{
 if(tree == NULL)
  return 0;
 free_all_tree(tree->leftchild); /* 좌 하위 트리를 반환한다. */
 free_all_tree(tree->rightchild); /* 우 하위 트리를 반환한다. */
 free(tree); /* 그리고 자신도 반환한다. */
 return 1;
}

 

/* 이진 트리를 복사하는 함수입니다. */
b_node *copy(b_node *tree)
{
 b_node *temp;
 if(tree == NULL)
  return NULL;
 
 temp = (b_node *)malloc(sizeof(b_node));
 temp->leftchild = copy(tree->leftchild); /* 좌 하위 트리를 복사하고 */
 temp->rightchild = copy(tree->rightchild); /* 우 하위 트리를 복사합니다. */
 temp->data = tree->data; /* 그리고 자신을 복사합니다. */
 return temp;
}

/* 두 개의 이진 트리를 비교하는 함수입니다. */
int equal(b_node *src, b_node *dest)
{
 if((src == NULL) && (dest == NULL))
  return 1; /* 둘 다 NULL 이면 두 이진 트리는 같습니다. */
 else if((src != NULL) && (dest != NULL))
 {
  if(equal(src->leftchild, dest->leftchild))
  {
   if(equal(src->rightchild, dest->rightchild))
   {
    if(src->data == dest->data)
     return 1;
   }
  }
 }
 return 0;
}

 

b_node *tree = NULL;

 

/* 주어진 데이터를 바탕으로 노드를 찾는 함수입니다. */
b_node *find_node(b_node *start, char data)
{
 b_node *temp;

 if(start == NULL)
  return NULL;
 if(start->data == data) /* 현재 노드가 찾는 노드인지 검사 */
  return start;
 temp = find_node(start->leftchild, data); /* 좌 하위 트리 전체 검색 */
 if(temp != NULL)
  return temp;
 else
  return find_node(start->rightchild, data); /* 우 하위 트리 전체 검색 */

}

 

b_node *find_child_prev(b_node *start, char child)
{

 return NULL;
}

 

int addnode(char child, char parent)
{
 b_node *start, *ch, *temp;

 if(parent == -1)
  start = tree;
 else
 { /* 부 노드를 찾아 냅니다. */
  start = find_node(tree, parent);
  if(start == NULL)
  {
   printf("Cannot Add\n");
   return 0;
  }
 }
 ch = make_node(child);
 if(start == NULL)
 { /* 아무 노드도 존재하지 않는 경우 */
  tree = ch;
  return 1;
 }

 /* 새로운 노드를 부 노드의 좌 자 노드로 한다. */
 temp = start->leftchild;
 ch->rightchild = temp;
 start->leftchild = ch;
 return 1;
}

 

int prt_child(b_node *p)
{
 b_node *temp = p->leftchild;

 while(temp)
 {
  print_data(temp->data);
  temp = temp->rightchild;
 }
 return 1;
}

 

int child(char parent)
{
 b_node *start;

 start = find_node(tree, parent);
 if(start == NULL)
 {
  printf("Cannot find\n");
  return 0;
 }

 printf("노드 %c 의 자 노드 : ", parent);
 prt_child(start);
 return 1;
}

int trv()
{
 printf("전위 순회법 : ");
 preorder(tree);
 printf("\n");
 printf("중위 순회법 : ");
 inorder(tree);
 printf("\n");
 printf("후위 순회법 : ");
 postorder(tree);
 printf("\n");

 return 1;
}

 

int trv_ex()
{
 b_node *tree = make_tree();
 b_node *tree1 = copy(tree);

 printf("전위 순회법\n");
 preorder(tree);
 printf("\n");
 printf("중위 순회법\n");
 inorder(tree);
 printf("\n");
 printf("후위 순회법\n");
 postorder(tree);
 printf("\n");

 if(equal(tree, tree1))
  printf("트리가 동일합니다\n");
 else
  printf("프로그램 에러입니다.\n");
 free_all_tree(tree);
 free_all_tree(tree1);
 return 1;
}

 

b_node *swap_tree(b_node *t)
{
 /* 이 부분을 채워 보시기 바랍니다. */
 printf("아직 구현 중 ... \n");
 return t;
}

 

int swap()
{
 tree = swap_tree(tree);
 printf("swap complete\n");
 return 1;
}

int quit()
{
 free_all_tree(tree);
 return 1;
}

void main()
{
 char buf[128];
 char *argv[10];
 int  argc;
 char *prompt = "\nBTREE> ";

 while(1)
 {
  printf(prompt);
  gets(buf);
  argc = parser( buf, argv, 10 );

  if(argc == 0)
   continue;
 

  if(!stricmp(argv[0], "add"))
  {
   if(argc > 2)
    addnode(argv[1][0], argv[2][0]);
   else if(argc == 2)
    addnode(argv[1][0], -1);
  }
  else if(!stricmp(argv[0], "child"))
  {
   if(argc == 2)
    child(argv[1][0]);
  }
  else if(!stricmp(argv[0], "trv"))
  {
   trv();
  }
  else if(!stricmp(argv[0], "trv_ex"))
  {
   trv_ex();
  }
  else if(!stricmp(argv[0], "swap"))
  {
   swap();
  }
  else if(!stricmp(argv[0], "quit"))
  {
   quit();
   break;
  }
  else if(!stricmp(argv[0], "help"))
  {
   printf("showav : show the available list\n");
  }
  else
  {
   printf("Invalid Command : %s\n", argv[0]);
  }
 }
}

<The End>