[자료구조] ch 4 트리 (1) - 이진 트리

4.1 트리 ADT

 

4.1.1 트리의 개념 

 

- 트리는 나무를 닮은 자료구조 

- 운영체제 파일 시스템, DOM, 검색 엔진, 데이터베이스 

 

4.1.2 트리의 구성 요소 

 

뿌리(root)

 - 트리 자료구조의 가장 위에 있는 노드 

 

가지(Branch)

 - 뿌리와 잎 사이에 있는 모든 노드

 

잎(Leaf)

 - 가지의 끝에 매달린 노드 

 - 단말 노드 (Terminal node)

 

- B는 C와 D의 부모 (Parent)

- C와 D는 B의 자식(Children)

- C와 D는 형제 (Sibling)

 

경로(Path)

 - 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서 

 ex) B 노드에서 F 노드를 찾아가려면 B 노드에서 출발하여 D 노드를 방문하고 D에서 출발하여 F에 도착 'B->D->F'

 

길이 (Length)

 - 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수 

 ex) B,D,F 경로의 길이는 2가 됨 

 

깊이(Depth)

 - 뿌리 노드에서 해당 노드까지 이르는 경로의 길이 

 

레벨(Level)

 - 깊이가 같은 노드의 집합 

 - 트리의 높이는 '가장 깊은 곳'에 있는 잎 노드까지의 깊이 

 

차수(Degree)

 - 노드의 차수는 그 노드의 자식 노드 개수 

 - 트리의 차수는 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수 

 

 

4.1.3 노드 표현 방법 

 

- 부모와 자식, 형제 노드를 서로 연결 짓는 방법 

 

N-링크 표현법 (N-Link)

 

 - 노드의 차수가 N이라면 노드가 N개의 링크를 갖고 있는데 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성

 

왼쪽 자식 - 오른쪽 형제 (Left Child - Right Sibling) 표현법 

 

- 왼쪽 자식과 오른쪽 형제에 대한 포인터만을 갖도록 노드를 구성하는 방법 

 

- 어느 한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 됨 

 - 해당 포인터를 이용해서 왼쪽 자식 노드의 주소를 얻은 후, 이 자식 노드의 오른쪽 형제 노드의 주소를 얻고, 그 다음 오른쪽 형제 노드의 주소를 계속해서 얻어나가면 됨

 

 

4.1.4 트리의 기본 연산 

 

1) 노드 선언

노드 구조체 

 - 데이터를 담는 Data 필드 

 - 왼쪽 자식( Left Child) , 오른쪽 자식 (Right Child)를 가리키는 포인터 

typedef struct tagLRCSNode
{
	struct tagLCRSNode* LeftChild;
	struct tagLCRSNode* RightSibling;

	ElementType Data;
}LCRSNode;

 

2) 노드 생성/소멸 연산 

 

노드 생성 함수 LCRS_CreateNode

 

- malloc() 함수를 이용하여 LCRSNode 구조체의 크기만큼 힙에 메모리를 할당하고 매개변수 NewData를 Data에 저장한 후 노드의 메모리 주소를 반환 

//노드 생성 
LCRSNode* LCRS_CreateNode(ElementType NewData)
{
	LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
	NewNode->LeftChild = NULL;
	NewNode->RightSibling = NULL;
	NewNode->Data = NewData;

	return NewNode;
}

 

노드 소멸 함수 LCRS_DestroyNode

 

- 노드를 힙에서 할당 해제 

//노드 소멸 
void LCRS_DestroyNode(LCRSNode* Node)
{
	free(Node);
}

 

3) 자식 노드 연결 

 

자식 노드 연결 함수 LRCS_AddChildNode

- 부모 노드와 이 부모 노드에 연결할 자식 노드를 매개변수로 받음

- 부모 노드인 Parent에게 자식 노드가 있는지 검사

  -> LeftChild가 NULL인 것을 확인하면 자식이 하나도 없다는 사실을 알 수 있음 

  -> Parent에게 자식 노드가 하나도 없다면 Parent의 LeftChild 포인터에 자식 노드 주소를 바로 저장하면 됨 

 

- Parent의 LeftChild가 NULL이 아닌 경우 자식 노드를 하나 이상 갖고 있다는 의미 

  -> 자식 노드의 RightSibling 포인터를 이용해서 가장 오른쪽에 있는 자식 노드 (RightSibling이 NULL인 노드)를 찾아냄

  -> 이렇게 찾아낸 가장 오른쪽 자식 노드의 RightSibling에 Child를 대입 

void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child)
{
	if (Parent->LeftChild == NULL)
	{
		Parent->LeftChild = Child;
	}
	else
	{
		LCRSNode* TempNode = Parent->LeftChild;
		while (TempNode->RightSibling != NULL)
			TempNode = TempNode->RightSibling;
		TempNode->RightSibling = Child;
	}
}

 

4) 트리 출력

 

트리 출력 함수 LCRS_PrintTree

 

- for 루프가 매개변수로 입력된 'Depth(깊이)-1'만큼 공백을 3칸씩 출력

- 공백 마지막에는 해당 노드가 누군가의 자식 노드임을 나타내는 '+--'를 덧붙인 후 노드의 데이터를 출력 

- 깊이가 0인 뿌리 노드는 제일 앞쪽에 출력되고 잎 노드는 제일 뒤쪽(깊은 곳)에 출력

//트리 출력
void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
	//들여쓰기 
	int i = 0;
	for (i = 0; i < Depth - 1; i++)
		printf("   "); //공백 3칸

	if (Depth > 0) //자식 노드 여부 표시
		printf("+==");

	//노드 데이터 출력
	printf("%c\n", Node->Data);

	if (Node->LeftChild != NULL)
		LCRS_PrintTree(Node->LeftChild, Depth + 1);
	if (Node->RightSibling != NULL)
		LCRS_PrintTree(Node->RightSibling, Depth);
}

 

4.1.5 트리 에제 프로그램 

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

typedef char ElementType;

typedef struct tagLRCSNode
{
	struct tagLCRSNode* LeftChild;
	struct tagLCRSNode* RightSibling;

	ElementType Data;
}LCRSNode;

//노드 생성 
LCRSNode* LCRS_CreateNode(ElementType NewData)
{
	LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
	NewNode->LeftChild = NULL;
	NewNode->RightSibling = NULL;
	NewNode->Data = NewData;

	return NewNode;
}

//노드 소멸 
void LCRS_DestroyNode(LCRSNode* Node)
{
	free(Node);
}


//트리 제거 
void LCRS_DestroyTree(LCRSNode* Root)
{
	if (Root->RightSibling != NULL)
		LCRS_DestroyTree(Root->RightSibling);
	if (Root->LeftChild != NULL)
		LCRS_DestroyTree(Root->LeftChild);

	Root->LeftChild = NULL;
	Root->RightSibling = NULL;

	LCRS_DestroyNode(Root);
}

//자식 노드 연결
void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode* Child)
{
	if (Parent->LeftChild == NULL)
	{
		Parent->LeftChild = Child;
	}
	else
	{
		LCRSNode* TempNode = Parent->LeftChild;
		while (TempNode->RightSibling != NULL)
			TempNode = TempNode->RightSibling;
		TempNode->RightSibling = Child;
	}
}

//트리 출력
void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
	//들여쓰기 
	int i = 0;
	for (i = 0; i < Depth - 1; i++)
		printf("   "); //공백 3칸

	if (Depth > 0) //자식 노드 여부 표시
		printf("+==");

	//노드 데이터 출력
	printf("%c\n", Node->Data);

	if (Node->LeftChild != NULL)
		LCRS_PrintTree(Node->LeftChild, Depth + 1);
	if (Node->RightSibling != NULL)
		LCRS_PrintTree(Node->RightSibling, Depth);
}

int main()
{
	//노드 생성 
	LCRSNode* Root = LCRS_CreateNode('A');
	LCRSNode* B = LCRS_CreateNode('B');
	LCRSNode* C = LCRS_CreateNode('C');
	LCRSNode* D = LCRS_CreateNode('D');
	LCRSNode* E = LCRS_CreateNode('E');
	LCRSNode* F = LCRS_CreateNode('F');
	LCRSNode* G = LCRS_CreateNode('G');
	LCRSNode* H = LCRS_CreateNode('H');
	LCRSNode* I = LCRS_CreateNode('I');
	LCRSNode* J = LCRS_CreateNode('J');
	LCRSNode* K = LCRS_CreateNode('K');

	//트리에 노드 추가 
	LCRS_AddChildNode(Root, B);
		LCRS_AddChildNode(B,C);
		LCRS_AddChildNode(B,D);
			LCRS_AddChildNode(D,E);
			LCRS_AddChildNode(D,F);

	LCRS_AddChildNode(Root, G);
		LCRS_AddChildNode(G, H);

	LCRS_AddChildNode(Root, I);
		LCRS_AddChildNode(I, J);
			LCRS_AddChildNode(J, K);

	//트리 출력 
	LCRS_PrintTree(Root, 0);

	//트리 소멸
	LCRS_DestroyNode(Root);

	return 0;
}

 

 

4.2 이진 트리 

 

이진 트리 (Binary Tree)

 

- 하나의 노드가 자식 노드를 2개까지만 가질 수 있음

- 노드의 최대 차수가 2

- 컴파일러나 검색과 같은 알고리즘의 뼈대가 되는 특별한 자료구조 

- 이진트리를 이용한 검색에서는 트리의 노드를 가능한 한 완전한 모습으로 유지해야 높은 성능을 보임

- 수식 이진트리, 이진 탐색 트리 

 

4.2.1 이진 트리의 종류 

 

포화 이진 트리 (Full Binary Tree)

- 잎 노드들이 모두 같은 깊이에 위치 

완전 이진 트리 (Complete Binary Tree)

- 잎 노드들이 트리 왼쪽부터 차곡차곡 채워짐

 

높이 균형 트리 (Height Balanced Tree)

 - 뿌리 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 2 이상 차이 나지 않는 이진 트리 

 

완전 높이 균형 트리 (Completely Height Balanced Tree)

 - 뿌리 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리

 

4.2.2 이진 트리의 순회 

 

순회(Traversal)

 - 트리 안에서 노드 사이를 이동하는 연산 

 

전위 순회(Preorder Traversal)

 - 뿌리 노드부터 시작하여 아래로 내려오면서 왼쪽 하위 트리를 방문하고 오른쪽 하위 트리를 방문 

 

 - 전위 순회를 이용하면 이진트리를 중첩된 괄호로 표현 가능

  -> 뿌리부터 시작해서 방문하는 노드의 깊이가 깊어질 때마다 괄호를 한 겹씩 두르면 

   (A(B(C,D)).(E,(F,G)))

 

중위 순회(Inorder Traversal)

 - 왼쪽 하위 트리부터 시작해서 뿌리를 거쳐 오른쪽 하위 트리를 방문

 - 트리에서 가장 왼쪽의 '잎 노드'부터 시작 

 - 잎 노드에서부터 시작된 순회는 부모 노드를 방문한 후 자신의 형제 노드를 방문하는 것으로 이어짐 

 - 최소 단위의 하위 트리 순회가 끝나면 그 위 단계 하위 트리에 대해 순회를 이어나감 

 

 - 중위 순회로 노드에 담긴 값을 출력하면 중위 표기식이 나옴

  ex) (1*2)+(7-8)

 

후위 순회 (Postorder Traversal)

 

- 왼쪽 하위 트리 방문하고 오른쪽 하위 트리를 방문한 다음 뿌리 노드를 방문함

- 이 순서는 하위 트리의 하위 트리, 또 그 하위 트리의 하위 트리에 대해 똑같이 적용 

 

- 후위 순회로 노드에 담긴 값을 출력하면 후위 표기식이 출력

 ex) 1 2 * 7 8 - +

 

4.2.3 이진 트리의 기본 연산 

 

1) 노드 선언 

 

이진 트리 노드 구조체 

 - 왼쪽 자식을 가리키는 Left 필드, 오른쪽 자식을 가리키는 Right 필드, 데이터를 담는 Data 필드 

typedef struct tagSBTNode
{
	struct tagSBTNode* Left;
	struct tagSBTNode* Right;

	ElementType Data;
}SBTNode;

 

2) 노드 생성 / 소멸 연산 

 

노드 생성  함수 SBT_CreateNode 

 

- malloc() 함수로 힙에 SBTNode 구조체의 크기만큼 메모리 공간을 할당하고, 이렇게 할당한 메모리 공간을 NewNode 포인터에 저장 

- Left 필드와 Right 필드를 NULL로 초기화 하고 Data 필드에 매개 변수로 입력받은 NewData를 저장 

- 함수의 마지막 라인에서는 생성한 노드의 포인터를 반환 

//노드 생성 
SBTNode* SBT_CreateNode(ElementType NewData)
{
	SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode));
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Data = NewNode;

	return NewNode;
}

 

노드 소멸 함수  SBT_DestroyNode

 

- free() 함수를 이용하여 노드가 할당되어 있던 공간을 할당 해제 

//노드 소멸
void SBT_DestroyNode(SBTNode* Node)
{
	free(Node);
}

 

3) 전위 순회를 응용한 이진 트리 출력

 

전위 순회 함수 SBT_PreorderPrintTree

 - 뿌리노드 -> 왼쪽 하위 트리 ->오른쪽 하위 트리 

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

	//뿌리 노드 출력 
	printf("%c", Node->Data);

	//왼쪽 하위 트리 출력
	SBT_PreorderPrintTree(Node->Left);

	//오른쪽 하위 트리 출력
	SBT_PreorderPrintTree(Node->Right);
}

 

4) 중위 순회를 응용한 이진 트리 출력

 

중위 순회 함수 SBT_InorderPrintTree

 - 왼쪽 하위 트리->뿌리 노드 -> 오른쪽 하위 트리 

//중위 순회 
void SBT_InorderPrintTree(SBTNode* Node)
{
	if (Node == NULL)
		return;

	//왼쪽 하위 트리 출력
	SBT_InorderPrintTree(Node->Left);

	//뿌리 노드 출력
	printf(" %c", Node->Data);

	//오른쪽 하위 트리 출력
	SBT_InorderPrintTree(Node->Right);
}

 

5) 후위 순회를 응용한 이진 트리 출력 

 

후위 순회 함수 SBT_PostorderPrintTree

 - 왼쪽 하위 트리 -> 오른쪽 하위 트리 -> 뿌리 노드 

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

	//왼쪽 하위 트리 출력
	SBT_PostorderPrintTree(Node->Left);

	//오른쪽 하위 트리 출력
	SBT_PostorderPrintTree(Node->Right);

	//뿌리 노드 출력
	printf("%c", Node->Data);
}

 

6) 후위 순회를 응용한 트리 소멸 

 

트리 소멸 함수 SBT_DestroyTree

 

- 트리를 파괴할 때는 반드시 잎 노드부터 힙에서 제거해야 함

- 잎 노드부터 방문하여 뿌리 노드까지 거슬러 올라가며 방문하는 후위 순회를 이용

//트리 소멸
void SBT_DestroyTree(SBTNode* Node)
{
	if (Node == NULL)
		return;
	
	//왼쪽 하위 트리 소멸
	SBT_DestroyTree(Node->Left);

	//오른쪽 하위 트리 소멸
	SBT_DestroyTree(Node->Right);

	//뿌리 노드 소멸 
	SBT_DestroyNode(Node);
}

 

4.2.4 이진 트리 예제 프로그램

 

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

typedef char ElementType;

typedef struct tagSBTNode
{
	struct tagSBTNode* Left;
	struct tagSBTNode* Right;

	ElementType Data;
}SBTNode;

//노드 생성 
SBTNode* SBT_CreateNode(ElementType NewData)
{
	SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode));
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Data = NewNode;

	return NewNode;
}

//노드 소멸
void SBT_DestroyNode(SBTNode* Node)
{
	free(Node);
}

//트리 소멸
void SBT_DestroyTree(SBTNode* Node)
{
	if (Node == NULL)
		return;
	
	//왼쪽 하위 트리 소멸
	SBT_DestroyTree(Node->Left);

	//오른쪽 하위 트리 소멸
	SBT_DestroyTree(Node->Right);

	//뿌리 노드 소멸 
	SBT_DestroyNode(Node);
}

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

	//뿌리 노드 출력 
	printf(" %c", Node->Data);

	//왼쪽 하위 트리 출력
	SBT_PreorderPrintTree(Node->Left);

	//오른쪽 하위 트리 출력
	SBT_PreorderPrintTree(Node->Right);
}

//중위 순회 
void SBT_InorderPrintTree(SBTNode* Node)
{
	if (Node == NULL)
		return;

	//왼쪽 하위 트리 출력
	SBT_InorderPrintTree(Node->Left);

	//뿌리 노드 출력
	printf(" %c", Node->Data);

	//오른쪽 하위 트리 출력
	SBT_InorderPrintTree(Node->Right);
}

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

	//왼쪽 하위 트리 출력
	SBT_PostorderPrintTree(Node->Left);

	//오른쪽 하위 트리 출력
	SBT_PostorderPrintTree(Node->Right);

	//뿌리 노드 출력
	printf(" %c", Node->Data);
}

int main()
{
	//노드 생성
	SBTNode* A = SBT_CreateNode('A');
	SBTNode* B = SBT_CreateNode('B');
	SBTNode* C = SBT_CreateNode('C');
	SBTNode* D = SBT_CreateNode('D');
	SBTNode* E = SBT_CreateNode('E');
	SBTNode* F = SBT_CreateNode('F');
	SBTNode* G = SBT_CreateNode('G');

	//트리에 노드 추가 
	A->Left = B;
	B->Left = C;
	B->Right = D;

	A->Right = E;
	E->Left = F;
	E->Right = G;

	//트리 출력
	printf("Preorder...\n");
	SBT_PreorderPrintTree(A);
	printf("\n\n");
	printf("Inorder...\n");
	SBT_InorderPrintTree(A);
	printf("\n\n");
	printf("Postorder...\n");
	SBT_PostorderPrintTree(A);
	printf("\n\n");

	//트리 소멸
	SBT_DestroyTree(A);

	return 0;

}