수식트리

//수식트리

//발전 가능성 : 지금은 각 노드를 사용자가 직접 입력하도록 해놨다. -> string을 통해 변경해보기

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

#define max(a,b)  (((a) > (b)) ? (a) : (b))

typedef struct TreeNode
{
 int data;
 TreeNode *left,*right;
}TreeNode;

int preorder(TreeNode *root)
{
 int op1, op2;
 if(root == NULL) // 값이 없는 경우
  return 0;
 

 

 if(root->left == NULL && root->right == NULL) {// root만 데이터가 있는 경우
  printf("%d ", root->data );
  return root->data ;
 }else{
  printf("%c ", root->data );
  int op1=preorder(root->left);  // 왼쪽 서브트리 순회
  int op2=preorder(root->right); // 오른쪽 서브트리 순회
  switch(root->data)
  {
   case '+' :
    return op1+op2;
   case '-' :
    return ((op1>op2) ? op1-op2 : op2-op1);
   case '*' :
    return op1*op2;
   case '/' :
    return ((op1>op2) ? op1/op2 : op2/op1);
  }
 }

 printf("\n");
 return 0;
}

int inorder(TreeNode *root)
{
 int op1, op2;
 if(root == NULL) // 값이 없는 경우
  return 0;

 

 
 if(root->left == NULL && root->right == NULL) {// root만 데이터가 있는 경우
  printf("%d ", root->data );
  return root->data ;
 }else{
  op1=inorder(root->left);  // 왼쪽 서브트리 순회
  printf("%c " ,root->data);
  op2=inorder(root->right); // 오른쪽 서브트리 순회

  switch(root->data)
  {
   case '+' :
    return op1+op2;
   case '-' :
    return ((op1>op2) ? op1-op2 : op2-op1);
   case '*' :
    return op1*op2;
   case '/' :
    return ((op1>op2) ? op1/op2 : op2/op1);
  }
 } 
 printf("\n");
 return 0;
}

int postorder(TreeNode *root)
{
 if(root == NULL) // 값이 없는 경우
  return 0;
 

 if(root->left == NULL && root->right == NULL) { // root만 데이터가 있는 경우
  printf("%d ", root->data );
  return root->data ;

 }else{
  int op1=postorder(root->left);  // 왼쪽 서브트리 순회
  int op2=postorder(root->right); // 오른쪽 서브트리 순회
  printf("%c " ,root->data);
  
  switch(root->data)
  {
   case '+' :
    return op1+op2;
   case '-' :
    return ((op1>op2) ? op1-op2 : op2-op1);
   case '*' :
    return op1*op2;
   case '/' :
    return ((op1>op2) ? op1/op2 : op2/op1);
  }
 } 
 printf("\n");
 return 0;
}

int NodeCount(TreeNode *node) // 노드의 갯수
{
 int count=0;
 if(node != NULL)
  count = 1+NodeCount(node->left)+NodeCount(node->right);
  // 루트노드 + 왼쪽 서브트리 노드 + 오른쪽 서브트리 노드
 return count;
}

int LeafCount(TreeNode *node) // 단말 노드의 갯수
{
 int count=0;
 if(node != NULL)
 {
  if(node->left == NULL && node->right == NULL) return 1; // 단말노드
  else count = LeafCount(node->left) + LeafCount(node->right); // 왼쪽,오른쪽 순회
 }
 return count;
}

int GetHeight(TreeNode *node)
{
 int count=0;
 if(node != NULL)
  count=1+max(GetHeight(node->left),GetHeight(node->right));
  // 루트 + 왼쪽 서브트리 높이와 오른쪽 서브트리의 높이중 큰 값
 return count;
}

int main()
{
 TreeNode n6={25,NULL,NULL};
 TreeNode n5={16,NULL,NULL};
 TreeNode n4={4,NULL,NULL};
 TreeNode n3={1,NULL,NULL};
 TreeNode n2={'+',&n5,&n6};
 TreeNode n1={'*',&n3,&n4};
 TreeNode root={'+',&n1,&n2};

 printf("preorder 결과 : %d\n",preorder(&root));
 printf("inorder 결과 : %d\n",inorder(&root));
 printf("postorder 결과 : %d\n",postorder(&root));

 printf("노드의 갯수 : %d\n",NodeCount(&root));
 printf("단말 노드의 갯수 : %d\n",LeafCount(&root));
 printf("트리의 높이 : %d\n",GetHeight(&root));

 return 0;
}