이진 트리의 순회(Traversal)
앞서 이진 트리의 순회가 필요한 이유를 설명했으니, 바로 이어서 트리의 순회 방법을 설명하겠다. 참고로 순호의 방법 또한 재귀적이다.
순회의 세가지 방법
이진 트리를 대상으로 하는 대표적인 순회의 세 가지 방법은 다음과 같다.
전위 순회(Preorder Traversal) : 루트 노드를 먼저
중위 순회(Inorder Traversal) : 루트 노드를 중간에
후위 순회(Postorder Traversal) : 루트 노드를 마지막에
이렇듯 이진 트리를 순회하는 대표적인 방법은 다음 내용을 기준으로 세 가지로 나뉜다.
"루트 노드를 언제 방문하느냐"
다음과 같은 순서 및 방향으로 순회할 경우 , 루트 노드는 중간에 방문이 이뤄지기 때문에 이러한 방식의 순회를 가리켜 중위 순회라 한다.
유사하게 다음과 같은 순서 및 방향으로 순회할 경우, 루트 노드는 마짐가에 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 후위 순회라 한다.
끝으로 루트 노드를 먼저 방문하는 방식의 순회를 가리켜 전위 순회라 한다.
이렇듯 순회의 방법은 간단하다. 루트 노드와 이를 부모로 하는 두 자식 노드를 놓고, 한쪽 방향으로 순서대로 방문을 하면 된다.
그림을 통해 보였듯이 높이가 1인 이진 트리의 순회는 어렵지 않다. 그런데 높이가 2 이상이 되면 조금 당황스럽다. 하지만 이진 트리는 그 구조가 재귀적이다. 따라서 우리가 지금 이야기 한 세 가지 순회의 방법을 재귀적으로 구현만 하면 문제는 해결이 된다.
순회의 재귀적 표현
"세 가지 순회의 방법을 재귀적으로 구현만 하면 문제는 해결이 된다."
이제 중위 순회를 진행하는 함수를 정의해 볼텐데 , 이를 위해서 다음 그림을 관찰하자. 이 그림에서 보이는 이진 트리는 루트 노드를 기준으로 왼쪽가 오른쪽에 서브 트리가 존재하는 가장 일반적인 모델이다.
위 그림의 이진 트리를 대상으로 중위 순회를 할 경우 순회의 순서는 다음과 같다.
1단계 : 왼쪽 서브 트리의 순회
2단계 : 루트 노드의 방문
3단계 : 오른쪽 서브 트리의 순회
여기서 문제는 1단계와 3단게이다. 어떠한 방법으로 서브 트리를 순회해야 하는가? 서브 트리라고 해서 순회의 방법이 달라지는 것은 아니다. 즉 이들을 대상으로도 중위 순회를 진행하면 된다. 따라서 이진 트리 전체를 순회하는 함수는 , 완전하지는 않지만 일단 다음과 같이 정의할 수 있다.
void InorderTraverse(BTreeNode *bt) //이진 트리 전체를 중위 순회 하는 함수
{
InorderTraverse(bt->left); //1단계 왼쪽 서브 트리의 순회
printf("%d \n", bt->data); //2단계 루트 노드의 방문
InorderTraverse(bt->right); //3단계 오른쪽 서브 트리의 순회
}
위의 함수에서는 노드의 데이터를 정수라고 가정하였다. 그런데 이 함수에서도 두 가지 의문이 있다.
1. 재귀의 탈출 조건이 정의되어 있지 않다.
2. 노드의 방문이 그저 데이터의 출력이다.
노드에 저장된 데이터의 출력으로 , 노드의 방문이 이뤄진 것으로 가정한 이유는, 순회의 방법에 초점을 두기 위한것이니 우선은 재귀의 탈출 조건 구성에 집중을 하자. 그럼 이와 관련해서 다음 상황을 보자.
만약 왼쪽 서브트리의 레벨1 의 노드에 오른쪽 노드가 존재하지 않다고 가정을 하자.
위 상황에서 재귀의 탈출 조건을 발견할 수 있다. 오른쪽 서브 트리가 공집합(NULL)이므로 함수에 NULL이 전달되기 떄문이다. 따라서 함수는 다음과 같이 정의되어야 한다.
void InorderTraverse(BTreeNode *bt)
{
if(bt==NULL) //bt가 NULL이면 재귀 탈출
return ;
InorderTraverse(bt->left); //1단계 왼쪽 서브 트리의 순회
printf("%d \n", bt->data); //2단계 루트 노드의 방문
InorderTraverse(bt->right); //3단계 오른쪽 서브 트리의 순회
}
이로써 중위 순회 함수를 완성하였으니, 앞서 구현한 에제 BinaryTreeMain.c에 이 함수를 추가하여 그 결과를 확인하자.
//BinaryTreeMain.c
#include <stdio.h>
#include "BinaryTree.h"
void InorderTraverse(BTreeNode *bt)
{
if(bt==NULL) //bt가 NULL이면 재귀 탈출
return ;
InorderTraverse(bt->left); //1단계 왼쪽 서브 트리의 순회
printf("%d \n", bt->data); //2단계 루트 노드의 방문
InorderTraverse(bt->right); //3단계 오른쪽 서브 트리의 순회
}
int main()
{
BTreeNode * bt1 = MakeBTreeNode(); //노드 bt1생성
BTreeNode * bt2 = MakeBTreeNode(); //노드 bt2생성
BTreeNode * bt3 = MakeBTreeNode(); //노드 bt3생성
BTreeNode * bt4 = MakeBTreeNode(); //노드 bt4생성
SetData(bt1, 1); //bt1에 1 저장
SetData(bt2, 2); //bt2에 2 저장
SetData(bt3, 3); //bt3에 3 저장
SetData(bt4, 4); //bt4에 4 저장
MakeLeftSubTree(bt1, bt2); //bt2를 bt1의 왼쪽 자식 노드로
MakeRightSubTree(bt1, bt3); //bt3을 bt1의 오른쪽 자식 노드로
MakeLeftSubTree(bt2, bt4); //bt4를 bt2의 왼쪽 자식 노드로
InorderTraverse(bt1);
return 0;
}
===============실행 결과==========================
4
2
1
3
위와 같은 순서로 출력이 이뤄지면 성공이다. 이는 중위 순회의 노드 방문 순서와 일치하기 때문이다. 이로써 중위 순회 하나를 끝냈지만, 전위 순회와 후위 순회도 끝낸 것이단 다름 없다. 노드의 방문 순서가 이들의 유일한 차이점 이기 때문이다. 그럼 이이서 전위 순회와 후위 순회를 진행하는 함수를 소개하겠다.
void PreorderTraverse(BTreeNode * bt) //전위 순회 함수
{
if(bt ==NULL)
return;
printf("%d \n", bt->data); //전위 순회이므로 루트 노드 먼저 방문
PreorderTraverse(bt->left);
PreorderTraverse(bt->right);
}
void PostorderTraverse(BTreeNode *bt) //후위 순회 함수
{
if(bt==NULL)
return;
PostorderTraverse(bt->left);
PostorderTraverse(bt->right);
printf("%d \n ", bt->data); //후위 순회 이므로 루트 노드 나중에 방문
}
위에서 보이듯이 중위, 전위, 후위 순회 함수의 유일한 차이점은 루트 노드를 방문하는 문장이 삽입된 위치이다.
노드의 방문목적은 데이터의 출력이 전부가 아니다. 방문의 목적은 상황에 따라 달리진다. 따라서 방문했을 때 할 일을 결정할 수 있도록, 앞서 정의한 세 개의 순회 함수를 변경하고자 한다.
typedef void (*VisitFuncPtr)(BTData data);
void InorderTraverse(BTreeNode * bt, VisitFuncPrt action)
{
if(bt== NULL);
return;
InorderTraverse(bt->left, action);
action(bt->data); //노드의 방문
InorderTraverse(bt->right, action);
}
함수의 주소 값을 매개변수 action을 통해서 전달받도록 변경하였다. 그리고 이 함수를 기반으로 노드의 방문은 다음과 같이 처리되도록 변경하였다.
action(bt->data); //노드의 방문
즉 매개변수 action에 전달되는 함수의 내용에 따라서 노드의 방문 결과가 결정되는 것이다. 그럼 이와 관련해서 완성된 예제를 보이겠다.
//BinaryTree2.h
#ifndef __BINARY_TREE2_H__
#define __BINARY_TREE2_H__
typedef int BTData;
typedef struct _bTreeNode
{
BTData data;
struct _bTreeNode *left;
strcut _bTreeNode *right;
}BTreeNode;
BTreeNode *MakeBTreeNode(void);
BTData GetData(BTreeNOde *bt);
void SetData(BTreeNode * bt, BTData data);
BTreeNode * GetLeftSubTree(BTreeNode *bt);
BTreeNOde * GetRightSubTree(BTreeNode * bt);
void MakeLeftSubTree(BTreeNode * main, BTreeNode *sub);
void MakeRightSubTree(BTreeNOde *main, BTreeNode *sub);
typedef void (*VisitFuncPtr)(BTData data);
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);
#endif이는 앞서 정의한 헤더파일 BinaryTree.h 에 전위, 중위, 후위 순회 관련 함수의 선언을 추가한 것이다. 따라서 이 둘의 구분을 목적으로 파일에 별도의 이름을 부여하였다. 마찬가지로 이어서 소개하는 소스 파일도 BinaryTree.c 에 순회 관련 함수의 정의를 추가한 것이다. 따라서 변경되지 않은 부분에 대해서는 그 내용을 생략하였다.
//BinaryTree2.c
#include <stdio.h>
#include <stdlib.h>
BTreeNode * MakeBTreeNode(void) { 생략 }
BTData GetData(BTreeNode * bt) { 생략 }
void SetData(BTreeNOde * bt, BTData data) { 생략 }
BTreeNode * GetLeftSubTree(BTreeNode * bt) { 생략}
BTreeNode * GetRightSubTree(BTreeNode * bt) {생략}
void MakeLeftSubTree(BTreeNode * main, BTreeNode *sub) { 생략}
void MakeRightSubTree(BTreeNode * main, BTreeNode *sub) { 생략}
void PreorderTraverse(BTreeNOde * bt, VisitFuncPtr action)
{
if(bt==NULL)
return;
action (bt->data);
PreorderTraverse(bt->left, action);
PreorderTraverse(bt->right, action);
}
void InorderTraverse(BTreeNOde * bt, VisitFuncPtr action)
{
if(bt==NULL)
return;
InorderTraverse(bt->left, action);
action (bt->data);
InorderTraverse(bt->right, action);
}
void PreorderTraverse(BTreeNOde * bt, VisitFuncPtr action)
{
if(bt==NULL)
return;
PreorderTraverse(bt->left, action);
PreorderTraverse(bt->right, action);
action (bt->data);
}마지막으로 main 함수를 보이겠다. 그런데 순회 관련 함수의 두번째 인자로 전달되어 노드 방문의 결과를 결정하는 함수는 , 트리를 활용하여 프로그램을 구현하는 프로그래머의 몫이 되어야 한다. 그래서 그러한 의미를 반영하기 위해서, main함수가 위치한 다음 소스파일에 두 번째 인자로 전달되는 함수를 정의하였다.
//BinaryTrereMain2.c
#include <stdio.h>
#include "BinaryTree2.h"
void ShowIntData(int data);
int main()
{
BTreeNode * bt1 = MakeBTreeNode();
BTreeNode * bt2 = MakeBTreeNode();
BTreeNode * bt3 = MakeBTreeNode();
BTreeNode * bt4 = MakeBTreeNode();
BTreeNode * bt5 = MakeBTreeNode();
BTreeNode * bt6 = MakeBTreeNode();
SetData(bt1, 1);
SetData(bt2, 2);
SetData(bt3, 3);
SetData(bt4, 4);
SetData(bt5, 5);
SetData(bt6, 6);
MakeLeftSubTree(bt1, bt2);
MakeRightSubTree(bt1, bt3);
MakeLeftSubTree(bt2, bt4);
MakeRightSubTree(bt2, bt5);
MakeRightSubTree(bt3, bt6);
PreorderTraverse(bt1, ShowIntData);
printf("\n");
InorderTraverse(bt1, ShowIntData);
printf("\n");
PostorderTraverse(bt1, ShowIntData);
printf("\n");
retrun 0;
}
void ShowIntData(int data)
{
printf("%d ", data);
}
==============================실행결과=============================
1 2 4 5 3 6
4 2 5 1 3 6
4 5 2 6 3 1위의 예제에서도, 노드의 방문 결과는 출력이다.
위의 예제를 바탕으로 실제 필요한 다양한 방문의 목적을 달성할 수 도있다.
수식 트리 (Expression Tree)의 구현
이진 트리에 대한 설명에 이어서 이진 트리의 일종인 수식 트리를 설명하고자 한다.
수식 트리의 이해
이진 트리를 이용해서 수식을 표현해 놓은 것을 가리켜 '수식 트리'라 한다. 즉 수식 트리는 이진 트리와 구분이 되는 별개의 것이 아니다. 그럼 수식 트리에 대한 이야기를 시작하겠다. 먼저 다음 수식을 보자
7 + 4 * 2 - 1
우리는 보통 이러한 수식을 컴퓨터가 스스로 알아서 인삭할 수 있다고 생각한다. 그도 그럴 것이 다음과 같은 연산문을 작성하는 것이 가능하기 때문이다.
result = 7 + 4 * 2 -1
그렇다면 컴파일러는 이러한 수식을 어떻게 처리할까? 우리도 알다시피 컴파일러는 위의 코드를 실행이 가능한 상태로 만드는 소프트 웨어이다. 그런데 그 방법을 인간이 결정하여 컴파일러에게 인식시킨다는 사실을 놓치는 경우가 종종있다.
컴퓨터의 유연한 판단을 유도하는 것은 쉽지 않다. 때문에 가급적 정해진 일련의 과정을 거쳐서 수식을 인식할 수 있도록 도와야 한다. 그리고 이를 위해서 수식 트리라는 것을 활용하낟. 결론은 수식을 트리로 표현하면 컴파일러의 수식해석이 좋아진다는 것이다. 따라서 컴파일러는 수식의 이해를 위해서 수식을 수식 트리로 재 표현한다. 그럼 수식 트리의 예를 보이겠다.
위 그림은 앞서 보인 수식을 수식 트리로 표현한 결과이다 .그런데 이를 보면서 다음과 같은 내용이 궁금할 수 있다.
"수식트리는 중위 표기법을 사용하는가? 후위 표기법을 사용하는가?"
그런데 수식 트리는 그냥 수식 트리일 뿐이다. 중위 표기법이 수식 표현의 한가지 방법이라면 수식트리도 이와 대등한, 수식을 표현하는 또 다른 방법일 뿐이다.
그럼 수식 트리의 계산 과정을 한 차례 보이겠다. 수식 트리는 , 그리고 수식 트리를 구성하는 서브트리는 기본저긍로 다음의 방식으로 연산이 진행된다.
"루트 노드에 저장된 연산자의 연산을 하되 ,두 개의 자식 노드에 저장된 두 피연산자를 대상으로 연산을 한다"
즉, 위의 수식 트리에서는 다음 그림에서 보이듯이 곱셉이 먼저 진행되어 그 결과가 +연산자의 오른쪽 자식 노드를 대체하게 된다.
그리고 이어서 다음 그림에서 보이듯이 + 연산이 진행되고 , 그 결과가 - 연산자의 왼쪽 자식 노드를 대체한다.
마지막으로 15와 1을 대상으로 - 연산이 진행되어 최종 연산 결과인 14를 얻게 된다.
이렇듯 수식 트리는 우리가 보아도 연산의 순서과 명확하고, 연산의 과정을 쉽게 파악할 수 있는 이진트리의 일종이다.
우리는 이제 수식 트리를 구성하는 방법에 대해서 고민할 것이다. 그런데 중위 표기법의 수식을 곧장 수식트리로 표현하는 것은 복잡하고 힘든 일이다. 하지만 후위 표기법의 수식을 수식트리로 표현하는 것은 비교적 간단하다. 따라서 다음의 과정을 거쳐서 수식 트리를 만들 도록 프로그램을 작성할 것이다.
중위 표기법의 수식 -> 후위 표기법의 수식 -> 수식 트리
다행이도 우리는 이전에 중위 표기법의 수식을 후위 표기법의 수식으로 바꾸는 함수를 정의한 바가 있다. 따라서 실제로 신경 쓸 것은 후위 표기법의 수식을 수식 트리로 바꾸는 일이므로. 이에 관한 프로그램부터 구현하겠다.
수식 트리의 구현에 필요한 도구와 헤더파일의 정의
수식트리를 구현한다고 하면, 수식 트리의 표현에 필요한 모든 것을 일일이 만들어야 한다고 생각하는 경우를 종종본다. 하지만 그럴필요 없다. 수식 틜도 이진 트리이다. 이진트리를 만드는 도구를 이미 만들어 놓았으니 이것을 활용하면 된다. 수식 트리를 만드는 과정에서 스택을 필요로 하는데, 우리는 스택도 과거에 구현해놨으니 이것도 그냥 활용하면 된다.
수식 트리 구현에 필요한 이진 트리 : BinaryTree2.h, BinaryTree2.c
수식 트리 구현에 필요한 스택 : ListBaseStack.h, ListBaseStack.c
먼저 수식 트리의 표현을 위한 헤더파일을 구현하겠다.
#ExpressionTree.h
#ifndef __EXPRESSION_TREE_H__
#define __EXPRESSION_TREE_H__
#include "BinaryTree2.h"
BTreeNode * MakeExpTree(char exp[]); //수식 트리 구성
int EvaluateExpTree(BTreeNode *bt); //수식 트리 계산
void ShowPrefixTypeExp(BTreeNode * bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode *bt); //후위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode *bt); //후위 표기법 기반 출력
#endif위의 헤더파일에 선언된 함수 중에서 핵심이라 할 수 있는 첫번째 함수는 다음과 같다. 이 함수가 바로 수식 트리를 구성하는 함수이다.
BTreeNode * MakeExpTree(char exp[]); //수식 트리를 구성하는 함수
이 함수는 후위 표기법의 수식을 문자열의 형태로 입력 받으며, 이를 기반으로 수식 트리를 구성하고 그 수식 트리의 주소 값, 정확히 말해서 수식 트리의 루트 노드의 주소 값을 반환한다.
이어서 핵심이 되는 두 번째 함수는 다음과 같다. 이는 인자로 전달된 수식 트리의 수식을 계산하여 그 결과를 반환하는 함수이다.
int EvaluateExpTree(BTreeNode *bt); //수식 트리를 계산하는 함수
마지막으로 수식 트리의 구성을 검증하기 위해서 다음 세 함수를 추가로 정의하고자 한다. 이들은 각각 수식트리의 수식을 전위, 중위, 후위 표기법으로 출력하는 기능의 함수들이다.
void ShowPrefixTypeExp(BTreeNode * bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode *bt); //후위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode *bt); //후위 표기법 기반 출력
그런데 이들은 트리의 순회와 관련이 있어서 그 구현이 어렵지 않다. 예를 들어서 수식 트리를 후위 순회 하면서 노드에 저장된 데이터를 출력하면 그 결과가 바로 후위 표기법의 수식이 된다.
이로써 구현할 함수들에 대해서 모두 언급하였으니, 가장 핵심이 되는 함수 MakeExpTree를 정의해보겠다.
후위 표기법의 수식을 기반으로 수식 트리 구성하기
함수 MakeExpTree의 구현을 위해서 후위 표기법의 수식을 수식 트리로 표현하는 방법을 알아야 한다. 그럼 이에 대한 설명을 위해서 다음 수식을 보자. 이는 후위 표기법의 수식이다.
1 2 + 7 *
이어서 위의 수식을 대상으로 만든 수식 트리를 보이겠으니, 우리 나름대로 구성방법을 고민해보자.
수식 트리의 구성을 위해서는 후위 표기법의 다음 두 가지 특징을 인지하고 있어야 한다.
1. 연산 순서대로 왼쪽에서 오른쪽으로 연산자가 나열된다.
2. 해당 연산자의 두 피연산자는 연산자 앞에 나열된다.
그런데 수식 트리에서는 트리의 아래쪽에 위치한 연산자들의 연산이 먼저 진행된다. 때문에 후위 표기법의 수식에서 먼저 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 트리의 윗부분을 구성해 나가야 한다.
"후위 표기법의 수식에서 앞쪽에 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 수식 트리의 윗부분을 구성해 나간다"
물론 이것이 MakeExpTree 함수의 구현에 있어서 전부는 아니다. 위의 내용을 이해하는 것과 위의 내용대로 수식 트리가 만들어지도록 코드를 작성하는 것은 별개이기 때문이다. 그래서 우리는 수식 트리의 구성과정을 자세히 볼것이다.
1 2 + 7 *
쟁반 : (empty)
이렇게 있다고 가정하자
위의 과정에서는 수식 트리를 만드는데 사용할 수식과 스택을 의미하는 쟁반이 하나 놓여있다. 수식 트리의 구성을 위해서는 스택이 필요하다는 의미이다. 첫번째 단계를 보자.
2+7*
쟁반 : 1
수식을 이루는 문자들을 하나씩 처리해 나가야 하는데, 위의 그림에서 보이듯 문자가 피연산자라면 이를 스택으로 옮긴다.
+7*
쟁반: 1 2
위의 과정에서 보이듯이 이어서 등장한 두번째 문자도 피연산자이므로 조건 없이 그냥 스택으로 옮긴다.
"수식 트리의 구성과정에서 피연산자는 무조건 스택으로 옮긴다"
다음에 등장하는 문자가 연산자이기 때문에 다음은 다르다.
7*
쟁반 : empty
루트 노드 : + , 왼쪽 노드 1, 오른쪽 노드 2
위 과정에서 보이듯이 연산자가 등장하면 , 스택에 쌓여있는 두 개의 피연산자를 꺼내어 연산자의 자식 노드로 연결해야 한다. 먼저 꺼내진 피연산자가 오른쪽 자식 노드가 되고, 그 다음에 꺼내진 피연산자가 왼쪽 자식 노드가 됨에 주의해야 한다.
이렇게 해서 수식 트리의 모양새를 갖추었다. 다음과정에서 보이듯이 만들어진 수식 트리 자체를 스택으로 옮긴다.
7 *
쟁반 : 위에 만들어진 수식 트리
이렇듯 트리 전체를 스택으로 옮기는 이유는, 이것이 다른 연산자의 자식 노드가 되어야 하기 때문이다.
의미적으로 수식 트리 전부를 옮기는 것이 되지만, 실제로 코드상에서는 + 연산자가 젖아된 노드의 주소 값만 스택으로 옮기면 된다. 자식 노드는 연결이 되어 있기 때문이다. 위 과정에서 스택으로 +연산자의 노드를 옮긴다고 해서 자식 노드와의 연결이 끊어지는 것은 아니기 때문이다 .
그리고 다음 단계의 과정을 보자.
*
쟁반 : 수식트리 7
위 과정에서 보이듯이 , 이어서 등장한 것이 피연산자 이므로, 마찬가지로 스택에 옮긴다. 따라서 현재 스택에는 자식 노드가 될 하나의 노드와 하나의 서브트리가 존재하는 상황이다. 그럼 이제 마지막 과정을 보자.
쟁반 : (empt)
위 그림의 수식트리가 완성이 된다.
이어서 등장한 것이 연산자이므로 스택에서 두 개의 노드를 (하나의 노드와 하나의 서브트리를) 꺼내어 각각 오른쪽과 왼쪽의 자식 노드로 연결을 한다.
참고로 이것이 끝이 아니었다면, 아직도 처리해야 할 피연산자와 연산자가 남아 있었다면, 위의 그림에서 만들어진 수식 트리는 다시 스택으로 이동해야 한다. 이제 수식 트리를 구성하는 방법을 이해하였을 것이다. 정리하면 다음과 같다.
1. 피연산자를 만나면 무조건 스택으로 옮긴다.
2. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내어 자식 노드로 연결한다.
3. 자식 노드를 연결해서 만들어진 트리는 다시 스택으로 옮긴다.
기본 원리는 이것이 전부이다. 위에서 말하는 스택에 저장되어 있는 두 개의 피연산자는 노드가 될수 있고, 트리가 될수도 있다는 사실에만 주의하면 된다.
이제 남은 것은 지금까지 설명한 논리를 코드로 그대로 옮기는 것이다. 위에서 설명한 흐름을 그대로 코드로 옮겨서 함수를 정의하면 된다
#include "ListBaseStack.h"
#include "BinaryTree2.h"
.. 몇몇 표준 헤더파일의 선언도 필요
BTreeNode *MakeExpTree(char exp[])
{
Stack stack;
BTreeNode * pnode;
int expLen = strlen(exp);
int i;
StackInit(&stack);
for(i=0;i<expLen;i++)
{
pnode = MakeBTreeNode ();
if(isdigit(exp[i])) //피연산자라면..
{
SetData(pnode, exp[i] -'0'); //문자를 정수로 바꿔서 저장
}
else //연산자라면
{
MakeRightSubTree(pnode, SPop(&stack));
MakeLeftSubTree(pnode, SPop(&stack));
SetData(pnode, exp[i]);
}
SPush(&stack, pnode);
}
return SPop(&stack);
}
이진 트리도 스택도 앞서 우리가 구현한 것을 활용했기 때문에 간단히 구현할 수 있었다. 만약에 이전 것을 이용하지 않고 처음부터 다시 만들었다면, 이렇게 단단히 결과를 확인할 수 없었을 것이다.
이제 우리가 정의한 함수들이 제대로 동작하는지 확인할 차례이다. 그런데 아직은 마땅히 확인할 방법이 없다.
그래서 수식 트리를 전위, 중위, 후위 순회하면서 노드에 저장된 데이터를 출력하는 함수를 정의하고, 그 함수의 호출결과를 관찰하는 것으로 MakeExpTree함수의 검증을 대신하고자 한다.
수식 트리의 순회
수식 트리의 순회 결과를 통해서도 수식 트리의 장점을 파악할 수 있다. 결론부터 정리하면 다음과 같다.
전위 순회하여 데이터를 출력한 결과 : 전위 표기법의 수식
중위 순회하여 데이터를 출력한 결과 : 중위 표기법의 수식
후위 순회하여 데이터를 출력한 결과 : 후위 표기법의 수식
이렇듯 수식 트리를 구성하면 다양한 표기법으로의 수식 표현이 간단해진다. 이제 순회하는 코드를 만들어서 헤더파일에 선언된 다음 함수들을 채워야 할까?
void ShowPrefixTypeExp(BTreeNode * bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode *bt); //후위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode *bt); //후위 표기법 기반 출력
아니다 . 우리가 구현한 이진 트리에서는 다음 함수들이 정의되어 있다. 그리고 이 함수들은 순회의 결과를 결정할 수 있도록 앞서 정의하지 않았는가?
typedef void (*VisitFuncPtr)(BTData data);
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);
때문에 답은 간단하다. 먼저 노드에 저장된 데이터를 출력하는 함수를 다음과 같이 정의한다.
void ShowNodeData(int data)
{
if(0<=data && data <=9)
printf("%d ", data); //피연산자 출력
else
printf("%c ", data); //연산자 출력
}
그리고 이를 기반으로 헤더파일에 선언된 함수들을 다음과 같이 채우면 된다. 즉 앞서 구현해 놓은 순회 함수들을 그대로 활용하는 것이다.
void ShowPrefixTypeExp(BTreeNode * bt) //전위 표기법 기반 출력
{
PreorderTraverse(bt, ShowNodeData);
}
void ShowInfixTypeExp(BTreeNode *bt) //후위 표기법 기반 출력
{
InorderTraverse(bt, ShowNodeData);
}
void ShowPostfixTypeExp(BTreeNode *bt) //후위 표기법 기반 출력
{
PostorderTraverse(bt, ShowNodeData);
}
그럼 지금까지 구현한 내용을 바탕으로 수식 트리의 헤더파일과 소스파일을 제시하고, 이를 테스트 하기 위한 main함수도 소개하겠다.
이진 트리 관련 : BinaryTree2.h BinaryTree2.c
스택 관련 : ListBaseStack.h ListBaseStack.c
수식 트리 관련 : ExpressionTree.h, ExpressionTree.c
main 함수 관련 ExpressionTree.c
위에서 이진 트리 관련 파일은 그냥 가져다 쓰면 된다. 그러나 스택 관련 파일에서는 약간의 변경이 필요하다.
ListBaseStack.h에서 typedef 선언을 다음과 같이 변경해야 한다.
typedef BTreeNode * Data;
이어서 수식 트리 관련 파일과 main함수를 소개하겠다.
//ExpressionTree.h
#ifndef __EXPRESSION_TREE_H__
#define __EXPRESSION_TREE_H__
#include "BinaryTree2.h"
BTreeNode * MakeExpTree(char exp[]);
int EvaluateExpTree(BTreeNode *bt);
void ShowPrefixTypeExp(BTreeNode *bt);
void ShowInfixTypeExp(BTreeNode * bt);
void ShowPostfixTypeExp(BTreeNode * bt);
#endif//ExpressionTree.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
#include "BinaryTree2.h"
BTreeNode * MakeExpTree(char exp[])
{
Stack stack;
BTreeNode * pnode;
int expLen = strlen(exp);
int i;
StackInit(&stack);
for(i=0;i<expLen;i++)
{
pnode = MakeBTreeNode ();
if(isdigit(exp[i]))
{
SetData(pnode, exp[i]-'0');
}
else
{
MakeRightSubTree(pnode, SPop(&stack);
MakeLeftSubTree(Pnode, SPop(&stack);
SetData(pnode, exp[i]);
}
SPush(&stack, pnode);
}
return SPop(&stack);
}
int EvaluateExpTree(BTreeNode *bt)
{
//다음에 설명
}
void ShowNodeData(int data)
{
if(0<=data && data<=9)
printf("%d ", data);
else
printf("%c ", data);
}
void ShowPrefixTypeExp(BTreeNode *bt)
{
PreorderTraverse(bt, ShowNodeData);
}
void ShowInfixTypeExp(BTreeNode *bt)
{
InorderTraverse(bt, ShowNodeData);
}
void ShowPostfixTypeExp(BTreeNode *bt)
{
PostorderTraverse(bt, ShowNodeData);
}//ExpressionMain.c
#include <stdio.h>
#include "ExpressionTree.h"
int main()
{
char exp[] = "12+7*";
BTreeNode * eTree = MakeExpTree(exp);
printf("전위 표기법의 수식 : ");
ShowPrefixTypeExp(eTree); printf("\n");
printf("중위 표기법의 수식 : ");
ShowInfixTypeExp(eTree); printf("\n");
printf("후위 표기법의 수식 : ");
ShowPostfixTypeExp(eTree); printf("\n");
printf("연산의 결과 : %d\n", EvaluateExpTree(eTree));
return 0;
}
=========================실행결과================
전위 표기법의 수식 : * + 1 2 7
중위 표기법의 수식 : 1 + 2 * 7
후위 표기법의 수식 : 1 2 + 7 *
연산의 결과 : 21수식 트리의 계산
수식 트리에 담겨있는 수식을 계산하는 함수를 정의하라고 하면, 단말 노드가 붙어 있는 서브 트리에서부터 계산을 해야 한다고 생각을 한다. 하지만 트리는 재귀적인 구조를 띠므로 접근 방법을 달리 해야한다. 먼저 다음 함수를 보자.
int EvaluateExpTree(BTreeNode *bt)
{
int op1, op2;
op1 = GetData (GetLeftSubTree(bt)); //첫번째 피연산자
op2 = GetData(GetRightSubTree(bt)); //두번째 피연산자
switch(GetData(bt)) //연산자를 확인하여 연산을 진행
{
case '+' :
return op1 + op2;
case '-':
return op1-op2;
case '*' :
return op1 * op2;
case '/':
return op1/ op2;
}
return 0;
}
위의 함수는 두 개의 자식 노드에 담겨있는 두 피연산자를 확인하고, 부모 노드에 저장된 연산자를 확인하여 연산을 진행한다. 따라서 이 함수는 분명 수식 트리의 수식을 계산한다. 다만 자식 노드에 , 피연산자가 아닌 서브 트리가 달려있는 경우에 문제가 된다. 그럼 위의 함수를 어떻게 변경해야 할까? 걱정없다. 위의 함수 EvaluateExpTree가 수식 트리를 계산하는 함수가 아닌가? 따라서 다음과 같이 변경하면 서브 트리의 수식을 계산해 낼것이다.
int EvaluateExpTree(BTreeNode *bt)
{
int op1, op2;
op1 = EvaluateExpTree(GetLeftSubTree(bt)); //왼쪽 서브 트리 계산
op2 = EvaluateExpTree(GetRightSubTree(bt)); //오른쪽 서브 트리 계산
switch(GetData(bt)) //연산자를 확인하여 연산을 진행
{
case '+' :
return op1 + op2;
case '-':
return op1-op2;
case '*' :
return op1 * op2;
case '/':
return op1/ op2;
}
return 0;
}
이렇게 재귀적으로 정의해 놓으면, 서브 트리의 서브 트리가 존재해도 문제 없다. 이것이 바로 재귀의 위력이다.
위의 재귀 함수에는 탈출 조건이 존재하지 않는다. 그럼 위와 관련해서 위의 함수의 일부를 구성하는 다음 두 문장을 보자.
op1 = EvaluateExpTree(GetLeftSubTree(bt)); //왼쪽 서브 트리 계산
op2 = EvaluateExpTree(GetRightSubTree(bt)); //오른쪽 서브 트리 계산
보다시피 서브 트리를 대상으로 , 서브 트리의 주소 값을 전달하여 EvaluateExpTree함수를 호출하고 있다. 따라서 이 함수의 탈출 조건은 다음과 같이 정의하면 된다.
"전달된 것이, 서브 트리가 추가로 달려있지 않은 단말 노드의 주소 값이라면, 그 단말 노드에 저장된 피연산자를 반환한다."
수식 트리의 구조를 봐서 알겠지만 단말 노드에는 피연산자 정보가 담기기 마련이다. 따라서 탈출 조건을 명시하여 함수를 다음과 같이 완성할 수 있다.
int EvaluateExpTree(BTreeNode *bt)
{
int op1, op2;
if(GetLeftSubTree(bt) == NULL && GetRightSubTree(bt) ==NULL) //단말 노드라 면
return GetData(bt);
op1 = EvaluateExpTree(GetLeftSubTree(bt)); //왼쪽 서브 트리 계산
op2 = EvaluateExpTree(GetRightSubTree(bt)); //오른쪽 서브 트리 계산
switch(GetData(bt)) //연산자를 확인하여 연산을 진행
{
case '+' :
return op1 + op2;
case '-':
return op1-op2;
case '*' :
return op1 * op2;
case '/':
return op1/ op2;
}
return 0;
}
위의 함수가 위치해야 할 소스파일은 앞서 소개한 ExpressionTree.c이다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 우선순위 큐(Priority Queue) 와 힙(Heap) 2 (0) | 2021.03.08 |
|---|---|
| 우선순위 큐(Priority Queue) 와 힙(Heap) 1 (0) | 2021.03.07 |
| 트리 1 (0) | 2021.03.02 |
| 덱(Deque)의 이해와 구현 (0) | 2021.03.01 |
| 큐(Queue)의 연결리스트 기반 구현 (0) | 2021.02.28 |
