메뉴 건너뛰기


Computer Science > Algorithm
제가 만든 프로그램 중 사용자 질의 분석기라는 게 있습니다.
이 분석기의 구현에서 이진트리(Binary Tree)를 사용하였는데 트리 대한 순회를 재귀(recusive)방식으로 하다보니 굉장히 긴 질의문에 대해서는 Stack Overflow와 같은 오류가 발생하게 되서리... 이를 반복(iterative)방식으로 바꿔야 겠다는 생각을 했습니다.
꽤 머리가 너무 복잡하더군요.
 
사실 Post Traversal 방식만 구현하면 제일은 끝나는 것이였는데... 한번 손을 댄김에 in, pre, post, level 모두 만들어 봤습니다.
 
혹시 위에서 이야기한 Tree의 순회 방식에 대해서 모르시는 분은 다음의 그림과 설명을 참조하세요.
 
binarytreetraversalflags.0.gif
 
preorder는 노드의 앞쪽(왼쪽)에 스위치가 있다고 생각하고...
inorder는 노드의 가운데(아래쪽)에 있다고 생각하고...
postorder는 노드의 뒤쪽(오른쪽)에 있다고 생각하고 다음과 같이 사선을 그려 만나는 접점을 순서대로 적으로 됩니다.
 
binarytreetraversalflags1.gif
         
            Preorder Traversal의 경우
 
 
binarytreetraversalflags2.gif
 
              Inorder Traversal의 경우
 
 
binarytreetraversalflags3_copy.gif
 
             Postorder Traversal의 경우
 
다시 본론으로 들어가서 다음은 소스 코드입니다.
 
#include <stdio.h>
#include <string.h>
#include <malloc.h>



typedef struct _Tree Tree;
struct _Tree {
  char data;
  Tree *left;
  Tree *right;
};



Tree *stack[100];
unsigned int pos=0;

Tree *pop(void)
{
  if(pos==0return NULL;
  pos--;
  return stack[pos];
}

void push(Tree *data)
{
  stack[pos]=data;
  pos++;
}

void stackinit(void)
{
  pos=0;
}

int isemptystack(void)
{
  return !(pos);
}




Tree *queue[100];
unsigned int qpos=0;

Tree *dequeue(void)
{
  unsigned int i;
  Tree *out;

  if(qpos==0return NULL;

  out=queue[0];

  for(i=0; i<qpos; i++) {
    queue[i]=queue[i+1];
  }
  qpos--;
  
  return out;
}

void enqueue(Tree *data)
{
  queue[qpos]=data;
  qpos++;
}

void queueinit(void)
{
  qpos=0;
}

int isemptyqueue(void)
{
  return !(qpos);
}



void inorder_r(Tree *root)
{
  if(root == NULL) return;

  inorder_r(root->left);
  printf("%c ", root->data);
  inorder_r(root->right);
}

void inorder(Tree *root)
{
  Tree *node=root;

  if(root==NULL) return;

  stackinit();

  while(node->left) {
    push(node);
    node = node->left;
  }

  do {
    printf("%c ", node->data);
    if (node->right) {
      node = node->right;
      while(node->left){
        push(node);
        node = node->left;
      }
    }else{
      node=pop();
    }
  }while (node);

  return;
}



void postorder_r(Tree *root)
{
  if(root==NULL) return;

  postorder_r(root->left);
  postorder_r(root->right);
  printf("%c ", root->data);
}

void postorder(Tree *root)
{
  Tree *store = root;
  Tree *node = root;

  if(root==NULL) return;

  stackinit();
  while(node || !isemptystack()) {
    if(node){
      push(node);
      node=node->left;
    } else {
      node=pop();
      while(node->right == NULL || node->right == store) {
        printf("%c ",node->data);
        store = node;
        if(isemptystack()) return;
        node=pop();
      }
      push(node);
      store=node=node->right; 
    }
  }

  return;
}


void preorder_r(Tree *root)
{
  if(root == NULL) return;

  printf("%c ", root->data);
  preorder_r(root->left);
  preorder_r(root->right);
}

void preorder(Tree *root)
{
  Tree *store = root;
  Tree *node = root;

  if(root==NULL) return;

  stackinit();
  while(node || !isemptystack()) {
    if(node){
      printf("%c ",node->data);
      push(node);
      node=node->left;
    } else {
      node=pop();
      while(node->right == NULL || node->right == store) {
        store = node;
        if(isemptystack()) return;
        node=pop();
      }
      push(node);
      store=node=node->right; 
    }
  }

  return;
}


void levelorder(Tree *root)
{
  Tree *node=root;

  if(root == NULL) return;

  queueinit();
  enqueue(root);
  while (!isemptyqueue()){
    node = dequeue();
    printf("%c ", node->data);
    if(node->left)
      enqueue(node->left);
    if(node->right)
      enqueue(node->right);
  }
}




int main(int argc, char *argv[])
{
  Tree *root, *node;

  Tree nodearr[7]={{0x00,},};

  
  root=nodearr+0;
  node=root;
  node->data='A';
  node->left = nodearr+1;
  node->left->data='B';
  node->left->left = nodearr+2;
  node->left->left->data='D';
  node->left->right = nodearr+3;
  node->left->right->data='E';
  node->right = nodearr+4;
  node->right->data='C';
  node->right->left = nodearr+5;
  node->right->left->data='F';
  node->right->right = nodearr+6;
  node->right->right->data='G';


  printf("**************************************************************\n");
  printf(" IN ORDER TRAVERSAL\n");
  printf("**************************************************************\n");
  inorder_r(root); printf("\n");
  inorder(root);
  printf("\n**************************************************************\n");
  printf(" POST ORDER TRAVERSAL\n");
  printf("**************************************************************\n");
  postorder_r(root); printf("\n");
  postorder(root);
  printf("\n**************************************************************\n");
  printf(" PRE ORDER TRAVERSAL\n");
  printf("**************************************************************\n");
  preorder_r(root); printf("\n");
  preorder(root);

  printf("\n**************************************************************\n");
  printf(" LEVEL ORDER TRAVERSAL\n");
  printf("**************************************************************\n");
  levelorder(root);

  printf("\n");

  return 0;
}
 
컴파일 후 실행하게 되면 다음과 같은 결과가 나타납니다.
 
**************************************************************
 IN ORDER TRAVERSAL
**************************************************************
D B E A F C G
D B E A F C G
**************************************************************
 POST ORDER TRAVERSAL
**************************************************************
D E B F G C A
D E B F G C A
**************************************************************
 PRE ORDER TRAVERSAL
**************************************************************
A B D E C F G
A B D E C F G
**************************************************************
 LEVEL ORDER TRAVERSAL
**************************************************************
A B C D E F G
 
예제로 사용한 트리는 위의 그림에서 나타난 트리 구조와 똑같이 만들었습니다.
 
위의 소스는 반복 이진 트리 순회에 포커스가 맞춰져서 만들어 졌습니다.
즉, Tree를 생성하거나 Stack이나 Queue를 위한 코딩은 전혀 실용적이지 않습니다.
그냥 논리적인 코딩이 맞는지 확인하기 위해 가장 단순하고 쉽게 만들었기 때문입니다.
기본 코드 구조는 모두 보이므로 위의 소스를 이해하셨다면 뭐 쓸만한 이진 Tree생성 소스나 Stack, Queue소스를 갖다 붙이면 되겠죠? ^^;
 
 
 
 
Creative Commons License
Creative Commons License이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
Copyright 조희창(Nicholas Jo). Some rights reserved. http://bbs.nicklib.com