[자료구조] 이진 수식 트리 생성과 계산

이진 수식 트리 생성과 계산

수식 트리란 산술 식을 트리 형태로 표현한 트리입니다. 수식 트리에서 연산자들은 비단말 노드에 해당되며 피연산자들은 단말 노드에 해당됩니다. 

 

전위, 중위, 후위 수식 표기법은 아래 포스팅에 설명되어있으니 참고하시기 바랍니다.

[자료구조] 스택을 응용, 활용한 프로그램

수식 트리를 계산하는 방법은 여러가지 순회가 있으나 이 글에서는 후위순회를 사용합니다. 서브트리의 값을 순환호출하여 계산하고 연산자(비단말 노드)를 방문할 때 피연산자(양쪽 서브트리의 값)을 저장된 연산자를 이용하여 계산합니다.

 

알고리즘 ( evaluate 재귀 호출 수는 노드 수와 동일 )

#include <stdio.h>

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
} TreeNode;
/*
       +
   *       +
  1 4    16 25
*/
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, NULL, NULL };
TreeNode n3 = { '*', &n1, &n2 };
TreeNode n4 = { 16, NULL, NULL };
TreeNode n5 = { 25, NULL, NULL };
TreeNode n6 = { '+', &n4, &n5 };
TreeNode n7 = { '+', &n3, &n6 };
TreeNode* exp = &n7;

// 수식 계산 함수
int evaluate(TreeNode* root) {
	if (root == NULL) return 0;
	if (root->left == NULL && root->right == NULL) // 단말노드라면
		return root->data;
	else {
		int op1 = evaluate(root->left);
		int op2 = evaluate(root->right);
		printf("%d %c %d을 계산합니다.\n", op1, root->data, op2);
		switch (root->data) {
		case '+':	return op1 + op2;
		case '-':	return op1 - op2;
		case '*':	return op1 * op2;
		case '/':	return op1 / op2;
		}
	}
	return 0;
}

int main(void) {
	printf("수식의 값은 %d입니다. \n", evaluate(exp));
	return 0;
}
/*
1 * 4을 계산합니다.
16 + 25을 계산합니다.
4 + 41을 계산합니다.
수식의 값은 45입니다.
*/