자체참조 구조체 스택을 활용한 트리의 순회

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#define MAX_STACK_SIZE 100

typedef struct TreeNodeType {

   char data;

   struct TreeNodeType *left, *right;

}TreeNode;

typedef TreeNode* element;

typedef struct {

   element stack[MAX_STACK_SIZE];

   int top;

}StackType;

TreeNode n1 = { 'D', NULL, NULL };

TreeNode n2 = { 'E', NULL, NULL };

TreeNode n3 = { 'B', &n1, &n2 };

TreeNode n4 = { 'F', NULL, NULL };

TreeNode n5 = { 'C', &n4, NULL };

TreeNode n6 = { 'A', &n3, &n5 };

TreeNode *root = &n6;

// 스택 초기화 함수 

void init(StackType *s)

{

   s->top = -1;

}

// 공백 상태 검출 함수 

int is_empty(StackType *s)

{

   return (s->top == -1);

}

// 포화 상태 검출 함수 

int is_full(StackType *s)

{

   return (s->top == (MAX_STACK_SIZE-1));

}

// 삽입 함수 

void push(StackType *s, element item)

{

   if(is_full(s)){

      fprintf(stderr, "스택 포화 에러\n");

      return;

   }

   else s->stack[++(s->top)] = item;

}

// 삭제 함수 

element pop(StackType *s)

{

   if(is_empty(s)){

      fprintf(stderr, "스택 공백 에러\n");

      exit(1);

   }

   else return s->stack[(s->top)--];

}

// 피크함수 

element peek(StackType *s)

{

   if(is_empty(s)){

      fprintf(stderr, "스택 공백 에러\n");

      exit(1);

   }

   else return s->stack[s->top];

}

void display_stack(StackType *s){

int i;

if(is_empty(s)){

fprintf(stderr, "스택 공백 에러\n");

exit(1);

}else {

for ( i = s->top; i >= 0; i--){

printf("%c ", s->stack[i]->data);

}

}

}

void inorder(TreeNode * root) //중위순회 

{

   StackType _mStack;

   TreeNode *current = root;

   init(&_mStack);

   while (current != NULL || !is_empty(&_mStack)) {

      if (current){

         push(&_mStack, current);

         current = current->left;

      }

      else {

         current = pop(&_mStack);

         printf("%c ", current->data);

         current = current->right;

      }

   }

   /*if (root) {

   inorder(root->left);

   printf("%d", root->data);

   inorder(root->right);

   }*/

}

void preorder(TreeNode * root) //전위순회 

{

   StackType _mStack;

   TreeNode *current = root;

   init(&_mStack);

   while (current != NULL || !is_empty(&_mStack)) {

      if (current){

         printf("%c ", current->data);

         push(&_mStack, current);

         current = current->left;

      }

      else {

         current = pop(&_mStack);

         current = current->right;

      }

   }

   /*if (root) {

   printf("%d", root->data);

   preorder(root->left);

   preorder(root->right);

   }*/

}

void postorder(TreeNode * root) //후위 순회 

{

   StackType _mStack;

   StackType _mTemp;

   TreeNode *current = root;

   init(&_mStack); init(&_mTemp);

   while (current != NULL || !is_empty(&_mStack)) {

      if (current){

         push(&_mStack, current); push(&_mTemp, current);

         current = current->right;

      }

      else {

         current = pop(&_mStack);

         current = current->left;

      }

   }

   display_stack(&_mTemp);

   /*if (root) {

   postorder(root->left);

   postorder(root->right);

   printf("%d", root->data);

   }*/

}

int main(void){

   inorder(root);

   printf("\n");

   preorder(root);

   printf("\n");

   postorder(root);

   system("pause");

   return 0;

}