Chapter 08. 이진 트리의 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이제 이진 트리를 직접 구현해 볼 차례입니다. 그런데 이진 트리는 재귀적인 특성을 지니고 있습니다. 이런 재귀적인 특성 때문에 이진 트리와 관련된 일부 연산은 재귀 호출의 형태를 띱니다. 따라서 여러분은 재귀적인 사고에, 그리고 재귀 함수의 정의에 어느 정도 익숙한 상태여야 합니다.

---

이진 트리 역시 배열 기반으로도, 그리고 연결 리스트를 기반으로도 구현이 가능합니다. 하지만 트리를 표현하기에는 연결 리스트가 더 유연하기 때문에 앞으로 대부분의 트리는 연결 리스트를 기반으로 구현하게 됩니다.

 

하지만 이진 트리라면, 특히 매우 빈번한 탐색이 이루어질 완전 이진 트리라면 배열을 기반으로 한 구현도 고려해 볼만 합니다. 배열은 분명 연결 리스트에 비해서 탐색이 매우 용이하고 빠르기 때문입니다. 따라서 완전 이진 트리의 구조를 가지는 '힙'이라고 하는 자료구조는 배열을 기반으로 구현합니다.

---

이진 트리를 구현하기에 앞서 이진 트리의 ADT를 먼저 정의하겠습니다.

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);
//오른쪽 서브 트리를 연결한다.

이진 트리의 경우 노드 하나만 있어도 그 자식으로 공집합 노드가 2개 달리기 때문에, 노드 그 자체가 서브 트리가 될 수 있습니다. 따라서 필요할 때마다 노드(서브 트리)를 생성하고, 생성한 노드(서브 트리)를 다른 노드의 오른쪽 혹은 왼쪽에 연결함으로써 트리를 만들어 나갑니다.

 

위 ADT를 바탕으로 이진 트리의 헤더 파일을 구현해 보겠습니다.

//BinaryTree.h 헤더 파일로 저장
#ifndef BINARYTREE_H
#define BINARYTREE_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);

#endif

뭔가 어색할지도 모릅니다. 노드는 정의되어 있는데, 이진 트리를 표현하는 구조체는 정의되어 있지 않습니다. 지금까지 리스트, 스택, 큐, 덱의 경우에는 노드도 정의되고, 각각 리스트, 스택, 큐, 덱을 나타내는 구조체도 정의되어 있었습니다. 하지만 앞서 말했다시피 트리에서는 노드가 곧 트리이기 때문에 노드만 구조체로 정의되어 있습니다.

 

이제 위 헤더 파일을 기반으로 각각의 함수들을 구현해 보겠습니다.

그런데 그전에, 위 ADT와 헤더 파일에는 나와 있지 않지만 제가 필요하다고 생각되어 직접 정의한 함수를 하나 소개하겠습니다. 이 함수는 아직 책에는 나와 있지 않습니다.

void DeleteSubTree(BTreeNode* bt);
//인자로 전달받은 노드와 그 후손 노드들을 모두 삭제한다.

위 함수까지 포함하여 헤더 파일과 소스 파일을 모두 보이겠습니다.

//BinaryTree.h 헤더 파일로 저장
#ifndef BINARYTREE_H
#define BINARYTREE_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 DeleteSubTree(BTreeNode* bt);    //ADT에는 정의되지 않은 함수, 직접 구현

#endif

//BinaryTree.c 소스 파일로 저장
#include "BinaryTree.h"
#include <stdlib.h>
#include <stdio.h>

BTreeNode* MakeBTreeNode(void)
{
	BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}
	newNode->left = NULL;
	newNode->right = NULL;

	return newNode;
}

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)
	{
		DeleteSubTree(main->left);
	}
	main->left = sub;
}

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

//입력받은 노드와 그 후손 노드들을 모두 삭제하는 함수, 직접 구현
void DeleteSubTree(BTreeNode* bt)
{
	if (bt->right != NULL)
	{
		DeleteSubTree(bt->right);
	}
	
	if (bt->left != NULL)
	{
		DeleteSubTree(bt->left);
	}

	printf("%d를 삭제합니다.", bt->data);
	free(bt);
}

트리의 구현은 비교적 간단했습니다. 주의할 것은 노드의 삭제 부분입니다. 트리를 구성하는 노드들은 동적 할당되기 때문에 동적 할당된 공간을 잘 회수해야 합니다. MakeLeftSubTree 함수나 MakeRightSubTree 함수는 입력받은 노드에 자식 노드를 연결합니다. 만약 왼쪽에 자식 노드를 추가하고 싶은데 그 자리에 이미 다른 노드가 있다면 그 노드를 삭제하고 자식 노드를 추가합니다.

 

따라서 다음의 그림에서,

A노드를 인자로 주고 MakeLeftSubTree 함수를 호출하게 되면 해당 자리에는 B노드가 있기 때문에 B노드를 삭제하고 해당 자리에 자식 노드를 추가할 것입니다. 그런데 이때 B노드를 삭제해버리면 그의 후손 노드인 D와 E 노드에는 더 이상 접근할 수가 없게 됩니다. D와 E노드도 동적으로 할당된 노드이기 때문에 나중에는 메모리 공간을 반환시켜주어야 하고, 그러기 위해서 해당 노드에 접근할 수 있어야 합니다. 하지만 B노드가 삭제되어 더 이상 접근할 수 없게 되므로 프로그램이 끝나기까지 D노드와 E노드가 할당된 메모리 공간을 절대 사용할 수가 없게 되는 것입니다.

 

이러한 문제를 예방하기 위해 B노드를 삭제할 때는 그의 후손 노드인 D와 E까지 같이 삭제해주어야 합니다. 따라서 노드를 삭제하는 함수는 재귀적으로 정의되어 후손 노드들을 모두 삭제하고 마지막으로 B노드를 삭제하게 됩니다. 

 

구현이 끝난 트리를 테스트하기 위해 main 함수를 정의하고, 실행결과를 보도록 하겠습니다.

//main.c 소스 파일로 저장
#include "BinaryTree.h"
#include <stdio.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);     //bt4를 bt2의 왼쪽 자식 노드로

	//bt1의 왼쪽 자식 노드의 데이터 출력
	printf("%d\n", GetData(GetLeftSubTree(bt1)));

	//bt1의 왼쪽 자식 노드의 왼쪽 자식 노드의 데이터 출력
	printf("%d\n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

	DeleteSubTree(bt1);    //트리의 모든 노드를 삭제, 직접 구현

	return 0;
}

/*
실행결과

2
4
3를 삭제합니다.
4를 삭제합니다.
2를 삭제합니다.
1를 삭제합니다.

*/

트리의 모든 노드를 삭제할 때는 루트 노드를 인자로 주어 DeleteSubTree 함수를 호출합니다.