트리 - 스레드 이진 트리

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다.

 

// 해당 단원인 '트리'의 목차가 업데이트 될 예정입니다.

이전 글: 트리 - 이진 트리의 노드 개수/ 단말 노드 개수/ 높이 구하기

 

스레드 이진 트리 Threaded Binary Tree

스레드 이진 트리가 무엇인지 알기 전에 왜 '스레드 이진트리'가 나오게 되었는지 먼저 생각해보자.

 

전위/중위/후위/레벨 순회 등 이진트리를 순회할 때 NULL 링크를 만나면 왼쪽 또는 오른쪽 자식 노드가 없음으로 이해해왔다. 즉 NULL 링크(또는 포인터) 는 자식노드의 유무를 알려주는 유일한 도구이다. 

 

그런데, 이러한 NULL 포인터가 이진트리 내에 몇 개가 존재하는지 따져본 적이 없다.

 

이진트리에 존재하는 노드가 n개라면, 노드 간의 부모-자식 관계를 표현하기 위한 포인터(또는 간선)는(은) 총 2n개 존재한다. 그 중에서 자식이 존재함을 알리는 포인터는 n-1 개, 그리고 자식이 없음을 표현하기 위한 NULL 포인터는 n+1개 존재한다.

 

의외로 NULL 포인터가 트리 내에서 차지하는 비중이 크다. 

 

그렇다면, 이 NULL 포인터를 좀 더 유의미하게 사용할 수 없을까? 하여 나온 아이디어가 이번 글에서 다뤄볼 '스레드 이진 트리'이다. 

 

이진 트리를 중위 순회할 때, 어느 순간의 특정 노드 기준 '지나쳐온' 또는 '지나갈' 노드를 의미하는 '중위 선행자' 또는 '중위 후속자'를 'NULL 포인터'가 가리키는 트리가 '스레드 이진 트리'이다.

 

단, 특정 노드의 포인터가 '자식을 가리키는 포인터'인지 'NULL이 저장되어야 했지만 중위선행자 또는 중위후속자가 저장된 포인터'이지 구별을 해야 한다. 이를 위한 태그 필드 is_thread를 노드 구조체에 추가해줌으로써 노드의 구조는 다음과 같다.

typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
	int is_thread;
} TreeNode;

※ 해당 글에서는 중위 후속자, 즉 '지나갈' 노드를 right 포인터가 가리킨다고 가정한다.

 

만약 is_thread가 1 또는 TRUE 이면 right 포인터는 중위 후속자를 가리키고, 반대로 0 또는 FALSE 이면 right 포인터는 자식을 가리키는 포인터이다. 

 

트리를 구성하는 노드의 구조가 변경되었으니, 트리를 순회하는 중위 순회 알고리즘도 다음과 같이 변경되어야 한다.

void thread_inorder(TreeNode* root)
{
	TreeNode* q;
	q = root;
	// 중위순회는 가장 왼쪽 노드부터 시작하니까 while문으로 가장 왼쪽 노드로 이동
	while (q->left != NULL)	// 가장 왼쪽 노드로 간다
	{
		q = q->left;
	}
	// 데이터를 출력한 다음에 중위 후속자를 찾음
	// 후속자가 자식노드일수도, 아니면 NULL포인터를 원래 가리켜야 하지만 스레드 이진트리 특성상 그 다음에 방문할 노드를 가리킴
	do {					
		printf("%c -> ", q->data);	// 데이터 출력
		q = find_successor(q);		// 후속자 함수 호출
	} while (q);					// NULL이 아니면 반복
}

전체 프로그램은 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
	int is_thread;	// 만약 오른쪽 링크가 스레드이면 TRUE
} TreeNode;
TreeNode* find_successor(TreeNode* p)	// 정점 p의 중위 후속자를 반환
{
	// p의 오른쪽 포인터가 무엇을 가리키는지에 따라 리턴해야 하는 정점이 다름
	TreeNode* q = p->right;
	// p의 오른쪽 포인터가 NULL을 가리키거나, 스레드이면 오른쪽 포인터를 반환하고, 
	if (q == NULL || p->is_thread == TRUE) {
		return q;
	}
	// 아니면, 중위순회해야 하므로 서브 트리의 가장 왼쪽 노드를 반환한다.
	while (q->left != NULL) {
		q = q->left;
	}
	return q;
}
void thread_inorder(TreeNode* root)
{
	TreeNode* q;
	q = root;
	// 중위순회는 가장 왼쪽 노드부터 시작하니까 while문으로 가장 왼쪽 노드로 이동
	while (q->left != NULL)	// 가장 왼쪽 노드로 간다
	{
		q = q->left;
	}
	// 데이터를 출력한 다음에 중위 후속자를 찾음
	// 후속자가 자식노드일수도, 아니면 NULL포인터를 원래 가리켜야 하지만 스레드 이진트리 특성상 그 다음에 방문할 노드를 가리킴
	do {					
		printf("%c -> ", q->data);	// 데이터 출력
		q = find_successor(q);		// 후속자 함수 호출
	} while (q);					// NULL이 아니면 반복
}
//		G
//	C		F
// A  B   D  E
TreeNode n1 = { 'A', NULL, NULL, 1};
TreeNode n2 = { 'B', NULL, NULL, 1};
TreeNode n3 = { 'C', &n1, &n2, 0 };
TreeNode n4 = { 'D', NULL, NULL, 1};
TreeNode n5 = { 'E', NULL, NULL, 1};
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode* root = &n7;

int main()
{
	n1.right = &n3;
	n2.right = &n7;
	n4.right = &n6;
	thread_inorder(root);
	printf("\n");
	return 0;

}

결과물은 아래와 같이 정상적으로 중위순회했음을 알 수 있다.