[Data Structure] 이진 트리 : 수식 트리

수식 트리

- 산술 연산자(+, -, *, /), 피연산자로 구성

- 피연산자 = 단말노드

- 산술 연산자 = 비단말노드

- 각 루트노드들은 산술 연산자이기 때문에 루트보다 자식 노드(피연산자)들을 먼저 방문해야한다

• 그러므로 후위 순회를 사용

 

알고리즘

1. root에서부터 시작해서 해당 node가 NULL이면 그냥 return (종료) -- (1)
2. 해당 node의 left, right가 모두 NULL이면 해당 node는 단말노드 = 피연산자 ∴ return 해당 node의 data -- (2)

- (1), (2)에 해당이 안되면, 각 node의 left, right에서 (1), (2) 반복

 

 

Example)

• root(+) → evaluate(root->left) = '*' / evaluate(root->right) = '-'
• root->left(*) → op1 = 1 / op2 = 2
• root->right(-) → op1 = 7 / op2 = 8
• 1 * 2
• 7 - 8 
• (1*2) + (7-8)

//           *
//    +           -
// 8     39    85    2

// 수식 계산 : (8+39) * (85-2) = 47 * 83 = 3901

int evaluate(treenode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left == NULL && root->right == NULL) {
		// 단말노드 : root->data = 피연산자 return
		return root->data;
	}
	else  { // root = 비단말노드 ~> left, right를 순회해서 피연산자를 return해야 한다
		int op1 = evaluate(root->left); // left에 있는 피연산자
		int op2 = evaluate(root->right); // right에 있는 피연산자
		printf("--> %d %c %d 계산\n", op1, root->data, op2);
		switch (root->data) {
		case '+':
			return op1 + op2;
			break;
		case '-':
			return op1 - op2;
			break;
		case '*':
			return op1 * op2;
			break;
		case '/':
			return op1 / op2;
			break;

		}
	}
	return 0;
}

 

 

※ Example

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

typedef struct treenode {
	int data;
	struct treenode* left;
	struct treenode* right;
}treenode;

treenode n1 = { 8, NULL, NULL };
treenode n2 = { 39, NULL, NULL };
treenode n3 = { 85, NULL, NULL };
treenode n4 = { 2, NULL, NULL };
treenode n5 = { '+', &n1, &n2};
treenode n6 = { '-', &n3, &n4};
treenode n7 = { '*', &n5, &n6};
treenode* root = &n7; // 트리의 루트 노드(n7)를 가리키는 root 포인터

//           *
//    +           -
// 8     39    85    2

// 수식 계산 : (8+39) * (85-2) = 47 * 83 = 3901

int evaluate(treenode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left == NULL && root->right == NULL) {
		// 단말노드 : root->data = 피연산자 return
		return root->data;
	}
	else  { // root = 비단말노드 ~> left, right를 순회해서 피연산자를 return해야 한다
		int op1 = evaluate(root->left); // left에 있는 피연산자
		int op2 = evaluate(root->right); // right에 있는 피연산자
		printf("--> %d %c %d 계산\n", op1, root->data, op2);
		switch (root->data) {
		case '+':
			return op1 + op2;
			break;
		case '-':
			return op1 - op2;
			break;
		case '*':
			return op1 * op2;
			break;
		case '/':
			return op1 / op2;
			break;

		}
	}
	return 0;
}

int main(void) {
	printf("수식의 결과 값 : %d", evaluate(root));
}