[ 자료구조 ] 트리 - 03 . 수식트리

 

[수식트리]

[수식트리]

수식을 표현하는 이진트리 . 수식 이진 트리라고 부르기도 한다 .

일반적으로 수식트리는 하나의 연산자가 두개의 피연산자를 취한다는 가정하에 다음 두가지 규칙을 가진다 .

1. 피연산자는 잎 노드이다 .
2. 연산자는 루트노드 / 혹은 가지노드이다 .

[예제]

1*2+(7+8)

 

루트노드/가지노드는 피연산자 (수 / 식)를 양쪽 자식으로 둔다 .

이런 방법으로 수식트리는 가장 아래에 있는 하위 수식 트리로부터 수 또는 계산결과를

병합해 올라가는 과정을 반복하며 계산을 수행한다 .

 

이러한 수식트리의 성질에는 후위순회(왼쪽 노드- 오른쪽 노드 - 루트 노드)가 알맞다 .

양쪽 하위 트리에서부터 결과값을 병합해 올라와야 하기때문이다 .

 

[수식트리의 구축]

[수식트리]

컴퓨터가 처리하기 좋은 후위 표기식을 이용해 트리를 구축하는 것이 수월하다 .

후위 표기식에 기반한 수식 트리 구축 알고리즘은 다음과 같다 .

1. 수식을 뒤에서 부터 앞으로 읽어 나간다 .
2. 수식에서 제일 마지막 토근은 루트 노드가 된다 . 후위 표기식 가장 마지막 토큰은 항상 연산자이다.
3. 수식에서 읽어낸 토큰이 연산자라면 가지노드가 , 이 토큰 다음 두개의 토큰은 오른쪽,왼쪽 자식노드가 된다 .               (다음 토큰에도 연속해서 연산자인 경우 이 토큰으로 부터 만들어진 하위 트리가 완성된 이후 읽어낸 토큰이 왼쪽 자식 노드가 된다)
4. 수식에서 읽어낸 토큰이 숫자면 이 노드는 잎 노드이다 .

[예제]

1 2 * 7 8 - +

 

1. 마지막 토큰인 + 가 루트 노드가 된다 .

2. 다음 토큰이 연산자 - 이므로 두번째 토큰은 첫번째 토큰의 피 연산자가 된다 .

3. 다음 토큰 - 는 연산자이므로 다음 토큰 7,8 은 오른쪽 왼쪽의 자식이 된다 . 새로운 자식은 연산자이니 자식이 없는 잎 노드이다 . 이렇게 + 노드의 오른쪽 하위 수식 트리가 완성되었으니 왼쪽 자식으로 넘어간다 .

4.* 는 +의 왼쪽 자식이 된다 .

5.1,2는 *의 왼쪽,오른쪽 자식 노드가 되고 수식을 모두 읽었으니 전체 수식트리 완성

[수식트리의 주요연산]

[수식트리 구축하기]

 매개변수로 입력된 후위 표기식을 뒤부터 읽어 토큰 하나를 분리한다 .

읽어낸 토큰이 연산자라면 뒤 두개의 피연산자가 뒤 따라온다 .

이 경우 연산자 토큰을 노드에 연결 , ET_BuildExpressionTree()를 두번 호출하여 따라오는 피연산자

둘을 양쪽 자식으로 결합한다 . 처음 읽은 토큰이 피연산자라면 토큰을노드에 입력 함수를 반환한다 .

void ET_BuildExpressionTree(char* PostfixExpression , ETNode** Node)
{
    int len=strlen(PostfixExpression);
    char Token=PostfixExpression[len-1];
    PostficExpression[len-1]='\0';
    
    switch(Token)
    {
    	case '+':case '-': case '/': case '*' :
        (*Node) = ET_CreateNode(Token);
        ET_BuildExpressionTree(PostfixExpression , &(*Node)->Right);
        ET_BuildExpressionTree(PostfixExpression , &(*Node)->Left);
        break;
        
        default:
        (*Node)=ET_CreateNode(Token);
        break;
    }
}

 

[수식트리 계산하기]

앞서 만든 수식트리의 노드에 담긴 토큰을 확인하고 , 연산자 / 피연산자 나누어 처리한다 .

• 노드의 양쪽 자식에 대해 ET_Evaluate()를 재귀호출한다 . 재귀호출하여 반환된 왼쪽트리의 계산결과는 left변수에       오른쪽 수식 트리의 결과는 Right변수에 저장한다 . 이후 연산자의 종류에 따라 계산을 수행한다
• 피연산자라면 토큰에 담겨있던 값을 수로 변환해 반환한다 . 

double EV_Evaluate(ETNode* Tree)
{
	char Temp[2];
    
    double Left = 0;
    double Right = 0;
    double Result =0;
    
    if(Tree == NULL)
    return 0;
    
    switch(Tree -> Data)
    {
    	case '+':case'-':case '*': case '/':
        
        Left = ET_Evaluate(Tree->Left);
        Right = ET_Evaluate(Tree -> Rigjt);
        
        if(Tree->Data =='+' result =Left+Right;
        else if(Tree->Data == '-' result = Left - Right;
        else if(Tree->Data == '*' result = Left * Right;
        else if(Tree->Data == '/' result = Left / Right;
        break;
        
        default : 
        memset(Temp , 0 ,sizeof(Temp));
        Temp[0]=tree->Data;
        Result = atof(Temp);
        break;
    }
    
    return Result;
}

[수식트리의 구현]

[ET.h]

#ifndef ET
#define ET

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

typedef char ElementType;

typedef struct tagETNode
{
	tagETNode* LeftNode;
	tagETNode* RightNode;
	ElementType Data;
}ETNode;

//노드 생성
ETNode* ET_CreateNode(ElementType NewData);
//노드 삭제
void ET_DestroyNode(ETNode* Node);
//트리 삭제
void ET_DestroyTree(ETNode* Root);
//전위 순회
void ET_PreorderPrintTree(ETNode* Node);
//중위 순회
void ET_InorderPrintTree(ETNode* Node);
//후위 순회
void ET_PostorderPrintTree(ETNode* Node);
//후위표기식을 트리로
void ET_BuildExpressioinTree(char* PostfixExpression, ETNode** Node);
//트리를 계산
double ET_Evaluate(ETNode* Tree);





#endif // !ET

[ET.cpp]

#include"ET.h"

//노드 생성
ETNode* ET_CreateNode(ElementType NewData)
{
	ETNode* NewNode = (ETNode*)malloc(sizeof(ETNode));
	NewNode->LeftNode = NULL;
	NewNode->RightNode = NULL;
	NewNode->Data = NewData;
	return NewNode;
}
//노드 삭제
void ET_DestroyNode(ETNode* Node)
{
	free(Node);
}
//트리 삭제
void ET_DestroyTree(ETNode* Root)
{
	if (Root == NULL)
		return;

	ET_DestroyNode(Root->LeftNode);
	ET_DestroyNode(Root->RightNode);
	ET_DestroyNode(Root);
}
//전위 순회
void ET_PreorderPrintTree(ETNode* Node)
{
	if (Node == NULL)
		return;

	printf("%c", Node->Data);
	ET_PreorderPrintTree(Node->LeftNode);
	ET_PreorderPrintTree(Node->RightNode);
}
//중위 순회
void ET_InorderPrintTree(ETNode* Node)
{
	if (Node == NULL)
		return;
	printf("(");
	ET_InorderPrintTree(Node->LeftNode);
	printf("%c", Node->Data);
	ET_InorderPrintTree(Node->RightNode);
	printf(")");

}
//후위 순회
void ET_PostorderPrintTree(ETNode* Node)
{
	if (Node == NULL)
		return;

	ET_PostorderPrintTree(Node->LeftNode);
	ET_PostorderPrintTree(Node->RightNode);
	printf("%c", Node->Data);
}
//후위표기식을 트리로
void ET_BuildExpressioinTree(char* PostfixExpression, ETNode** Node)
{
	int length = strlen(PostfixExpression);
	//토큰을 받아온다
	char Token = PostfixExpression[length - 1];
	//받아온 부분은 널문자로 초기화 (strlen은 NULL 전까지의 길이 반환)
	PostfixExpression[length - 1]='\0';

	//토큰의 유형에 따라 
	switch (Token)
	{
		//연산자라면
	case '+':case '-':case '*':case '/':
	{
		//노드에는 나를 넣어주고 (두개) 오른쪽 -> 왼쪽 노드에서 다시 토큰값을 받아 처리를 한다 .
		(*Node)= ET_CreateNode(Token);
		ET_BuildExpressioinTree(PostfixExpression,&(*Node)->RightNode);
		ET_BuildExpressioinTree(PostfixExpression, &(*Node)->LeftNode);
		break;
	}
	default:
		//피연산자라면 노드에 나를 넣는다.
		(*Node) = ET_CreateNode(Token);
		break;
	}



}
//트리를 계산
double ET_Evaluate(ETNode* Tree)
{
	char Temp[2];

	double Left = 0;
	double Right = 0;
	double Result = 0;

	if (Tree == NULL)
		return 0;

	//트리의 데이터에 따라 분기
	switch (Tree->Data)
	{
		//연산자라면
	case '+':case '-':case '*':case '/':
	{
		//왼쪽 계산
		Left=ET_Evaluate(Tree->LeftNode);
		//오른쪽 계산
		Right= ET_Evaluate(Tree->RightNode);

		//나온 데이터를 연산하여 반환
		if (Tree->Data == '+')Result = Left + Right;
		else if (Tree->Data == '-')Result = Left - Right;
		else if (Tree->Data == '/')Result = Left / Right;
		else if (Tree->Data == '*')Result = Left * Right;
		break;
	}
	default:
			//피연산자라면 나를 반환 .
		//쓰레기값 없이 초기화
		memset(Temp, 0, sizeof(Temp));
		Temp[0] = Tree->Data;
		//문자열을 숫자로
		Result = atof(Temp);
		break;
	}
	return Result;
}

[Test.cpp]

#include "ET.h"

int main(void)
{
	ETNode* Root = NULL;

	char PostfixExpressioin[20] = "71*52-/";
	ET_BuildExpressioinTree(PostfixExpressioin, &Root);

	printf("Preorder ... \n");
	ET_PreorderPrintTree(Root);
	printf("\n\n");

	printf("Inorder ... \n");
	ET_InorderPrintTree(Root);
	printf("\n\n");

	printf("Postorder ... \n");
	ET_PostorderPrintTree(Root);
	printf("\n\n");

	printf("Evaluate Result : %f\n", ET_Evaluate(Root));

	ET_DestroyNode(Root);
	printf("종료");
	return 0;

}