8. 트리(Tree)

1. 트리의 개요

 

트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다

 

 

 

 

 ※ 트리는 단순한 데이터의 저장을 넘어서 데이터의 표현을 위한 도구이다

 

▣ 트리 관련 용어

 

트리

 

∙ 노드
node 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소

∙ 간선 (edge)
노드와 노드를 연결하는 연결선

∙ 루트 노드 (root node )
트리 구조에서 최상위에 존재하는 A와 같은 노드

∙ 단말 노드 (terminal node)
 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드

∙ 내부 노드 (internal node)
 단말 노드를 제외한 모든 노드로 A, B와 같은 노드

 

 

▣ 트리의 노드간 관계

 

 

∙  노드 A는 노드 B, C, D의 부모 노드(parent node)이다.

∙ 노드 B, C, D는 노드 A의 자식 노드(child node)이다.

∙ 노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 형제 노드(sibling node)이다.

▣ 서브 트리의 이해

 

루트의 서브트리

 

하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리켜 서브 트리라 한다

 

왼쪽 서브의 서브트리

 

서브 트리 역시 또 다른 서브 트리를 갖는다

 

서브 트리 역시 서브 트리로 이뤄져 있으며, 
그 서브 트리 역시 또 다른 서브 트리로 이뤄져 있다. 

이렇듯 트리는 그 구조가 재귀적이다!

 

---

▣ 이진 트리의 이해

 

▶ 이진 트리의 조건
∙ 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
∙ 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.

이상적인 이진트리

트리 그리고 이진 트리는 그 구조가 재귀적이다.
따라서 트리와 관련된 연산은 재귀적으로 사고하고 재귀적으로 구현할 필요가 있다

 

▣ 이진 트리와 공집합 노드

 

공집합1

 

공집합2

 

 

공집합(empty set)도 이진 트리에서는 노드로 간주한다!

하나의 노드에 두 개의 노드가 달리는 형태의 트리는 모두 이진 트리이다

 

▣ 레벨과 높이, 그리고 포화, 완전 이진 트리

 

트리의 높이 레벨

트리의 높이와 레벨의 최대 값은 같다

 

 

포화 이진 트리  

모든 레벨에 노드가 꽉 찬 
포화 이진 트리

 

 

 

빈 틈 없이 차곡차곡 채워진
완전 이진 트리

 

 

※ 완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 의미한다. 

따라서 포화 이진 트리는 동시에 완전 이진 트리이지만 그 역은 성립하지 않는다.

---

2. 이진 트리의 구현

 

 

▣  이진 트리 구현의 두 가지 방법

 

배열 기반

 

∙ 노드에 번호를 부여하고 그 번호에 해당하는 값을 배열의 인덱스 값으로 활용한다.  
∙ 편의상 배열의 첫 번째 요소는 사용하지 않는다.

 

연결리스트 기반

 

∙ 연결 리스트 기반에서는 트리의 구조와 리 스트의 연결 구조가 일치한다. 
∙ 따라서 구현과 관련된 직관적인 이해가 더 좋은 편이다. 

 

▣ ADT

 

 

이진 트리의 모든 노드는 직/간접적으로 연결되어 있다.  
따라서 루트 노드의 주소 값만 기억하면, 이진 트리 전체 를 가리키는 것과 다름이 없다.

 

논리적으로도 하나의 노드는 그 자체로 이진 트리이다. 
따라서 노드를 표현한 구조체는 실 제로 이진 트리를 표현한 구조체가 된다.

 

//노드 생성
BTreeNode* MakeBTreeNode()
{
	BTreeNode* ne = new BTreeNode();
	ne->left = NULL;
	ne->right = NULL;
	return ne;
}

BTData GetData(BTreeNode* bt)
{
	bt->data;
}

//노드에 데이터를 저장
void SetData(BTreeNode* bt, BTData data)
{
	bt->data = data;
}

//왼쪽 서브트리의 주소값 반환
BTreeNode* GetLeftSubTree(BTreeNode* bt)
{
	return bt->left;
}

//오른쪽 서브트리의 주소값 반환
BTreeNode* GetRightSubTree(BTreeNode* bt)
{
	return bt->right;
}

//main 왼쫀 서브트리로 sub 연결
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub)
{
	if (main->left != NULL)
		delete main->left;

	main->left = sub;
}

//main 오른쪽 서브트리로 sub 연결
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
	if (main->right != NULL)
		delete main->right;

	main->right = sub;
}

 

int main()
{
	BTreeNode * ndA = MakeBTreeNode();       
	BTreeNode * ndB = MakeBTreeNode();     
	BTreeNode * ndC = MakeBTreeNode();    


	MakeLeftSubTree(ndA, ndB); 

	MakeRightSubTree(ndA, ndC); 

	return 0;
}

 

1차원 이진트리 채워진 결과

 

int main()
{
	BTreeNode * bt1 = MakeBTreeNode();       
	BTreeNode * bt2 = MakeBTreeNode();       
	BTreeNode * bt3 = MakeBTreeNode();       
	BTreeNode * bt4 = MakeBTreeNode();


	SetData(bt1, 1);
	SetData(bt2, 2);
	SetData(bt3, 3);
	SetData(bt4, 4);


	MakeLeftSubTree(bt1, bt2); 
	MakeRightSubTree(bt1, bt3); 
	MakeLeftSubTree(bt2, bt4);

	return 0;
}

 

main 함수에서 생성하는 트리

 

---

3. 이진 트리의 순회(Traversal)

 

 

기준은 루트 노드를 언제 방문하느냐에 있다

루트 노드를 방문하는 시점에 따라서 중위, 후위, 전위 순회로 나뉘어 진다.

 

 

중위 순회

 

후위 순회

 

전위 순회

 

 

▣ 순회의 재귀적 표현

 

이진 트리의 중위 순회

 

탈출 조건이 명시되지 않은 불완전한 구현

 

▣ 순회의 재귀적 표현 완성

void InorderTraverse(BTreeNode* bt)
{
	if (bt == NULL)		//NULL 이면 재귀 탈출
    return;

	InorderTraverse(bt->left);
	cout <<  bt->data << "\n";
	InorderTraverse(bt->right);
}

 

 

 

노드가 단말 노드인 경우, 단말 노드의 자식 노드는 NULL이다!

 

int main()
{
	BTreeNode * bt1 = MakeBTreeNode();       
	BTreeNode * bt2 = MakeBTreeNode();       
	BTreeNode * bt3 = MakeBTreeNode();       
	BTreeNode * bt4 = MakeBTreeNode();


	SetData(bt1, 1);
	SetData(bt2, 2);
	SetData(bt3, 3);
	SetData(bt4, 4);


	MakeLeftSubTree(bt1, bt2); 
	MakeRightSubTree(bt1, bt3); 
	MakeLeftSubTree(bt2, bt4);


	InorderTraverse(bt1); //재귀 적트로 트리를 순회하면서, 값을 출력

	return 0;
}

 

 

▣ 준위 순회와 후위 순회

중위순회

void InorderTraverse(BTreeNode* bt)
{
	if (bt == NULL)		return;

	InorderTraverse(bt->left);
	cout <<  bt->data << "\n"; // 중위순회
	InorderTraverse(bt->right);
}

 

 

전위 순회

void InorderTraverse(BTreeNode* bt)
{
	if (bt == NULL)		return;

	cout << bt->data << "\n"; //전위순회
	InorderTraverse(bt->left);
	InorderTraverse(bt->right);
}

 

 

후위 순회

void InorderTraverse(BTreeNode* bt)
{
	if (bt == NULL)		return;

	InorderTraverse(bt->left);
	InorderTraverse(bt->right);
	cout << bt->data << "\n";   //후위 순회
}

 

 

▣ 노드의 방문 이유! 자유롭게 구성하기

 

함수포인터를 이용하여, 추가 함수 기능 구현

 

//함수 포인터 형 VisitFuncPtr의 정의
typedef void VisitFuncPtr(BTData data);

//Funcptr이 가리키는 함수를 통해서 방문을 진행
void InorderTraverse(BTreeNode* bt, VisitFuncPtr Funcptr)
{
	if (bt == NULL)		return;

	InorderTraverse(bt->left, Funcptr);
	Funcptr(bt->data);
	InorderTraverse(bt->right, Funcptr);
}

//VisitFuncPtr형을 기준으로 정의된 함수
void ShowData(int data)
{
	cout << data << " \n";
}


int main()
{
	BTreeNode * bt1 = MakeBTreeNode();       
	BTreeNode * bt2 = MakeBTreeNode();       
	BTreeNode * bt3 = MakeBTreeNode();       
	BTreeNode * bt4 = MakeBTreeNode();

	SetData(bt1, 1);
	SetData(bt2, 2);
	SetData(bt3, 3);
	SetData(bt4, 4);

	MakeLeftSubTree(bt1, bt2); 
	MakeRightSubTree(bt1, bt3); 
	MakeLeftSubTree(bt2, bt4);

	//InorderTraverse(bt1);
	InorderTraverse(bt1,ShowData);

	return 0;
}