[자료구조 강좌]


나무와 유사한 계층적 구조!

트리(Tree)



오늘 배우게 될 트리(Tree)란 자료구조는 나무와 유사하게 계층적 구조를 띄고 있는 자료구조입니다. 트리 그대로죠. 나무에 뿌리와 가지, 잎이 있듯 트리라는 자료구조에서도 나무와 뿌리 그리고 가지가 존재합니다. 여기서 뿌리 노드는 루트 노드라 하고, 가지와 잎은 그대로 가지 노드, 잎 노드와 같이 부릅니다. 트리가 응용되는 분야에는 무엇이 있을까요? 트리의 주된 목적은 탐색이며, 의사 결정, 파일 시스템(디렉터리 구조), 검색 엔진, DBMS, 라우터 알고리즘, 계층적 데이터를 다루는 등 매우 다양한 곳에서 응용이 되고 있습니다. 전에 배운 자료구조와 트리가 다른게 있다면, 리스트와 스택, 큐는 모두 선형 구조를 띄고 있다면 이 트리는 계층 구조(즉, 비선형 구조)를 띈다는 특징을 뽑을 수 있겠습니다. 한번 그림으로 직접 보도록 할까요?


<트리(Tree)의 계층적 구조>


위 그림을 보니, 무언가 나무처럼 쭉 뻗어나오는것 같지 않나요? 여기에선 위로 뻗어나가는 모양이 아니라, 아래로 뻗어가는 모양이지만요. 여기서는 A가 뿌리, 즉 루트 노드입니다. 그리고 B,D,E,C,F,G는 가지 노드, 가지에서 나온 I,J,K,L 노드는 잎 노드(단말 노드라고도 불립니다)입니다. 나무가 아닌 인간 관계로 보자면, A의 자식 노드는 B와 C, B와 C의 부모 노드는 A 그리고 B의 자식 노드는 D, E, D와 E의 부모 노드는 B.. 등을 예로 들 수 있습니다. 여기선 유일하게 루트 노드인 A만 부모가 없습니다.


그리고 차수(degree), 높이(height), 레벨(level)에 대해 알아보도록 하겠습니다. 여기서 차수란 어떤 노드가 가지고 있는 자식 노드의 수를 말합니다. 예를 들어 B 노드의 차수는 2, C 노드의 차수는 2, A 노드의 차수는 2 이렇게 되는 것입니다. (트리의 차수를 말할때는, 트리에서 가장 높은 차수를 말합니다) 그리고 레벨(level)이란, 트리의 각 층의 번호라고 말할 수 있습니다. 여기서는 레벨 1은 A, 레벨 2는 B, C 그리고 레벨 3은 D,E,F,G를 가리킵니다. 마지막으로 높이(height)는 트리의 루트 노드부터 시작하여 맨 끝에있는 잎 노드까지의 깊이(여기서 깊이란 루트 노드에서 해당 노드까지 경로의 길이를 말합니다.)를 말합니다. 위의 트리에선 깊이가 3이라고 볼수 있겠네요. (ABDI, ABEJ, ACFK, ACGL 모두 루트부터 시작하여 잎까지의 경로의 길이가 3)


 1. Left Child-Right Sibling 표현법  왼쪽은 자식 노드, 오른쪽은 형제 노드!


트리를 구현하기 전, 노드를 표현하기 위해 Left Child-Right Sibling란 표현법을 택하도록 합시다. 여기서 왼쪽 자식-오른쪽 형제(Left Child-Right Sibling) 표현법이란 아래 그림처럼 한 개의 노드에는 자식과 형제의 포인터를 지니고 있는 구조입니다.


<여기서 Child란 자식 노드, Sibling이란 형제 노드(같은 레벨에 있는 노드)>


위의 그림을 보시면 맨 위에있는 노드부터 시작해서 왼쪽에 위치한 자식 노드를 구함->그 노드의 자식 노드를 구하고 옆에 있는 형제 노드를 구함->형제 노드의 자식 노드를 구함->구한 자식 노드의 형제 노드를 구함.. 이런식으로 모든 자식 노드를 찾을 수 있습니다.


우선 직접 코드를 보아가며 이해를 하도록 합시다. 이번에도 이 Left Child-Right Sibling 표현법에서의 Tree 클래스를 구현해보도록 합시다. 제일 먼저 생성자와 속성을 먼저 보도록 합시다.

class Tree
{
private:
	char Data; // 데이터 필드
	Tree* LeftChild; // 왼쪽 자식노드를 가리키는 포인터
	Tree* RightSibling; // 오른쪽 형제노드를 가리키는 포인터
public:
	Tree() { } // 디폴트 생성자
	Tree(char Data) // 넘겨받은 인자로 Data를 초기화시킴
	{
		LeftChild = NULL; // 왼쪽 자식노드를 가리키는 포인터 초기화
		RightSibling = NULL; // 오른쪽 형제노드를 가리키는 포인터 초기화
		this->Data = Data; // 데이터 대입
	}
..

트리 클래스 내에는 데이터(Data)와 왼쪽 자식노드(Left Child)를 가리키는 포인터, 그리고 오른쪽 형제 노드를 가리키는 포인터(Right Sibling)이 있습니다. 그리고 Data를 넘겨받는 Tree 생성자를 보시면, 왼쪽 자식노드와 오른쪽 자식노드를 가리키는 포인터를 NULL로 지정합니다. 그러고 나서 넘겨받은 Data를 자신의 Data에 대입합니다. 다음으로 노드에 자식 노드를 추가하는 함수를 보도록 합시다.

..
	void appendChildNode(Tree* Child) // 노드에 자식 노드를 추가하는 함수
	{
		// 자식 노드가 없으면 넘겨받은 노드를 자식노드로 지정한다
		if (LeftChild==NULL) LeftChild = Child; 
		else { // 자식 노드가 존재할 경우에는
			Tree* temp = LeftChild; // 왼쪽에 있는 자식 노드의 주소값을 임시 포인터에 넣어둔다
			while (temp->RightSibling != NULL) // 오른쪽 형제 노드의 주소값이 NULL일때까지 반복한다
				temp = temp->RightSibling; // temp에 오른쪽 형제 노드의 주소값을 대입한다
			temp->RightSibling = Child; // 마지막 형제 노드 포인터에 Child의 주소값을 대입한다
		}
	}
..

이 appendChildNode는 노드의 주소값을 넘겨 받습니다. 이 노드의 주소값을 받고 자식 노드로 만들어 나가는 과정입니다. 우선, 현재 노드의 자식 노드가 없으면 넘겨받은 노드를 자식 노드로 지정합니다. 반대로, 자식 노드가 존재할 경우에는 임시로 자식 노드의 주소값을 포인터 변수에 대입한 뒤에, 오른쪽 형제 노드가 NULL일때까지 반복합니다. 즉, 비어있는 형제 노드를 구하는 겁니다. 이렇게 구해진 비어있는 형제 노드의 자리에 넘겨받은 자식 노드의 주소값을 대입합니다. 마지막으로 printTree 함수를 보도록 합시다.

..
	void printTree(int Depth) // 트리를 출력하는 함수
	{
		// 깊이 수 만큼 공백을 출력한다
		for(int i=0; i<Depth; i++)
			cout<<" ";
		// 데이터를 출력한다
		cout<<Data<<endl;

		// 재귀 함수, 왼쪽 자식 노드의 데이터를 출력하기 위해 printTree 호출(깊이는 현재 깊이의 1을 더함, 자식 노드이기 때문)
		if(LeftChild != NULL) LeftChild->printTree(Depth+1);
		// 재귀 함수, 오른쪽 형제 노드의 데이터를 출력하기 위해 printTree 호출(깊이는 그냥 넘겨줌, 형제 노드라 깊이가 같음)
		if(RightSibling != NULL) RightSibling->printTree(Depth);
	}
..

위의 printTree 함수는 깊이를 가지고 그 수만큼 공백을 출력합니다. 그 후엔 데이터를 출력합니다. 그리고 나서는 왼쪽 자식 노드가 비어있는지 확인하고, 비어있지 않을 경우에 왼쪽 자식노드의 printTree 메서드를 호출합니다. (왼쪽 자식 노드의 형제 노드, 자식 노드를 출력하기 위해서) 이때 자식 노드이므로 현재 깊이값에서 1을 더한 값을 넘겨줍니다. 그리고 그 다음엔, 형제 노드가 비어있는지 확인합니다. 비어있지 않을 경우엔 형제 노드의 printTree 메서드를 호출합니다. (오른쪽 형제 노드의 형제 노드, 자식 노드를 출력하기 위해서) 이때 형제 노드이므로 깊이가 같으니 그대로 넘겨줍니다. 이해 되시나요? 그럼 전체 코드와 결과를 보도록 합시다.


예>

#include <iostream>
using namespace std;

class Tree
{
private:
	char Data; // 데이터 필드
	Tree* LeftChild; // 왼쪽 자식노드를 가리키는 포인터
	Tree* RightSibling; // 오른쪽 형제노드를 가리키는 포인터
public:
	Tree() { } // 디폴트 생성자
	Tree(char Data) // 넘겨받은 인자로 Data를 초기화시킴
	{
		LeftChild = NULL; // 왼쪽 자식노드를 가리키는 포인터 초기화
		RightSibling = NULL; // 오른쪽 형제노드를 가리키는 포인터 초기화
		this->Data = Data; // 데이터 대입
	}
	void appendChildNode(Tree* Child) // 노드에 자식 노드를 추가하는 함수
	{
		// 자식 노드가 없으면 넘겨받은 노드를 자식노드로 지정한다
		if (LeftChild==NULL) LeftChild = Child; 
		else { // 자식 노드가 존재할 경우에는
			Tree* temp = LeftChild; // 왼쪽에 있는 자식 노드의 주소값을 임시 포인터에 넣어둔다
			while (temp->RightSibling != NULL) // 오른쪽 형제 노드의 주소값이 NULL일때까지 반복한다
				temp = temp->RightSibling; // temp에 오른쪽 형제 노드의 주소값을 대입한다
			temp->RightSibling = Child; // 마지막 형제 노드 포인터에 Child의 주소값을 대입한다
		}
	}
	void printTree(int Depth) // 트리를 출력하는 함수
	{
		// 깊이 수 만큼 공백을 출력한다
		for(int i=0; i<Depth; i++)
			cout<<" ";
		// 데이터를 출력한다
		cout<<Data<<endl;

		// 재귀 함수, 왼쪽 자식 노드의 데이터를 출력하기 위해 printTree 호출(깊이는 현재 깊이의 1을 더함, 자식 노드이기 때문)
		if(LeftChild != NULL) LeftChild->printTree(Depth+1);
		// 재귀 함수, 오른쪽 형제 노드의 데이터를 출력하기 위해 printTree 호출(깊이는 그냥 넘겨줌, 형제 노드라 깊이가 같음)
		if(RightSibling != NULL) RightSibling->printTree(Depth);
	}
};

int main()
{
	// 루트 노드를 비롯한 다른 노드를 생성한다
	Tree Root('A'), B('B'), C('C'), D('D'), E('E'), F('F');

	// 루트 노드에 노드 B를 자식으로 추가한다
	Root.appendChildNode(&B);
	// B 노드에 노드 C를 자식으로 추가한다
	B.appendChildNode(&C);
	// B 노드에 노드 D를 자식으로 추가한다
	B.appendChildNode(&D);
	// 루트 노드에 노드 E를 자식으로 추가한다. (루트 노드의 자식은 B, E)
	Root.appendChildNode(&E);
	// E 노드에 노드 F를 자식으로 추가한다
	E.appendChildNode(&F);

	// 루트 노드부터 시작하여 트리 내에 노드의 데이터들을 출력한다
	Root.printTree(0);
}

결과:

A
 B
  C
  D
 E
  F
계속하려면 아무 키나 누르십시오 . . .


메인 함수부터 살펴보자면 노드가 Root, A, B, C, D, E, F가 생성되고 각 노드에 자식 노드를 추가합니다. (여기서 클래스가 Node가 아닌 Tree인 이유는 단원이 Tree라 그렇습니다. 간단하죠?) 차례대로 살펴보면, 루트 노드의 자식 노드에 B노드가 추가되고, B 노드의 자식 노드에 C와 D가 추가됩니다. 그 후에는 다시 루트 노드의 자식 노드에 E가 추가되며, E 노드에는 F 노드가 자식 노드로 추가됩니다. 마지막으로는 트리 내에 노드의 데이터를 모두 출력합니다. 트리란 자료구조에 대해 대충 감이 잡히셨나요? 위에서 배운 왼쪽 자식-오른쪽 형제 표현법은 맛보기였고, 이번엔 본격적으로 트리에 들어가보려고 합니다.


 2. 이진 트리(Binary Tree)  최대 2개의 자식 노드를 갖는다!


혹시 이진 트리(Binary Tree)라고 해서 들어보신적이 있으신가요? 이진 트리에서의 노드는 최대 2개의 자식 노드를 가질수 있습니다. 최대 2개의 자식 노드를 가질수 있다는건, 한 노드당 1개의 노드를 가질수도 있고, 2개의 노드를 가질수가 있다는 말입니다. 그리고 자식 노드가 아에 없을수도 있죠. 마치 잎 노드처럼 말이죠. 이 2진 트리에는 여러가지의 형태가 존재합니다. 완전 이진 트리(Complete Binary Tree)와 사향 이진 트리(Skewed Binary Tree), 포화 이진 트리(Full Binary Tree)에 대해서 우선 알아보도록 합시다. 먼저 완전 이진 트리입니다.

<완전 이진 트리(Complete Binary Tree)>

위에 보시는 트리의 형태가 완전 이진 트리입니다. 완전 이진 트리는 어떤 잎 노드 두개의 레벨차가 1 이하이며, 왼쪽부터 오른쪽으로 채워지는 그런 트리입니다. 만약, 왼쪽에서 오른쪽으로 가다가 어떤 잎 노드와 다른 잎 노드 사이에 노드가 하나라도 비어있으면 그건 완전 이진 트리가 아닙니다. 다음은 사향 이진 트리입니다.

<사향 이진 트리(Skewed Binary Tree)>

이 사향 이진 트리의 특징은 루트 노드를 제외한 모든 노드가 부모 노드의 왼쪽 자식 노드이거나 혹은 오른쪽 자식 노드인 것을 말합니다. 즉, 노드의 방향이 한쪽 방향으로만 치우쳐 있습니다. 그게 이 사향 이진 트리의 특징입니다. 다른 말로 경사, 편향 이진 트리라고 불리기도 합니다. 다음은 포화 이진 트리입니다.

<포화 이진 트리(Full Binary Tree)>

이 포화 이진 트리는 완전 이진 트리와는 다르게 최대한 노드가 가득차있는 트리를 말합니다. 모든 노드가 자식 노드를 2개나 가지고 있습니다. 말 그대로 포화 상태인 셈이죠. 정리하자면, 잎 노드를 제외한 모든 노드의 차수가 2인 트리라고 할까요? (모든 포화 이진 트리는 완전 이진 트리입니다. 반대로 역은 성립할 수 없습니다.)


이진 트리의 상태를 이제 분류하실 수 있겠죠? 여태까지 이진 트리의 형태에 대해 알아봤다면, 이번엔 이진 트리의 순회 방법에 대해 알아보도록 합시다. 이진 트리의 순회 방법에는 전위 운행법, 중위 운행법, 후위 운행법이 있습니다. (레벨 운행법도 있지만 이건 설명에서 제외하도록 하겠습니다.) 먼저 전위 운행법입니다.

<전위 운행법/순회(Preorder Traversal) (A-B-D-H-I-E-C-F-G)>


위의 그림은 전위 순회(Preorder Traversal) 입니다. 루트 노드를 시작으로 아래로 내려오며 좌측 하위 트리를 먼저 방문하고, 방문이 끝나면 우측 하위 트리를 방문합니다. 위 그림에서는, 루트 노드인 A부터 시작하여 내려오며, 좌측 하위 트리를 먼저 방문하기 때문에 B 노드를 먼저 방문합니다. 그 다음에 D 노드를 방문하고, H 노드를 방문합니다. 그다음에 I 노드와 E 노드를 방문하는 것입니다. 그 후에는 좌측 하위 트리는 모두 방문을 끝냈으므로, 우측 하위 트리로 이동합니다. C 노드를 방문하고 나서, 좌측에 있는 F 노드를, 그리고 우측에 있는 G 노드를 들립니다. 이번엔 중위 운행법을 살펴보도록 할까요?

<중위 운행법/순회(Inorder Traversal) (H-D-I-B-E-A-F-C-G)>


전위 운행법보다는 조금 복잡해보이죠? 이 중위 운행법은 좌측 하위 트리부터 시작하여 루트 노드를 거치고 우측 하위 트리를 방문합니다. 위 그림에서는, 좌측 하위 트리부터 시작한다고 했으므로 H 노드부터 시작하여 D 노드를 거친 다음에 I 노드를 거칩니다. 그 다음에 B 노드를 거치고, E 노드를 거칩니다. 그 후에 루트 노드를 거치고 나서 우측 하위 트리를 방문합니다. 여기서도 주의하실건 가장 좌측의 노드먼저 방문한다는 것입니다. 이 때문에, F 노드를 거치고, C 노드를 거친다음에 G 노드를 거치는 것입니다. 마지막으로 후위 운행법입니다.

<후위 운행법/순회(Postorder Traversal) (H-I-D-E-B-F-G-C-A)>


이 후위 운행법은 마지막에 루트 노드를 방문한다는 것이 특징입니다. 좌측 하위 트리부터 시작하여 우측 하위 트리를 거치고 마지막으로 루트 노드를 거칩니다. 위 그림에선, 좌측 하위 트리(최하위 좌측 노드 부터 시작)부터 시작합니다. H 노드부터 시작해서, I 노드를 거치고 D 노드를 거칩니다. 그 다음에 E 노드를 거치고, B 노드를 거치면 좌측 하위 트리는 모두 방문을 끝냈죠? 그러면 우측 하위 트리를 거칩니다. F 노드를 거치고, 그다음 G 노드, C 노드 다음에 마지막으로 루트 노드인 A 노드를 방문하는 겁니다. 이제 슬슬, 이진 트리를 구현해보도록 합시다. 이번에는 Node 클래스와 Tree 클래스로 구성됩니다. 우선 Node 클래스의 필드와 생성자부터 살펴보도록 합시다.

class Node {
private:
	char Data; // 데이터 필드
	Node* Left; // 왼쪽 자식 노드를 가리키는 포인터
	Node* Right; // 오른쪽 자식 노드를 가리키는 포인터
public:
	// 생성자, 문자를 넘겨받고 Data에 대입하고 왼쪽, 오른쪽 자식 노드를 가리키는 포인터를 초기화
	Node(char Data) { this->Data = Data; Left = NULL; Right = NULL; }
..

필드에는 좌측, 우측 자식 노드를 가리키는 포인터와 데이터로 구성되어 있습니다. 그리고 생성자는 문자를 넘겨받고, 넘겨받은 문자로 Data 필드를 초기화 하는 것입니다. 좌측, 우측 자식 노드를 가리키는 포인터의 초기화와 함께 말이죠. 다음에는 좌측/우측 자식 노드를 지정하는 것과, 데이터를 가져오는 메서드, 그리고 좌측/우측 자식 노드의 주소값을 반환하는 함수를 보도록 합시다.

..
	// 왼쪽 자식 노드를 지정함
	void setLeft(Node* Left) { this->Left = Left; }
	// 오른쪽 자식 노드를 지정함
	void setRight(Node* Right) { this->Right = Right; }
	// 데이터를 반환함
	char getData() { return Data; }
	// 왼쪽 자식 노드의 주소값을 반환함
	Node* getLeft() { return Left; }
	// 오른쪽 자식 노드의 주소값을 반환함
	Node* getRight() { return Right; }
..

의외로 노드의 메서드에는 큰 비중을 차지하고 있는 메서드가 없습니다. 위의 주석으로 충분히 이해하실거라 믿고, 트리 클래스의 생성자와 필드를 보도록 합시다.

..
class Tree {
private:
	Node* root; // 루트 노드를 가리키는 포인터
public:
	// 디폴트 생성자, 루트 노드를 가리키는 포인터 초기화
	Tree() { root = NULL; }
	// 생성자, 노드의 주소값을 넘겨받고 그 주소값으로 root를 초기화
	Tree(Node* root) { this->root = root; }
..

트리 클래스의 필드에는 루트 노드를 가리키는 포인터로 구성되어 있고, 그 아랫 부분에는 디폴트 생성자와 인자를 넘겨받는 생성자가 존재합니다. 하나는 root를 NULL로 초기화, 다른 하나는 넘겨받은 노드의 주소를 root로 지정하는 겁니다. 바로 전위 순회를 응용한 출력 메서드를 보도록 합시다.

..
	void PreorderPrint(Node* Leaf)
	{
		if (Leaf == NULL) return; // 넘겨받은 Leaf의 주소값이 NULL이면 return
		cout << Leaf->getData() << " "; // 넘겨받은 Leaf의 데이터를 출력한다, 루트 노드
		PreorderPrint(Leaf->getLeft()); // 재귀 호출, 넘겨받은 노드의 왼쪽 자식 노드의 주소값을 넘긴다, 왼쪽 하위 트리
		PreorderPrint(Leaf->getRight()); // 재귀 호출, 넘겨받은 노드의 오른쪽 자식 노드의 주소값을 넘긴다, 오른쪽 하위 트리
	}
..

위 메서드는 전위 순회를 응용한 출력 메서드입니다. 노드의 주소값을 넘겨받고, 이 노드가 아무것도 가리키지 않고 있으면 return 합니다. 만약 아니면 계속 실행되어, 루트 노드의 데이터를 출력하고 왼쪽 하위 트리를 출력하기 위해, 넘겨받은 노드의 주소값을 전달합니다. 그러곤 다시 돌아와 오른쪽 자식 노드의 주소값을 전달합니다. 나머지, 후위 순회, 중위 순회를 응용한 출력 메서드도 이와 비슷합니다. 다만 순서가 바뀌어 있을 뿐이죠. 같이 보도록 합시다.

..
	void InorderPrint(Node* Leaf)
	{
		if (Leaf == NULL) return; // 넘겨받은 Leaf의 주소값이 NULL이면 return
		InorderPrint(Leaf->getLeft()); // 재귀 호출, 넘겨받은 노드의 왼쪽 자식 노드의 주소값을 넘긴다, 왼쪽 하위 트리
		cout << Leaf->getData() << " "; // 넘겨받은 Leaf의 데이터를 출력한다, 루트 노드
		InorderPrint(Leaf->getRight()); // 재귀 호출, 넘겨받은 노드의 오른쪽 자식 노드의 주소값을 넘긴다, 오른쪽 하위 트리
	}
	void PostorderPrint(Node* Leaf)
	{
		if (Leaf == NULL) return; // 넘겨받은 Leaf의 주소값이 NULL이면 return
		PostorderPrint(Leaf->getLeft()); // 재귀 호출, 넘겨받은 노드의 왼쪽 자식 노드의 주소값을 넘긴다, 왼쪽 하위 트리
		PostorderPrint(Leaf->getRight()); // 재귀 호출, 넘겨받은 노드의 오른쪽 자식 노드의 주소값을 넘긴다, 오른쪽 하위 트리
		cout << Leaf->getData() << " "; // 넘겨받은 Leaf의 데이터를 출력한다, 루트 노드
	}
..

전위 순회를 응용한 출력 메서드의 순서가 루트 노드 -> 왼쪽 하위 트리 -> 오른쪽 하위 트리였다면, 중위 순회(Inorder Traversal)는 왼쪽 하위 트리 -> 루트 노드 -> 오른쪽 하위 트리의 순서를 지니고 있습니다. 그 아래에 있는 후위 순회(Postorder Traversal)는 왼쪽 하위 트리 -> 오른쪽 하위 트리 -> 루트 노드의 순서를 지니고 있죠. 이해가 가시나요? 그럼, 전체적인 코드를 살펴보고 결과까지 같이 봐보도록 합시다.


예>

#include <iostream>
using namespace std;

class Node {
private:
	char Data; // 데이터 필드
	Node* Left; // 왼쪽 자식 노드를 가리키는 포인터
	Node* Right; // 오른쪽 자식 노드를 가리키는 포인터
public:
	// 생성자, 문자를 넘겨받고 Data에 대입하고 왼쪽, 오른쪽 자식 노드를 가리키는 포인터를 초기화
	Node(char Data) { this->Data = Data; Left = NULL; Right = NULL; }
	// 왼쪽 자식 노드를 지정함
	void setLeft(Node* Left) { this->Left = Left; }
	// 오른쪽 자식 노드를 지정함
	void setRight(Node* Right) { this->Right = Right; }
	// 데이터를 반환함
	char getData() { return Data; }
	// 왼쪽 자식 노드의 주소값을 반환함
	Node* getLeft() { return Left; }
	// 오른쪽 자식 노드의 주소값을 반환함
	Node* getRight() { return Right; }
};

class Tree {
private:
	Node* root; // 루트 노드를 가리키는 포인터
public:
	// 디폴트 생성자, 루트 노드를 가리키는 포인터 초기화
	Tree() { root = NULL; }
	// 생성자, 노드의 주소값을 넘겨받고 그 주소값으로 root를 초기화
	Tree(Node* root) { this->root = root; }
	// 새로운 루트 노드를 지정함
	void newRoot(Node* root) { this->root = root; }
	void PreorderPrint(Node* Leaf)
	{
		if (Leaf == NULL) return; // 넘겨받은 Leaf의 주소값이 NULL이면 return
		cout << Leaf->getData() << " "; // 넘겨받은 Leaf의 데이터를 출력한다, 루트 노드
		PreorderPrint(Leaf->getLeft()); // 재귀 호출, 넘겨받은 노드의 왼쪽 자식 노드의 주소값을 넘긴다, 왼쪽 하위 트리
		PreorderPrint(Leaf->getRight()); // 재귀 호출, 넘겨받은 노드의 오른쪽 자식 노드의 주소값을 넘긴다, 오른쪽 하위 트리
	}
	void InorderPrint(Node* Leaf)
	{
		if (Leaf == NULL) return; // 넘겨받은 Leaf의 주소값이 NULL이면 return
		InorderPrint(Leaf->getLeft()); // 재귀 호출, 넘겨받은 노드의 왼쪽 자식 노드의 주소값을 넘긴다, 왼쪽 하위 트리
		cout << Leaf->getData() << " "; // 넘겨받은 Leaf의 데이터를 출력한다, 루트 노드
		InorderPrint(Leaf->getRight()); // 재귀 호출, 넘겨받은 노드의 오른쪽 자식 노드의 주소값을 넘긴다, 오른쪽 하위 트리
	}
	void PostorderPrint(Node* Leaf)
	{
		if (Leaf == NULL) return; // 넘겨받은 Leaf의 주소값이 NULL이면 return
		PostorderPrint(Leaf->getLeft()); // 재귀 호출, 넘겨받은 노드의 왼쪽 자식 노드의 주소값을 넘긴다, 왼쪽 하위 트리
		PostorderPrint(Leaf->getRight()); // 재귀 호출, 넘겨받은 노드의 오른쪽 자식 노드의 주소값을 넘긴다, 오른쪽 하위 트리
		cout << Leaf->getData() << " "; // 넘겨받은 Leaf의 데이터를 출력한다, 루트 노드
	}
};

int main()
{
	// 각 노드를 생성한다 (A, B, C, D, E, F, G, H, I)
	Node A('A'), B('B'), C('C'), D('D'), E('E'), F('F'), G('G'), H('H'), I('I');
	Tree tree(&A); // 트리 객체 생성, A의 주소값을 생성자로 넘긴다. (A가 루트 노드)

	A.setLeft(&B); // A의 왼쪽 자식 노드는 B 노드
	B.setLeft(&D); // B의 왼쪽 자식 노드는 D 노드
	D.setLeft(&H); // D의 왼쪽 자식 노드는 H 노드
	D.setRight(&I); // D의 오른쪽 자식 노드는 I 노드
	B.setRight(&E); // B의 오른쪽 자식 노드는 E 노드
	A.setRight(&C); // A의 오른쪽 자식 노드는 C 노드
	C.setLeft(&F); // C의 왼쪽 자식 노드는 F 노드
	C.setRight(&G); // C의 오른쪽 자식 노드는 G 노드

	cout << "전위 순회(Preorder Traversal): " << endl;
	tree.PreorderPrint(&A); // 전위 순회

	cout << endl << "중위 순회(Inorder Traversal): " << endl;
	tree.InorderPrint(&A); // 중위 순회

	cout << endl << "후위 순회(Postorder Traversal): " << endl;
	tree.PostorderPrint(&A); // 후위 순회
	cout << endl;
}

결과:

전위 순회(Preorder Traversal):
A B D H I E C F G
중위 순회(Inorder Traversal):
H D I B E A F C G
후위 순회(Postorder Traversal):
H I D E B F G C A
계속하려면 아무 키나 누르십시오 . . .


메인 함수부터 살펴보시면 처음부터 A, B, C, D, E, F, G, H, I 노드가 생성되었죠. 그리고 나서 트리 클래스를 기반으로 한 객체를 만들때 생성자에 A의 주소값을 같이 넘겨주었습니다. 이제부터 A가 트리의 루트 노드인 셈이죠. 그 다음에 각 노드마다 오른쪽, 왼쪽 자식 노드를 추가했는데 이는 위의 전위, 중위, 후위 순회에 사용하였던 노드의 구조와 동일하니 그 그림을 참고하시면 되겠습니다. (전위, 중위, 후위 순회의 순서가 궁금하시면 다시 위의 글을 보시면 됩니다) 이 이진 트리는 데이터베이스 뿐만 아니라, 검색 엔진에도, 그리고 자료를 탐색, 정렬하는 데이터 처리에 많이 이용되고 있습니다. 생각해보고 좀 지나면 이진 트리에 대해 강좌를 쓸 예정입니다. 모두 수고하셨습니다.

저작자표시 비영리 변경금지

'알고리즘, 자료구조' 카테고리의 다른 글

알고리즘 2-2강. 탐색 알고리즘 - 이진 탐색(Binary Search)  (11) 2013.05.25
알고리즘 2-1강. 탐색 알고리즘 - 순차 탐색(Sequential Search)  (2) 2013.05.23
자료구조 3강. 큐(Queue)  (4) 2013.01.15
자료구조 2강. 스택(Stack)  (8) 2013.01.09
자료구조 1강. 리스트(List)  (20) 2013.01.01

티스토리툴바