트리 - 수식 트리(후위 표기 수식)

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다.

 

// 해당 단원인 '트리'의 목차가 업데이트 될 예정입니다.

이전 글: 트리 - 레벨 순회알고리즘

 

수식트리 Expression Tree

흔히 우리가 알고 있는 수식을 트리로 표현한 것이다. 수식은 산술연산자와 피연산자로 구성된다. 

산술연산자는 트리의 비단말 노드가, 피연산자는 트리의 단말 노드가 되는데, 아래의 예를 보면 이해할 수 있다.

그렇다면, 이러한 수식 트리를 읽어들여서 연산할 수 있어야 한다.

이때 사용되는 것이 스택과 순회 알고리즘이다. 전위, 중위, 후위 순회 알고리즘 중 어느 것을 사용하는가에 따라 읽어들인 수식의 형태가 다른데, 아래의 표를 보면 무슨 말인지 이해가 될 것이다.

수식	a + b	a - b * c	(a<b) or (c>d)
전위순회 -> 전위표기수식	+ab	-a*bc	or < a b > c d
중위순회 -> 중위표기수식	a+b	a-b*c	a < b or c > d
후위순회 -> 후위표기수식	ab+	abc*-	a b < c > d or

3가지 순회 알고리즘을 통해 하나의 수식을 다양하게 읽을 수 있다. 이 중에서 컴퓨터가 연산을 수행하기에 가장 적합한 결과물은 후위 순회 알고리즘을 따른다. 후위 표기 수식은 연산의 우선순위를 이미 포함하고 있기 때문에, 컴퓨터는 후위표기수식을 순서대로 계산만 하면 되므로 고려해야 할 사항들이 줄어들어 연산이 빠르고 정확하다. 

 

수식트리를 후위표기 수식으로 변환하는 것은 어렵지 않다. 수식트리를 후위순회하여 읽어들인 방문 순서가 곧 후위표기 수식이다. 후위 순회 알고리즘은 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 노드순으로 방문한다. 이를 알고리즘으로 표현하면 다음과 같다.

// Pseudo Code
evaluate(root):
	if root == NULL
		return 0
	if root.left == NULL && root.right == NULL
    		return root.data
	else	
		x <- evaluate(root.left)
		y <- evaluate(root.right)
		op <- root.data
	return (x op y)

솔직히 위의 알고리즘만 봐서는 직관적으로 이해가 되지 않는다.

수식 '1*4 + (16+25)' 를 수식트리로 표현하고 후위순회 과정을 자세히 살펴보자.

 

위의 그림의 결과물이 45임을 알 수 있는데, 실제로 그러한지 c언어로 구현하여 살펴보자.

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

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

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* root = &n7;

// 수식 계산 함수
int eval(TreeNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return root->data;
	else {
		int op1 = eval(root->left);
		int op2 = eval(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()
{
	printf("수식의 값은 %d입니다.\n", eval(root));
	return 0;
}

결과가 동일함을 알 수 있다.

---

이와 같은 이진트리 순회는 수식 계산 이외에, 컴퓨터 디렉토리의 용량을 계산하는데도 사용된다.

예를 들어, 폴더 '나의 문서'에 음악폴더(50KB), 그림폴더(100KB)가 있다. 그림 폴더 내부에는 정지영상(200KB)과 동영상(500KB)가 있다고 한다면 '나의 문서' 용량을 어떻게 알아낼 수 있을까?

먼저 서브 디렉토리의 용량을 모두 계산한 다음에 루트 디렉토리의 용량을 계산해야 하므로, 이 경우에도 후위순회가 적합하다. c언어로 구현해보자. 

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

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

int calc_dir_size(TreeNode* root)
{
	int left_size, right_size;
	if (root == NULL)
		return 0;
	left_size = calc_dir_size(root->left);
	right_size = calc_dir_size(root->right);
	return (root->data + left_size + right_size);
}
int main() 
{
	TreeNode n5 = { 500, NULL, NULL };
	TreeNode n4 = { 200, NULL, NULL };
	TreeNode n3 = { 100, &n4, &n5 };
	TreeNode n2 = { 50, NULL, NULL };
	TreeNode n1 = { 0, &n2, &n3 };
	TreeNode* root = &n1;
	printf("디렉토리의 크기: %d \n", calc_dir_size(root));
	return 0;
}

실제로도, 50 + 100 + 200 + 500 = 850 임을 결과물로 알 수 있다.