이진 트리 구현

두개의 포스트에 걸쳐서 이진 트리를 설명했으니 드디어 구현에 들어가볼 차례입니다.

---

1. 배열로 이진 트리 구현하기?

트리도 배열을 이용해서 구현할 수는 있습니다.

그림처럼 노드에 번호를 부여하고 배열의 인덱스와 노드 번호를 일치시켜 데이터를 저장하죠. 다시 말하자면 배열의 크기를 (노드의 수+1) 만큼 잡고 인덱스 0번을 제외한 나머지 번호를 이용해서 구현합니다. 하지만 크기 가변이 힘들고, 위와 같은 그림의 완전 이진 트리가 아닌경우에, 비는 인덱스가 생긴다는 등의 문제로 인해서 일반적으로 트리를 배열로 구현하지는 않습니다. 물론 이진 트리 마지막에 소개드릴 '히프'라는 자료구조가 있는데, 이 구조에서 배열을 이용하게 됩니다.

 

 

2. 연결 리스트로 이진 트리 구현하기

노드 특히 양방향 노드를 이용하면 이진 트리를 쉽게 이해하고 구현할 수 있습니다.

그림을 보니 연결 리스트로 구현하는게 이해하기 편하다는 것이 느껴지시나요?

 

2-1. 노드 구조

노드 구조는 양방향 연결 리스트처럼 왼쪽/오른쪽 링크 필드가 있는 구조입니다. 이때 왼쪽 링크필드는 왼쪽 자식 노드를 오른쪽 링크 필드는 오른쪽 자식 노드와 연결됩니다. 그렇다면, 이전 노드로 돌아가는 것은 하지 않냐는 의문이 생길텐데, 트리는 한 번 검사할 자료를 돌아가서 다시 찾을 일은 없기 때문에 이전 부모 노드와의 연결은 따로 필요하지 않습니다. 그리고 이 부분에 대해서는 다음 포스트에서 '트리의 순회'라는 개념으로 다시 다룰 예정입니다.

 

typedef int element;

typedef struct BinaryTreeNode {
	struct BinaryTreeNode* leftNode;
	element data;
	struct BinaryTreeNode* rightNode;
}binaryTreeNode;

binaryTreeNode* createBinaryTree(void) {
	binaryTreeNode* BT;

	BT = (binaryTreeNode*)malloc(sizeof(binaryTreeNode));
	BT->leftNode = NULL;
	BT->rightNode = NULL;

	return BT;
}

위의 그림대로 노드 구조를 정의하고, 빈 트리를 만드는 과정입니다. 그동안 만들었던 구조와 똑같으니 추가적인 설명을 필요없으리라 예상됩니다.

 

2-2. 서브 트리 삽입하기

다음은 서브 트리를 삽입하는 과정입니다. 이진 트리이므로 왼쪽과 오른쪽 삽입 과정이 있습니다.

void makeLeftSubTree(binaryTreeNode* current, binaryTreeNode* sub) {
	if (current->leftNode != NULL) {
		free(current->leftNode);
	}

	current->leftNode = sub;
}

void makeRightSubTree(binaryTreeNode* current, binaryTreeNode* sub) {
	if (current->rightNode != NULL) {
		free(current->rightNode);
	}

	current->rightNode = sub;
}

현재 노드에서 왼쪽/오른쪽에 서브 트리를 삽입할 뿐입니다. 그러나 if문을 주목해보면, 이미 트리가 존재하는 경우에는 이미 있는 노드를 삭제하고 삽입을 진행합니다. 이때 삭제하는 서브 트리의 자식노드가 없다면 문제가 없지만, 서브 트리가 자식 노드를 가지고 있는 경우 그 노드에 대해서는 free 함수가 먹히지 않아서 메모리를 잡아먹게 됩니다. 이 경우를 해결하기 위해서는 삭제 대상 트리 밑의 모든 노드에 방문해서 free함수를 호출할 필요가 있는데, 이 과정을 '순회'라는 방식으로 해결하게 됩니다. 순회에 대해서는 다음 포스트에서 다루도록 하고 지금은 그렇구나 하고 개요를 알아두시면 좋습니다.

 

2-3. 데이터 설정, 가져오기 / 트리 가져오기

이 부분은 간단합니다.

void setData(binaryTreeNode* BT, element elem) {
	BT->data = elem;
}

element getData(binaryTreeNode* BT) {
	return BT->data;
}

binaryTreeNode* getLeftSubTree(binaryTreeNode* BT) {
	return BT->leftNode;
}

binaryTreeNode* getRightSubTree(binaryTreeNode* BT) {
	return BT->rightNode;
}

데이터 삽입(setData)은 인수로 전달한 노드의 데이터를 설정하는 과정입니다.

데이터 가져오기(getData)는 인수로 전달한 노드의 데이터를 가져옵니다.

get~SubTree메소드는 인수로 전달한 노드의 왼쪽 혹은 오른쪽 노드를 가져오는 메소드입니다.

---

만들고 보니 이진 트리 구조는 구성이 되지만 삽입 삭제 연산에서 순회라는 기능이 필요해 보입니다. 순회 기능이 갖춰줘야 이진 트리가 완성되었다고 할 수 있습니다. 따라서 다음 포스트에서 순회 기능을 더한 이진 트리를 완성해보겠습니다.