자료구조 :: 트리(2) 이진트리 응용(연산,수식계산)

# 이진트리 응용

BinaryTreeApp.cpp

이진트리의 연산

(1) 노드의 갯수 :  이진트리안의 노드의 갯수를 세어 표시한다.

get_count(x)

if x ≠ NULL then
    return 1+get_count(x.left)+get_count(x.right);

(2) 단말 노드의 갯수 : 단말 노드의 갯수를 세어 표시한다. (단말노드 : 자식노드가 없는 노드)

get_leaf_count(x)

if T ≠ NULL then
    if T.left=NULL and T.right=NULL then 
        return 1;
    else
        return get_left(T.left)+get_leaf(T.right);

(3) 트리의 높이 : 트리의 높이를 구하여 표시한다.

get_height(T)

if T ≠ NULL then
    return 1+max(get_height(T.left),get_height(T.right));

이진 트리의 수식계산
이진 트리 순회는 수식 트리를 처리하는데 사용될 수 있으며, 피연산자들은 단말노드가 되며 연산자는 비단말
노드가 된다. 각 연산자에 대하여 왼쪽 서브트리는 왼쪽 피연산자가 되며 오른쪽 서브트리는 오른쪽 피연산자를
나타낸다. 여러가지 순회 방법 중에서 가장 적잡한 순회 방식은 자식 노드를 먼저 방문하는 후위 순회이다.

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

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

typedefstruct TreeNode 
{ 
int data; 
    TreeNode *left,*right; 
}TreeNode; 

int evaluate(TreeNode *root) // 자식노드를 먼저 방문하는 후위순회를 사용한다.
{ 
if(root == NULL) // 값이 없는 경우
return0; 

if(root->left == NULL && root->right == NULL) // root만 데이터가 있는 경우
return root->data ; 
else
    { 
int op1=evaluate(root->left);  // 왼쪽 서브트리 순회
int op2=evaluate(root->right); // 오른쪽 서브트리 순회

        printf("%2d %c %2d\n",op1,root->data,op2); 

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); 
        } 
    }     
return0; 
} 

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) return1; // 단말노드
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("결과 : %d\n",evaluate(&root)); 
    printf("노드의 갯수 : %d\n",NodeCount(&root)); 
    printf("단말 노드의 갯수 : %d\n",LeafCount(&root)); 
    printf("트리의 높이 : %d\n",GetHeight(&root)); 

return0; 
}