[자료구조] ch 4. 트리 (2) - 수식 트리, 분리 집합

4.3 수식 트리 

 

수식 이진 트리(Expression Binary Tree)

- 수식을 표현하는 이진 트리 

- 피연산자는 잎 노드이다.

- 연산자는 뿌리 노드 또는 가지 노드이다.

 

ex) 1*2+(7-8)

- 뿌리 노드를 연산자로, 왼쪽 하위 수식 트리의 결괏값과 오른쪽 하위 수식 트리의 결괏값을 피연산자로 하여 계산을 수행하면 전체 수식의 계산 결과를 얻을 수 있음

-가장 아래에 있는 하위 수식 트리(잎 노드)로부터 수 또는 계산 결괏값을 병합해 올라가는 과정을 반복하며 계산을 수행

- 후위 순회는 왼쪽 하위 트리 - 오른쪽 하위 트리 - 뿌리 노드 순으로 순회하기 때문에 양쪽 하위 트리에서부터 결괏값을 병합해 올라와야 하는 수식 트리를 계산할 때 안성맞춤

 

4.3.1 수식 트리 구축 방법

 

수식 트리 구축 알고리즘

 

1) 수식을 뒤에서부터 앞쪽으로 읽어나가며 토큰을 취한다.

 

2) 수식에서 제일 마지막에 있는 토큰으로 뿌리 노드를 생성한다. 후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.

 

3) 읽어낸 토큰이 연산자인경우 가지 노드를 생성하여 이 토큰 다음에 따라오는 2개의 토큰으로 각각 오른쪽 자식 노드와 왼쪽 자식 노드를 생성한다. 단, 다음 토큰도 연산자인 경우 이 토큰에서 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰으로 왼쪽 자식 노드를 생성한다.

 

4) 읽어낸 토큰이 숫자인 경우 잎 노드를 생성한다.

 

4.3.2 수식 트리의 구현

 

수식 트리 생성 함수 ET_BuildExpressionTree 

 

- 입력된 후위 표기식으로부터 수식 트리를 만듬

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

- 읽어낸 토큰이 연산자라면 이는 2개의 피연산자가 뒤따라온다는 사실을 의미 

- 방금 읽어낸 연산자 토큰을 노드에 연결하고, 바로 이어서 ET_BuildExpressionTree()를 두 번 호출하여 뒤따라오는 피연산자 둘을 연산자 노드의 양쪽 자식으로 연결

 

//수식 트리 구축
void ET_BuildExpressionTree(char* PostfixExpression, ETNode** Node)
{
	int len = strlen(PostfixExpression);
	char Token = PostfixExpression[len - 1];
	PostfixExpression[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

 

- 토큰이 연산자일 때는 트리의 바닥(잎)부터 계산 결과를 병합하여 올라가도록 노드의 양쪽 자식에 대하여 ET_Evaluate()를 재귀 호출 

- 재귀 호출한 ET_Evaluate()가 값을 반환하면 왼쪽 수식 트리의 계산 결과는 Left 변수에, 오른쪽 수식 트리의 계산 결과는 Right 변수에 저장 

- 연산자의 종류에 따라 덧셈, 뺄셈, 곱셈, 나눗셈을 수행

 

- 토큰이 피연산자인 경우 토큰에 담겨있던 값을 수로 변환해서 반환

//수식 트리 계산
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->Left);
		Right = ET_Evaluate(Tree->Right);

		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 :
		//Temp가 가리키는 곳을 0으로 Temp 사이즈만큼 채움
		memset(Temp, 0, sizeof(Temp));
		Temp[0] = Tree->Data;
		//char to float : char 형식을 float로 바꿈
		Result = atof(Temp);
		break;
	}

	return Result;

}

 

4.3.3 수식 트리 예제 프로그램

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


typedef char ElementType;

typedef struct tagETNode
{
	struct tagETNode* Left;
	struct tagETNode* Right;

	ElementType Data;
}ETNode;

//노드 생성 
ETNode* ET_CreateNode(ElementType NewData)
{
	ETNode* NewNode = (ETNode*)malloc(sizeof(ETNode));
	NewNode->Left = NULL;
	NewNode->Right = 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->Left);
	ET_DestroyNode(Root->Right);
	ET_DestroyNode(Root);
}

//전위 순회 
void ET_PreorderPrintTree(ETNode* Node)
{
	if (Node == NULL)
		return;

	printf(" %c", Node->Data);

	ET_PreorderPrintTree(Node->Left);
	ET_PreorderPrintTree(Node->Right);
}

//중위 순회 
void ET_InorderPrintTree(ETNode* Node)
{
	if (Node == NULL)
		return;
	printf("(");
	ET_InorderPrintTree(Node->Left);

	printf(" %c", Node->Data);

	ET_InorderPrintTree(Node->Right);
	printf(")");
}

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

	ET_PostorderPrintTree(Node->Left);
	ET_PostorderPrintTree(Node->Right);
	printf(" %c", Node->Data);
}

//수식 트리 구축
void ET_BuildExpressionTree(char* PostfixExpression, ETNode** Node)
{
	int len = strlen(PostfixExpression);
	char Token = PostfixExpression[len - 1];
	PostfixExpression[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;
	}
}

//수식 트리 계산
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->Left);
		Right = ET_Evaluate(Tree->Right);

		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 :
		//Temp가 가리키는 곳을 0으로 Temp 사이즈만큼 채움
		memset(Temp, 0, sizeof(Temp));
		Temp[0] = Tree->Data;
		//char to float : char 형식을 float로 바꿈
		Result = atof(Temp);
		break;
	}

	return Result;

}

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

	char PostfixExpression[20] = "*71*52-/";
	ET_BuildExpressionTree(PostfixExpression, &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");

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

	//트리 소멸
	ET_DestroyTree(Root);

	return 0;
}

 

 

4.4 분리 집합

 

집합(Set)

 

 - 특정 조건에 맞는 원소의 모임

 

분리 집합(Disjoint Set)

 

 - 서로 공통된 원소를 갖지 않는, 즉 교집합을 갖지 않는 복수의 집합

 - 분리 집합에는 합집합(Union)만 존재 

 - 소속 관계가 분명해야 하는 데이터를 다룰 때 유용

 - 원소 또는 개체가 '어느 집합에 소속되어 있는가?'라는 정보를 바탕으로 무언가를 하는 알고리즘에 응용

 

ex) 도서 판매 관리 프로그램의 책의 가격 정보 

typedef struct tagBookPrice
{
    unsigned long ISBN; //책을 나타내는 고유 식별 번호
    unsigned long Price; //가격 정보 
}BookPrice;

- 가게 홍보를 위해 베스트셀러 한정으로 일주일간 할인 판매 행사를 진행

 -> 할인 행사는 임시적이기 때문에 BookPrice 구조체의 Price 값을 바꿔서는 안됨

 -> 행사가 끝나면 원래의 가격으로 일일이  다시 입력해야 하는 번거로움 존재 

 

- 분리 집합을 이용하여 '일반 도서 집합'과 '베스트셀러 집합'을 만들고 베스트셀러들의 BookPrice가 베스트셀러 집합의 원소가 되게 함 

- 이 경우 해당 BookPrice 개체가 베스트셀러 집합에 속해 있는지 여부만 알면 할인 가격으로 판매할지 원래 가격으로 판매할지 알 수 있음

- 할인 행사가 끝난 뒤에는 집합에서 모든 원소를 일반 도서 집합으로 옮기기만 하면 됨 

 

4.4.1 분리 집합 표현 

 

- 트리와 이진 트리는 부모가 자식을 가리키는 포인터를 갖고 있음

- 분리 집합은 이와 반대로 자식이 부모를 가리킴

- 뿌리 노드는 집합 그 자체이고, 뿌리 노드 자신을 포함한 트리 내의 모든 노드는 그 집합에 소속됨

분리 집합 노드의 구조체 

- 뿌리 노드는 부모가 없으므로 parent가 NULL

typedef struct tagDisjointSet
{
    struct tagDisjointSet* Parent; //부모 노드에 대한 포인터 
    void* Data;
}DisjointSet;

 

4.4.2 분리 집합의 기본 연산 

 

1) 합집합 연산 

 

- 합집합(Union)은 두 집합을 더하는 연산 

- 분리 집합을 이루는 트리 내의 모든 노드는 뿌리 노드가 나타내는 집합 안에 있음

- 두 집합을 합한다고 하면, 오른쪽에 있는 집합의 뿌리 노드를 왼쪽에 있는 뿌리 노드의 자식 노드로 만들면 됨 

 - 오른쪽 뿌리 노드(5)의 부모 노드를 1로 지정

//합집합 연산
void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2)
{
	Set2 = DS_FindSet(Set2);
	Set2->Parent = Set1;
}

 

2) 집합 탐색 연산 

 

- 분리 집합의 탐색(Find)은 집합에서 원소를 찾는 것이 아니라 원소가 속한 집합을 찾는 연산 

- 집합 내 어떤 노드에게든 트리의 최상위에 있는 뿌리 노드가 곧 자신이 속한 집합을 나타내므로 해당 원소(노드)가 어떤 집합에 속해 있는지 알려면 이 원소가 트리의 뿌리 노드를 찾으면 됨.

 

- 분리 집합의 각 노드는 '부모'노드를 가리키는 포인터를 가짐

- 이 포인터를 타고 쭉 올라가면 부모가 NULL인 뿌리 노드를 만날 수 있음 

- 뿌리 노드는 곧 집합을 나타내므로 이것을 반환하면 해당 노드가 소속된 집합을 반환하게 되는 것

//집합 탐색 연산
DisjointSet* DS_FindSet(DisjointSet* Set)
{
	while (Set->Parent != NULL)
	{
		Set = Set->Parent;
	}

	return Set;
}

 

4.4.3 분리 집합 예제 프로그램

 

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

//분리 집합의 구조체 
typedef struct tagDisjoinSet
{
	struct tagDisjointSet* Parent;
	void* Data;
}DisjointSet;


//집합 탐색 연산
DisjointSet* DS_FindSet(DisjointSet* Set)
{
	while (Set->Parent != NULL)
	{
		Set = Set->Parent;
	}

	return Set;
}

//합집합 연산
void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2)
{
	Set2 = DS_FindSet(Set2);
	Set2->Parent = Set1;
}

//집합 생성
DisjointSet* DS_MakeSet(void* NewData)
{
	DisjointSet* NewNode = (DisjointSet*)malloc(sizeof(DisjointSet));
	NewNode->Data = NewData;
	NewNode->Parent = NULL;

	return NewNode;
}

//집합 소멸 
void DS_DestroySet(DisjointSet* Set)
{
	free(Set);
}

int main(void)
{
	int a = 1, b = 2, c = 3, d = 4;
	DisjointSet* Set1 = DS_MakeSet(&a);
	DisjointSet* Set2 = DS_MakeSet(&b);
	DisjointSet* Set3 = DS_MakeSet(&c);
	DisjointSet* Set4 = DS_MakeSet(&d);

	printf("Set1 == Set2 : %d\n", DS_FindSet(Set1) == DS_FindSet(Set2));

	DS_UnionSet(Set1, Set3);
	printf("Set1 == Set3:%d\n", DS_FindSet(Set1) == DS_FindSet(Set3));

	DS_UnionSet(Set3, Set4);
	printf("Set3 == Set4:%d\n", DS_FindSet(Set3) == DS_FindSet(Set4));

	return 0;
}