//수식트리
//발전 가능성 : 지금은 각 노드를 사용자가 직접 입력하도록 해놨다. -> 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;
}
'Programming > C, C++' 카테고리의 다른 글
트리생성 (0) | 2013.05.21 |
---|---|
Doublelinkedlist (0) | 2012.12.26 |
Linkedlist (0) | 2012.12.26 |
Circular Queue (0) | 2012.12.21 |
Stack (0) | 2012.12.20 |
댓글