/* Binary tree application
   Parse tree and Traverse */

 #include<stdio.h>
 #include<stdlib.h>

 typedef struct _node{ //tree의 node
  int key;
  struct _node *left;
  struct _node *right;
 }node;

 node *head, *tail; //머리와 꼬리

 #define MAX 100
 node *stack[MAX]; //이하 stack 구조 정의
 int top;
 void init_stack(void){
  top = -1;
 }

 node *push(node *t){
  if(top >= MAX -1){
   printf("\n  Stack Overflow.");
   return NULL;
  }
  stack[++top] = t;
  return t;
 }

 node *pop(void){
  if(top<0){
   printf("\n  Stack Underflow.");
   return NULL;
  }
  return stack[top--];
 }

 int is_stack_empty(void){
  return (top == -1);
 }

 node *queue[MAX]; //이하 원형 큐 구조의 정의
 int front, rear;

 void init_queue(void){
  front = rear = 0;
 }

 node *put(node *k){
  if((rear +1) % MAX == front){
   printf("\n  Queue Overflow.");
   return NULL;
  }
   queue[rear] = k;
  rear = ++rear % MAX;
  return k;
 }

 node *get(void){
  node *i;
  if(front == rear){
   printf("\n  Queue Underflow.");
   return NULL;
  }
  i = queue[front];
  front = ++front % MAX;
  return i;
 }

 int is_queue_empty(void){
  return (front == rear);
 }

 void init_tree(void){  //나무 구조의 초기화
  head = (node*)malloc(sizeof(node));
  tail = (node*)malloc(sizeof(node));
  head->left = tail;
  head->right = tail;
  tail->left = tail;
  tail->right = tail;
 }

 int is_operator(int k){ //k가 연산자이면 참
  return (k=='+' || k=='-'|| k=='*'|| k=='/');
 }

 node *make_parse_tree(char *p){  //후위 표기법에 의한 parse tree
  node *t;
  while(*p){
   while(*p == ' ') //공백문자 제거
    p++;
   t = (node*)malloc(sizeof(node));
   t->key = *p;
   t->left = tail;
   t->right = tail;
   if(is_operator(*p)){ //연산자이면 pop
    t->right = pop(); //오른쪽 자식
    t->left =pop();  //왼쪽 자식
   }
   push(t);
   p++;
  }
  return pop();
 }

 int is_legal(char *s){
  int f = 0;
  while(*s){
   while(*s == ' ') //공백을 제거
    s++;
   if(is_operator(*s))
    f--; //연산자이면 감소
   else
    f++; // 피연산자이면 증가
   if(f<1) break; //언더플로우
   s++;
  }
  return (f == 1); //피연산자수-연산자수=1 일 때
 }

 void visit(node *t){
  printf("%c ", t->key);
 }
 void preorder_traverse(node *t){ //뿌리 먼저
  if(t != tail){
   visit(t);  //root 방문
   preorder_traverse(t->left);//left subtree
   preorder_traverse(t->right); //right subtree
  }
 }

 void inorder_traverse(node *t){  //뿌리 중간에
  if(t != tail){
   inorder_traverse(t->left);//left subtree
   visit(t);  //root 방문
   inorder_traverse(t->right); //right subtree
  }
 }

 void postorder_traverse(node *t){ //뿌리 나중에
  if(t != tail){
   postorder_traverse(t->left);//left subtree
   postorder_traverse(t->right);//right subtree
   visit(t);  //root 방문
  }
 }

 void levelorder_traverse(node *t){   //층별로 타는 방식
  put(t);
  while(!is_queue_empty()){
   t = get();
   visit(t);
   if(t->left != tail)
    put(t->left);
   if(t->right != tail)
    put(t->right);
  }
 }

 void main(void){
  char post[256]; //후위 표기법 수식 저장
  init_stack(); //stack, queue, tree 초기화
  init_queue();
  init_tree();
  while(1){
   printf("\n\nInput Postfix expression : ");
   gets(post);
   if(*post == NULL){
    printf("\n Program ends...");
    exit(0);
   }
   if(!is_legal(post)){
    printf("\nExpression is not legal.");
    continue;
   }
   head->right = make_parse_tree(post);

   printf("\nPreorder traverse -> ");
   preorder_traverse(head->right);

   printf("\nInorder traverse -> ");
   inorder_traverse(head->right);

   printf("\nPostorder traverse -> ");
   postorder_traverse(head->right);

   printf("\nLevelorder traverse -> ");
   levelorder_traverse(head->right);
  }
 }

tree_traverse.cpp

* 트리(tree)
노드(버텍스)
링크(엣지)

노드의 종류
 - 루트노드 : 맨 상위의 노드
 - 부모노드 : 상위의 노드
 - 형제노드 : 좌, 우에 위치한 노드
 - 자식노드 : 하위에 있는 노드
 - 외부노드(리프노드, 터미널노드) : 자식이 없는 노드, 맨 말단의 노드
 - 내부노드 : 리프노드가 아닌것들

차수(degree) : 가지의 수 [자료구조 알고리즘 68P 이미지 참고]
 - A노드의 차수? 3
 - C노드의 차수? 2
 - tree전체의 노드의 차수(가장 큰 차수)?3

레벨 : root로 부터의 거리(먼저, root 노드 레벨을 0 또는 1로 설정)
       [자료구조 알고리즘 68P 이미지 참고]

N진 트리를 2진 트리로 바꾸기
 - 왼쪽 자식은 자식 노드 중 가장 왼쪽 자식
      - 오른쪽 자식은 형제 노드

* 이진트리 [자료구조 알고리즘 68P, 69P 설명참고]
사향이진트리 : 한쪽방향으로 치우쳐져 뻗어 나가는 트리
포화이진트리 : 완전히 다 채워져 있으나, 마지막 레벨의 노드는 채워져 있을 필요 없음
완전이진트리 : 완전히 다 채워진 트리

배열로 2진 트리를 구성

* 트리 순회방법 [자료구조 알고리즘 68P, 69P 설명참고]
모든것을 순회, 반복해서 순회하지 말것, 한번씩 순회할 것

[root기준, r: root, L: 왼쪽, R: 오른쪽]
전위순회 : rLR
중위순회 : LrR
후위순회 : LRr
레벨순회

전위순회(rLR)
A->B->D->H->I->E->C->F->G

중위순회(LrR)
H->D->I->B->E->A->F->C->G

후위순회(LRr)
H->I->D->E->B->F->G->C->A


전위순회(rLR)
/*A+BCD

중위순회(LrR)
A*B+C/D

후위순회(LRr)
ABC+*D