트리(Tree)

1. 트리의 개요

이번에 설명하는 '트리'는 고급 자료구조로 구분이 된다.

때문에 그만큼 학습에 있어서 집중을 요한다.

특히 앞서 소개한 선형 자료구조들과 달리 트리는 비선형 자료구조이기 때문에 많이 다르게 느껴질 수 있다.

---

트리의 설명을 위해서 다음 내용을 먼저 말하고자 한다.

그만큼 이는 중요한 내용이다.

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

위의 문장에서 '계층적 관계'가 제일 눈에 띌 것이다.

그런데 이에 못지않게 관심을 둬야 할 단어가 바로 '표현'이다.

'자료구조'라고 하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인 것으로 이해하는 경우가 많다.

앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 있었으니 무리도 아니다.

하지만 자료구조는 근본적으로 무엇인가를 '표현'하는 도구이다.

표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다.

이런 이야기를 하는 이유는, 이러한 사실을 알지 못하면 이후에 접하게 되는 트리의 ADT를 이해하지 못하기 때문이다.

이번에 소개하는 트리는 데이터의 저장과 삭제가 아닌 '표현'에 초점이 맞춰져 있다.

때문에 이후에 소개하는 트리의 ADT를 다음과 같이 바라보면 안 된다.

"데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있나요?"

대신 다음과 같이 바라보아야 한다.

"트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나요?"

어떠한 차이가 있는지 알겠는가?

우리는 트리를 구현한 다음에 이를 기반으로 무엇인가를 표현해 볼 것이다.

앞서 리스트, 스택, 큐를 기반으로 정수를 저장했다가 이를 순서대로 꺼내서 출력하는 등의 예제는 이번 챕터에서 만들지 않을 것이다.

---

그렇다면 트리는 무엇을 표현하기 위한 자료구조일까?

사실 트리도 큐 못지않게 우리 주변에서 쉽게 접할 수 있는 자료구조이다.

컴퓨터의 디렉터리 구조도 트리의 예가 되고, 집안의 족보나 기업 및 정부의 조직도도 트리의 예가 된다.

위 그림은 언뜻 보면 나무처럼 보이지 않는다.

그럼에도 불구하고 트리 구조라 하는 이유는 나무와 위 그림 사이에 다음의 공통점이 있기 때문이다.

"가지를 늘려가며 뻗어나간다."

하늘로 뻗느냐 땅으로 뻗느냐는 중요치 않다.

중요한 것은 가지를 늘려가며 뻗어간다는 사실이다.

위 유형의 트리를 가리켜 '의사 결정 트리' 영어로는 'decision tree'라 한다.

그리고 위 트리의 내용은 다양한 데이터 분석 기법의 유용한 도구가 되며, 경영학 등 공학 이외의 영역에서도 유용하게 사용되는 도구이다.

"그럼 이번에 공부하는 트리는 이런 것을 표현하기 위한 것인가요?"

그렇다! 트리를 이용해서 무엇인가를 저장하고 꺼내야 한다는 생각을 지우자.

대신 무엇인가를 표현하는 도구라고 생각하자.

이것이 트리를 제대로 공부하는데 필요한 올바른 사고이다.

---

트리와 관련해서 제법 많은 용어가 정의되어 있다.

그리고 이러한 용어들도 한 차례 정리할 필요가 있다.

따라서 다음 그림을 대상으로 트리 관련 용어를 정리해 보겠다.

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

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

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

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

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

참고로 '단말 노드'는 나무의 구조상 잎에 해당한다 하여 '잎사귀 노드(leaf node)'라고도 불리며, '내부 노드'는 단말 노드가 아니라 하여 '비단말 노드(nonterminal node)'라고도 불린다.

그리고 노드간에는 부모(parent), 자식(child), 형제(sibling)의 관계가 성립이 되어 다음과 같이 표현할 수 있다.

참고로 트리 구조상 위에 있을수록 촌수가 높다.

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

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

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

그런데 부모와 자식의 관계는 상대적이다.

따라서 노드 B는 노드 A의 자식 노드이지만, 동시에 노드 E와 F의 부모 노드도 된다.

조금 더 나아가서 조상(Ancestor), 후손(Descendant)의 관계도 있다.

특정 노드의 위에 위치한 모든 노드를 가리켜 '조상 노드'라 하고, 특정 노드의 아래에 위치한 모든 노드를 가리켜 '후손 노드'라 한다.

즉 노드 A와 B는 노드 E의 조상 노드이다.

반면 노드 B, C, D, E, F는 모두 노드 A의 후손 노드이다.

---

다음 그림을 보자.

이 그림에서 보이듯이 큰 트리는 작은 트리로 구성이 된다.

그리고 이렇듯 큰 트리에 속하는 작은 트리를 가리켜 '서브 트리(sub tree)'라 한다.

다음 그림은 위 그림에서 왼쪽의 B를 루트 노드로 하는 서브 트리를 그린 것인데, 이 그림에서 보이듯이 서브 트리의 아래에는 더 작은 서브 트리가 존재한다.

이로써 서브 트리가 무엇을 의미하는지, 그리고 트리와 서브 트리와의 관계가 어떻게 되는지 이해하였을 것이다.

그럼 이러한 이해를 바탕으로 다음 트리를 보자.

위 그림에서 보이는 트리는 우리가 중점을 두어 공부하고 구현할 '이진 트리(Binary Tree)'이다.

"이진 트리라는 것이 자식 노드가 두 개씩 달린 트리인가요?"

완전하지는 않지만 간단하게 설명하면 그렇다!

그럼 구체적으로 이진 트리에 대해서 살펴보자.

우선 이진 트리는 다음 두 조건을 만족해야 한다.

- 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

- 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.

이 두 조건 중에서 두 번째 조건을 보면서 다음과 같이 생각하는 사람이 있을 수 있다.

"이진 트리의 조건을 정의하는데 있어서 이진 트리라는 단어를 등장시키다니!"

"이거 정의가 조금 이상한데요?"

하지만 이는 온전한 정의이다.

이진 트리의 조건 자체가 재귀적이기 때문에 이렇게 정의할 수밖에 없는 것이다.

그럼 이진 트리의 조건을 조금 쉽게 설명해 보겠다.

물론 이는 재귀적인 조건을 완전히 담아내지 못한 부족한 설명이다.

"이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리이어야 하고,

그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다."

이로써 이진 트리가 되기 위한 기본조건을 이해하였을 것이다.

그런데 이진 트리의 조건이 여기까지라면, 다음 트리는 이진 트리로 볼 수 없다.

모든 서브 트리가 이진 트리로 보이지 않기 때문이다.

하지만 이것도 이진 트리가 맞다.

왜냐하면 이진 트리와 관련해서 다음의 내용이 추가로 정의되어 있기 때문이다.

"노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다!"

"물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다!"

이진 트리에서 말하는 공집합 노드, 간단히 공집합이라 불리는 것을 그림에서 보이면 다음과 같다.

그리고 이 그림은 위의 트리가 이진 트리가 되는 이유도 함께 설명하고 있다.

이러한 공집합 노드 덕분에 위 그림에서 서브 트리가 하나인 노드 B와 C도, 그리고 단말 노드인 D와 E도 모두 이진 트리가 된다.

때문에 위 그림의 트리도, 그리고 다음 그림에서 보이는 트리도 이진 트리가 될 수 있는 것이다.

생각보다 이진 트리의 폭이 넓음을 알 수 있다.

따라서 이진 트리도 그 특성에 따라서 보다 세분화된다.

---

이진 트리의 몇몇 분류를 소개하기에 앞서 트리 관련 용어인 '레벨(level)'과 '높이(height)'를 소개하겠다.

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 '레벨'이라 하고, 트리의 최고 레벨을 가리켜 '높이'라 한다.

위 그림에서 보이듯이 레벨이 0에서부터 시작하는 관계로 최고의 레벨과 높이가 일치하기 때문에, 최고의 레벨을 높이라 하는 것이다.

자! 그럼 먼저 '포화 이진 트리(full binary tree)'를 소개하겠다.

다음 그림의 이진 트리는 모든 레벨이 꽉 차 있다.

따라서 노드를 더 추가하려면 레벨을 늘려야 한다.

이렇듯 모든 레벨이 꽉 찬 이진 트리를 가리켜 ' 포화 이진 트리'라 한다.

그럼 위 그림의 포화 이진 트리에서 레벨을 하나 더 늘려서 먼저 H를, 그리고 이어서 I를 추가한 다음 이진 트리를 보자.

위의 트리를 가리켜 '완전 이진 트리(complete binary tree)'라 한다.

이는 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리를 뜻한다.

그리고 여기서 말하는 '차곡차곡 빈 틈 없이 노드가 채워진 상태'가 갖는 의미는 다음과 같다.

"노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워졌다!"

그럼 이해를 돕기 위해서 완전 이진 트리가 아닌, 차곡차곡 빈 틈 없이 노드를 채우지 못한 이진 트리를 간단히 보이겠다.

위의 트리도 이진 트리의 조건에는 부합한다.

하지만 레벨 2의 가장 왼쪽 위치에 노드가 존재하지 않는다.

즉 빈 틈이 있는 상태이다.

따라서 '이진 트리'이긴 하되 '완전 이진 트리'는 아닌 것이다.

이로써 트리에 대한 개념적인 설명을 마치고 구현에 들어가기로 하겠다.

---

2. 이진 트리의 구현

드디어 트리를 구현할 차례가 되었다.

따라서 트리를 대표하는 이진 트리를 구현할 것이다.

그런데 이진 트리는 재귀적인 특성을 지니고 있다.

이는 앞서 보인 이진 트리의 정의에서도 확인할 수 있었다.

이진 트리의 이러한 재귀적인 특성 때문에 이진 트리와 관련된 일부 연산은 재귀호출의 형태를 띈다.

따라서 이진 트리를 구현하기 전에 재귀적인 사고와 재귀함수의 정의에 어느 정도 익숙한 상태이어야 한다.

---

이진 트리 역시 배열 기반으로도, 그리고 연결 리스트를 기반으로도 구현이 가능하다.

그러나 트리를 표현하기에는 연결 리스트가 더 유연하기 때문에 우리가 구현할 대부분의 트리는 연결 리스트를 기반으로 구현할 것이다.

그러나 이진 트리라면, 특히 다음과 같은 특성을 갖는 완전 이진 트리라면 배열 기반의 구현도 고려해 볼만 하다.

"트리가 완성된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄진다."

배열은 분명 연결 리스트에 비해서 탐색이 매우 용이하고 또 빠르기 때문이다.

따라서 배열을 기반으로 이진 트리를 구성하는 방법을 간단히 소개하고, 이어서 모든 이야기의 초점을 연결 리스트 기반의 이진 트리에 맞추겠다.

그럼 먼저 다음 이진 트리를 보자.

위 그림의 핵심은 노드에 번호가 부여되어 있다는 점이다.

이렇듯 배열을 기반으로 이진 트리를 구현하려면 노드에 고유의 노드 번호를 부여해야 한다.

그렇다면 이 번호가 의미하는 것은 무엇일까?

이는 각 노드의 데이터가 저장되어야 할 배열의 인덱스 값을 의미한다.

그럼 이와 관련해서 다음 그림을 보자.

위 그림에서는 길이가 8인 배열을 선언하여, 노드 번호 1부터 5까지의 노드에 저장된 데이터를 배열에 저장한 결과를 보여준다.

그림에서 데이터가 저장되는 배열의 위치는 노드 번호를 기준으로 결정되었다.

"그럼 인덱스가 0인 배열의 요소는 사용하지 않나요?"

사용할 수도 있지만 사용하지 않는 편이 여러모로 구현에 편의를 가져다 주고, 또 실수할 확률도 낮춰주기 때문에 일반적으로 사용하지 않는다.

이로써 배열을 기반으로 하는 이진 트리의 구현이 어떻게 이뤄지는지 대략적인 이해를 갖췄을 것이다.

그럼 이번에는 연결 리스트 기반의 구현 방법을 소개하겠으니, 이와 관련해서 다음 그림을 보자.

그림을 보는 순간 연결 리스트 기반의 구현 방식이 바로 이해됬을 것이다.

이렇듯 이해가 쉬운 이유는, 연결 리스트를 기반으로 트리를 구현할 경우 연결 리스트의 구성 형태가 트리와 일치하기 때문이다.

"그럼 배열 기반의 트리는 별 의미가 없는 건가요? 신경 쓰지 않아도 되나요?"

그렇지 않다!

완전 이진 트리의 구조를 갖는 '힙(heap)'이라는 자료구조는 배열을 기반으로 구현한다.

힙이 요구하는 바를 만족시키기가 배열이 훨씬 용이하기 때문이다.

힙은 다음 챕터에서 소개하니 그때가서 자세한 이야기를 나누기로 하자.

---

우리는 지금까지 ADT를 정의한 다음에 이를 기반으로 헤더파일을 정의하였다.

그리고 그것이 옳은 순서이다.

하지만 이번에는 헤더파일을 먼저 정의하고 나서 ADT를 정의하려고 한다.

"ADT의 정의와 헤더파일의 정의를 바꿔서 진행하는 이유가 뭐죠?"

학습의 편의를 돕기 위한 것이다.

이번 경우에는 ADT를 먼저 보이면 여러분이 혼란스러워 할 요소가 몇 가지 있다.

그래서 아예 헤더파일을 제시한 다음에 이를 바탕으로 부연설명을 먼저 진행하려고 한다.

자! 그럼 이진 트리의 헤더파일을 보이겠다.

---

BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

/*** BTreeNode 관련 연산들 ****/
BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

#endif

그럼 헤더파일에 대한 이야기를 시작해보자.

다음은 위의 헤더파일에 정의되어 있는 구조체이다.

typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

이것이 헤더파일에 정의되어 있는 유일한 구조체이다.

따라서 앞서 리스트, 스택, 큐를 경험한 우리들은 위의 헤더파일을 보면서 다음과 같이 생각할 수 있다.

"연결 리스트를 기반으로 이진 트리를 구현하니, 노드를 표현한 구조체는 당연히 있어야지!"

"근데 왜 이진 트리를 표현한 구조체는 정의하지 않은 거지?"

앞서 리스트 기반의 큐를 구현할 때에는 노드를 표현한 구조체와 큐를 표현한 구조체를 각각 정의하였다.

큐 뿐만 아니라, 스택을 구현할 때에도 그랬다.

때문에 위와 같이 느끼는 것이 당연하다.

하지만 우리는 다음 사실을 알고 있다.

"노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다!"

"물론 공집합 노드도 이진 트리를 판단하는데 있어서 노드로 인정한다!"

즉 다음 그림에서 보이듯이, 자식 노드가 하나도 없는 노드도 그 자체로 이진 트리이다.

두 개의 공집합 노드를 자식 노드로 두고 있기 때문이다.

마찬가지로 구조체 BTreeNode는 노드를 표현함과 동시에 이진 트리를 표현한 결과가 된다!

따라서 구조체 포인터 변수의 이름은 다음과 같이 선언될 수도 있지만,

BTreeNode * node;

다음과 같이 포인터 변수의 이름에 tree가 들어가도 이상할 것이 없다.

BTreeNode * ptree;

무슨 의도로 말하는지가 이해되는가?

변수의 이름을 꼭 위와 같이 선언하겠다는 뜻이 아니다.

BTreeNode는 노드의 표현결과일 뿐만 아니라 이진 트리의 표현결과도 된다는 것을 말하려는 것이다.

---

이진 트리의 구현은 의외로 간단하다.

다만 중요한 것은 앞서 설명한 이진 트리의 재귀적인 성향을 이해하는 것이다.

그럼 헤더파일에 선언된 함수의 기능을 설명하겠다.

참고로 이 함수들이 이진 트리를 만드는 도구가 된다.

BTreeNode * MakeBTreeNode(void); // 노드의 생성
BTData GetData(BTreeNode * bt); // 노드에 저장된 데이터를 반환
void SetData(BTreeNode * bt, BTData data); // 노드에 데이터를 저장

위의 세 함수는 이름이 의미하듯이 노드의 생성, 데이터의 반환 및 저장에 대한 기능을 제공한다.

특히 노드의 생성을 담당하는 MakeBTreeNode 함수는, 호출되면 다음 형태의 노드를 동적 할당 및 초기화하여 그 주소 값을 반환한다.

위 그림에 표시된 물음표는 쓰레기 값을 의미한다.

즉 멤버 data를 대상으로는 별도의 초기화를 진행하지 않는다.

그러나 왼쪽 서브 트리, 그리고 오른쪽 서브 트리를 가리키기 위한 멤버 left와 right는 NULL로 초기화된다.

그럼 이어서 다음 두 함수를 보자.

BTreeNode * GetLeftSubTree(BTreeNode * bt); // 왼쪽 서브 트리 주소 값 반환
BTreeNode * GetRightSubTree(BTreeNode * bt); // 오른쪽 서브 트리 주소 값 반환

위의 두 함수는 각각 인자로 전달된 이진 트리의 왼쪽 서브 트리, 그리고 오른쪽 서브 트리의 루트 노드의 주소 값을 반환하는 함수들이다.

마지막으로 다음 두 함수를 보자.

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

위의 두 함수는 서브 트리의 연결을 담당한다.

첫 번째 함수는 매개변수 sub로 전달된 트리 또는 노드를, 매개변수 main으로 전달된 노드의 왼쪽 서브 트리로 연결한다.

마찬가지로 두 번째 함수는 매개변수 sub로 전달된 트리 또는 노드를, 매개변수 main으로 전달된 노드의 오른쪽 서브 트리로 연결 한다.

이렇듯 이 두 함수는 연결을 담당할 뿐, 노드나 트리의 생성을 담당하지는 않는다.

그럼 지금까지 소개한 함수의 이해를 확인하기 위해서 다음 질문에 답을 해보자.

"노드 A, B, C를 생성해서 A를 루트로 하고,

B와 C를 각각 A의 왼쪽, 그리고 오른쪽 자식 노드가 되도록 구성하려면 함수의 호출 흐름을 어떻게 가져가야 하는가?"

위의 문장에서 말하는 대로 이진 트리를 구성하기 위한 함수의 호출 흐름은 대략 다음과 같다.

int main(void)
{
	BTreeNode * ndA = MakeBTreeNode(); // 노드 A 생성 
	BTreeNode * ndB = MakeBTreeNode(); // 노드 B 생성 
	BTreeNode * ndC = MakeBTreeNode(); // 노드 C 생성
	...
	 
	MakeLeftSubTree(ndA, ndB); // 노드 A의 왼쪽 자식 노드로 노드 B 연결
	MakeRightSubTree(ndA, ndC); // 노드 A의 오른쪽 자식 노드로 노드 C 연결 
	...
}

그럼 다음으로 이진 트리의 ADT를 정의하겠다.

이미 모두 설명한 내용이니, 함수에 대한 소개는 간략히 해 두겠다.

---

이진 트리의 구현은 의외로 쉽다.

코드도 몇 줄 안 된다.

그래서 헤더파일에 정의된 구조체, 그리고 이진 트리의 재귀적인 특성을 강조한 것이다.

이것이 이해할 내용의 전부이기 때문이다.

그럼 이어서 코드를 제시하겠다.

---

BinaryTree.c

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

BTreeNode * MakeBTreeNode(void)
{
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

BTData GetData(BTreeNode * bt)
{
	return 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;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->left != NULL)
		free(main->left);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->right != NULL)
		free(main->right);

	main->right = sub;
}

그런데 이진 트리를 삭제, 즉 메모리를 해제하는 free 과정을 거치려면 어떻게 해야 될까?

노드가 단 한개라면 한 번의 free 함수호출로도 가능하겠지만, 삭제할 서브 트리가 여러 개라면 메모리의 누수로 이어진다.

둘 이상의 노드로 이뤄져 있는 서브 트리를 완전히 삭제하려면 서브 트리를 구성하는 모든 노드를 대상으로 free 함수를 호출해야 한다.

즉 모든 노드를 방문해야 하는 것이다.

이렇듯 모든 노드를 방문하는 것을 가리켜 '순회'라 하는데, 이진 트리의 순회는 연결 리스트의 순회와 달리 별도의 방법이 필요하다.

잠시 후에는 서브 트리를 전부 삭제하는데 필요한 '순회'의 방법을 설명할 것이다.

그럼 이진 트리 구성의 예를 보이는 다음 main 함수를 보자.

---

BinaryTreeMain.c

#include <stdio.h>
#include "BinaryTree.h"

int main(void)
{
	BTreeNode * bt1 = MakeBTreeNode(); // 노드 bt1 생성
	BTreeNode * bt2 = MakeBTreeNode(); // 노드 bt2 생성
	BTreeNode * bt3 = MakeBTreeNode(); // 노드 bt3 생성
	BTreeNode * bt4 = MakeBTreeNode(); // 노드 bt4 생성

	SetData(bt1, 1); // bt1에 1 저장
	SetData(bt2, 2); // bt2에 2 저장
	SetData(bt3, 3); // bt3에 3 저장
	SetData(bt4, 4); // bt4에 4 저장

	MakeLeftSubTree(bt1, bt2); // bt2를 bt1의 왼쪽 자식 노드로
	MakeRightSubTree(bt1, bt3); // bt3를 bt1의 오른쪽 자식 노드로
	MakeLeftSubTree(bt2, bt4); // bt4f를 bt2의 왼쪽 자식 노드로

	printf("%d \n",
		GetData(GetLeftSubTree(bt1)));
	printf("%d \n",
		GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

	return 0;
}

위 main 함수를 통해서 형성되는 이진 트리의 구조는 다음과 같다.

---

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

앞서 이진 트리의 순회가 필요한 이유를 설명하였으니, 바로 이어서 트리의 순회 방법을 설명하겠다.

참고로 순회의 방법 또한 재귀적이다.

---

이진 트리를 대상으로 하는 대표적인 순회의 세 가지 방법은 다음과 같다.

- 전위 순회(Preorder Traversal): 루트 노드를 먼저!

- 중위 순회(Inorder Traversal): 루트 노드를 중간에!

- 후위 순회(Postorder Traversal): 루트 노드를 마지막에!

이렇듯 이진 트리를 순회하는 대표적인 방법은 다음 내용을 기준으로 세 가지로 나뉜다!

"루트 노드를 언제 방문하느냐!"

다음과 같은 순서 및 방향으로 순회할 경우, 루트 노드는 중간에 방문이 이뤄지기 때문에 이러한 방식의 순회를 가리켜 '중위 순회'라 한다.

유사하게 다음과 같은 순서 및 방향으로 순회할 경우, 루트 노드는 마지막에 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 '후위 순회'라 한다.

끝으로 루트 노드를 먼저 방문하는 방식의 순회를 가리켜 '전위 순회'라 한다.

이렇듯 순회의 방법은 간단하다.

루트 노드와 이를 부모로 하는 두 자식 노드를 놓고, 한쪽 방향으로 순서대로 방문을 하면 된다.

"그럼 높이가 2 이상인 이진 트리는 어떻게 순회를 하나요?"

그림을 통해 보였듯이 높이가 1인 이진 트리의 순회는 어렵지 않다.

그런데 높이가 2 이상이 되면 조금 당황스럽다.

하지만 이진 트리는 그 구조가 재귀적이다.

따라서 우리가 지금 이야기한 세 가지 순회의 방법을 재귀적으로 구현만 하면 문제는 해결이 된다.

---

자! 그럼 중위 순회를 진행하는 함수를 정의해 볼 텐데, 이를 위해서 다음 그림을 관찰하자.

이 그림에서 보이는 이진 트리는 루트 노드를 기준으로 왼쪽과 오른쪽에 서브 트리가 존재하는 가장 일반적인 모델이다.

위 그림의 이진 트리를 대상으로 중위 순회를 할 경우 순회의 순서는 다음과 같다.

- 1단계: 왼쪽 서브 트리의 순회

- 2단계: 루트 노드의 방문

- 3단계: 오른쪽 서브 트리의 순회

여기서 문제는 1단계와 3단계이다.

어떠한 방법으로 서브 트리를 순회해야 하겠는가?

서브 트리라고 해서 순회의 방법이 달라지는 것은 아니다.

즉, 이들을 대상으로도 중위 순회를 진행하면 된다.

따라서 이진 트리 전체를 순회하는 함수는, 완전하지는 않지만 일단 다음과 같이 정의할 수 있다.

void InorderTraverse(BTreeNode * bt) // 이진 트리 전체를 중위 순회하는 함수
{
	InorderTraverse(bt->left); // 1단계: 왼쪽 서브 트리의 순회
	printf("%d \n", bt->data); // 2단계: 루트 노드의 방문
	InorderTraverse(bt->right); // 3단계: 오른쪽 서브 트리의 순회
}

그런데 이 함수에서도 다음 두 가지 의문을 제기할 수 있다.

"재귀의 탈출 조건이 정의되어 있지 않다!"

"데이터를 그저 출력만 하는게 노드의 방문이냐!"

노드의 저장된 데이터의 출력으로, 노드의 방문이 이뤄진 것으로 가정한 이유는, 순회의 방법에 초점을 두기 위한 것이니 우선은 재귀의 탈출 조건 구성에 집중을 하자.

그럼 이와 관련해서 다음 그림을 보자.

위 그림에서 루트 노드가 L인 왼쪽 서브 트리를 보자.

이 역시 이진 트리이니, 다음의 과정을 거쳐서 순회를 진행하게 된다.

- 1단계: 왼쪽 서브 트리의 순회(노드 N을 대상으로)

- 2단계: 루트 노드의 방문(노드 L을 대상으로)

- 3단계: 오른쪽 서브 트리의 순회(공집합 노드를 대상으로)

그리고 다시 한번 강조하지만 단말 노드도 이진 트리이다.

그래서 단말 노드를 대상으로도 순회를 진행한다.

그런데 위의 3단계에서 우리는 재귀의 탈출조건을 발견할 수 있다.

노드 L의 오른쪽 서브 트리가 NULL이므로 함수에 NULL이 전달되기 때문이다.

따라서 함수는 다음과 같이 정의되어야 한다.

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

	InorderTraverse(bt->left); 
	printf("%d \n", bt->data); 
	InorderTraverse(bt->right); 
}

이로써 중위 순회 함수를 완성하였으니, 앞서 구현한 예제 BinaryTreeMain.c에 이 함수를 추가하여 그 결과를 확인해보자.

---

BinaryTreeTraverseMain.c

#include <stdio.h>
#include "BinaryTree.h"

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

	InorderTraverse(bt->left); 
	printf("%d \n", bt->data); 
	InorderTraverse(bt->right); 
}

int main(void)
{
	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 PreorderTraverse(BTreeNode * bt) // 전위 순회 함수
{
	if(bt == NULL)
		return;

	printf("%d \n", bt->data); 
	PreorderTraverse(bt->left);
	PreorderTraverse(bt->right);
}

void PostorderTraverse(BTreeNode * bt) // 후위 순회 함수
{
	if(bt == NULL)
		return;

	PostorderTraverse(bt->left);
	PostorderTraverse(bt->right);
	printf("%d \n", bt->data);
}

위에서 보이듯이 중위, 전위, 후위 순회 함수의 유일한 차이점은 루트 노드를 방문하는 문장이 삽입된 위치이다.

---

노드의 방문목적은 데이터의 출력이 전부가 아니다!

방문의 목적은 상황에 따라 달라진다.

따라서 방문했을 때 할 일을 결정할 수 있도록, 앞서 정의한 세 개의 순회 함수를 변경하고자 한다.

"아! 함수 포인터를 사용할 생각이군요!"

앞서 함수 포인터를 활용한 바 있으니 이러한 판단을 내릴 수 있을 것이다.

그럼 먼저 중위 순회 함수를 변경해 보이겠다.

void InorderTraverse(BTreeNode * bt, void (*fptr)(int))
{
	if(bt==NULL)
		return;
		
	InorderTraverse(bt->left, fptr);
	fptr(bt->data);
	InorderTraverse(bt->right, fptr);
}

함수의 주소 값을 매개변수 fptr을 통해서 전달받도록 변경하였다.

그리고 이 함수를 기반으로 노드의 방문은 다음과 같이 처리되도록 변경하였다.

fptr(bt->data);

즉 매개변수 fptr에 전달되는 함수의 내용에 따라서 노드의 방문결과가 결정되는 것이다.

그럼 이와 관련해서 완성된 코드를 보이겠다.

---

BinaryTree2.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

// 순회 관련 함수
void PreorderTraverse(BTreeNode * bt, void (*fptr)(int));
void InorderTraverse(BTreeNode * bt, void (*fptr)(int));
void PostorderTraverse(BTreeNode * bt, void (*fptr)(int));

// 트리 전체 노드 삭제 함수
void DeleteTree(BTreeNode * bt);

#endif

이는 앞서 정의한 헤더파일 BinaryTree.h에 전위, 중위, 후위 순회 관련 함수의 선언과 트리 전체의 삭제를 위한 함수의 선언을 추가한 것이다.

마찬가지로 이어서 소개하는 소스파일도 BinaryTree.c에 순회 관련 함수와 트리 삭제 함수 정의를 추가한 것이다.

---

BinaryTree.c

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

BTreeNode * MakeBTreeNode(void)
{
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
	nd->left=NULL;
	nd->right=NULL;
	return nd;
}

BTData GetData(BTreeNode * bt)
{
	return 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;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->left!=NULL)
		free(main->left);
		
	main->left=sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->right!=NULL)
		free(main->right);
		
	main->right=sub;
}

void PreorderTraverse(BTreeNode * bt, void (*fptr)(int))
{
	if(bt==NULL)
		return;
		
	fptr(bt->data);
	PreorderTraverse(bt->left, fptr);
	PreorderTraverse(bt->right, fptr);
}

void InorderTraverse(BTreeNode * bt, void (*fptr)(int))
{
	if(bt==NULL)
		return;
		
	InorderTraverse(bt->left, fptr);
	fptr(bt->data);
	InorderTraverse(bt->right, fptr);
}

void PostorderTraverse(BTreeNode * bt, void (*fptr)(int))
{
	if(bt==NULL)
		return;
		
	PostorderTraverse(bt->left, fptr);
	PostorderTraverse(bt->right, fptr);
	fptr(bt->data);
}

void DeleteTree(BTreeNode * bt)
{
	if(bt==NULL)
		return;
	
	DeleteTree(bt->left);
	DeleteTree(bt->right);
	free(bt);
}

트리를 삭제하는 함수는 앞서 설명한 적이 없지만 어떤 구조와 방식으로 삭제가 이뤄지는지 대충 감이 올 것이다.

코드에서 보이듯이 트리 전체의 삭제를 위해서도 트리의 순회가 필요하다.

단! 루트 노드가 마지막에 소멸되어야 하기 때문에, 위의 함수에서 보이듯이 반드시 후위 순회의 과정을 통해서 소멸을 진행해야 한다.

트리 삭제 함수의 핵심은 바로 이것이다!

마지막으로 main 함수를 보이겠다.

그런데 순회 관련 함수의 두 번째 인자로 전달되어 노드 방문의 결과를 결정하는 함수는, 트리를 활용해서 프로그램을 구현하는 프로그래머의 몫이 되어야 한다.

그래서 그러한 의미를 반영하기 위해서, main 소스파일에 두 번째 인자로 전달되는 함수를 정의하였다.

---

BinaryTreeMain2.c

#include <stdio.h>
#include "BinaryTree.h"

void ShowIntData(int data);

int main(void)
{
	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);
	
	PreorderTraverse(bt1, ShowIntData);
	printf("\n");
	InorderTraverse(bt1, ShowIntData);
	printf("\n");
	PostorderTraverse(bt1, ShowIntData);
	printf("\n");
	
	DeleteTree(bt1);
	
	InorderTraverse(bt1, ShowIntData); // 아무것도 출력되지 않음
	printf("\n");

	return 0;
}

void ShowIntData(int data)
{
	printf("%d ", data);
}