[자료구조] 스레드 이진 트리(Threaded Binary Tree)

이진 트리 순회는 순환 호출을 사용하지만, 함수를 반복해서 호출해야 한다는 점에서 비효율적이다.
노드의 개수가 많아지고 트리의 높이가 커지게 되는 경우 프로그램 실행 시간의 측면에서 상당히 비효율적이다.
따라서 순회를 스택을 이용한 순환 호출이 아닌,
링크에 저장되어 있는 주소를 이용하여 다음 노드로 이동하는 반복 구조의 스레드 이진 트리를 고려해볼 수 있다.

이진 트리의 노드에는 많은 NULL링크들이 존재한다.
트리의 노드 개수를 n개라고 하면, 총 링크의 개수는 2n개이고,
이들 링크 중 n-1개의 링크들이 루트노드를 제외한 n-1개의 다른 노드를 가리킨다.
따라서, 2n개 중에서 n+1개의 링크는 NULL임을 알 수 있고,
이들 null 링크를 활용하여 순환 호출 없이 트리의 노드들을 순회할 수 있는 방법이 존재한다.

스레드 이진 트리(Threaded Binary Tree)란,
중외 순회 시, 선행 노드인 중위 선행자(inorder predecessor) 또는 후속 노드인 중위 후속자(inorder successor)을 저장시켜 놓은 트리이다.




스레드 이진 트리의 노드 구조체는 다음과 같다.
스레드가 저장되어 있는지를 구별해주는 태그 필드 is_thread 가 추가된 구조체이다.

#define TRUE 1
#define FALSE 0

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
	int is_thread; // 스레드이면 True
}TreeNode;

만약 is_thread가 TRUE이면, right 필드에는 중위 후속자 노드의 포인터가 되고,
FALSE라면 그대로 오른쪽 자식을 가리키는 포인터가 된다. (NULL일 수도, 오른쪽 자식 노드가 존재할 수도)



중위 후속자를 반환하는 find_successor 함수이다.

// 중위 후속자를 찾는 함수
TreeNode* find_successor(TreeNode* 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;
}

p의 is_thread가 TRUE인 경우, right 필드에 저장된 값이 바로 중위 후속자가 되므로 right 값을 반환한다.
만약 right값이 NULL이라면 더이상 후속자가 없다는 뜻이므로 그대로 null을 반환한다.

오른쪽 자식이라면, 다시 가장 왼쪽 노드로 이동하여
다시 스레드를 따라 순회하기를 반복한다.


아래는 스레드를 통한 중위 순회를 하는 함수이다.
가장 왼쪽 노드로 이동 한 후에,
후속자 함수 find_successor 을 호출하며 순회하는 방식이다.

// 스레드 중위 순회
void thread_inorder(TreeNode* t) {
	TreeNode* q;

	q = t;
	while (q->left)		// 가장 왼쪽 노드로 이동
		q = q->left;
	do {
		printf("%c -> ", q->data);	// 데이터 출력
		q = find_successor(q);		// 후속자 함수 호출 (q가 NULL이면 종료)
	} while (q);
}