스레드 이진 트리

스레드 이진 트리(threaded binary tree)
- 함수를 호출해야 하므로 비효율적인 순환 호출 대신 스레드 이진 트리 사용 가능

- 스택 사용 x

 

- 트리의 노드 개수가 n개일 때

- 총 링크의 개수는 2n개(각 노드 당 2개의 링크가 있으므로)

- NULL이 아닌 링크의 개수는 (n-1)개

- NULL인 링크의 개수는 (n+1)개

 

- 중위 순회 시 NULL 링크에 스레드를 저장

- 선행 노드인 중위 선행자(inorder predecessor)나 후속 노드인 중위 후속자(inorder successor)를 저장해 놓은 트리가 스레드 이진 트리

- 스레드를 이용하여 노드들을 순회 순서대로 연결

- NULL 링크에 스레드가 저장되면, 링크에 자식을 가리키는 포인트가 저장되어 있는지 NULL 대신 스레드가 저장되어 있는지 구별하기 위해 별도의 태그 필드가 필요

- 노드의 구조가 아래와 같이 변경됨

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
	int is_thread;	//오른쪽 링크가 스레드이면 TRUE
} TreeNode;

(문제를 간단하게 하기 위하여 중위 후속자만 저장되어 있다고 가정)

- is_thread가 TRUE이면 right는 중위 후속자, FALSE이면 오른쪽 자식 노드를 가리키는 포인터

TreeNode* find_successor(TreeNode* p) {
	TreeNode* q = p->right;

	if (q == NULL || p->is_thread == TRUE) {
		return q;
	}	//오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환

	while (q->left != NULL) {
		q = q->left;
	}	//q가 오른쪽 자식 노드이면 가장 왼쪽 노드로 이동

	return q;
}

 

- 노드 p의 중위 후속자를 반환하는 함수 find_successor

- p의 is_thread가 TRUE이면 오른쪽 자식이 중위 후속자가 되므로 오른쪽 자식을 반환

- 오른쪽 자식이 NULL이면 더 이상 후속자가 없으므로 NULL 반환

- is_thread가 TRUE가 아닐 때는 서브 트리의 가장 왼쪽 노드로 가야 함

- 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 이동

void thread_inorder(TreeNode* t) {
	TreeNode* q;

	q = t;
	while (q->left) {
		q = q->left;
	}	//q의 왼쪽 자식 노드가 TRUE이면 왼쪽 링크를 타고 이동

	do {
		printf("%c -> ", q->data);	//데이터 출력
		q = find_successor(q);	//후속자 함수 호출
	} while (q);	//NULL이 아니면
}

- 순회는 가장 왼쪽 노드부터 시작하므로 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 이동

- 후속자가 NULL이 아니면 계속 루프 반복

 

- 스레드 트리는 순회 속도 면에서 유리

- 스레드 설정을 위해 삽입이나 삭제 함수가 더 많은 일을 해야 함

---

전체 코드

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

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
	int is_thread;	//오른쪽 링크가 스레드이면 TRUE
} TreeNode;

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, 0 };
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode* exp = &n7;

TreeNode* find_successor(TreeNode* p) {
	TreeNode* q = p->right;

	if (q == NULL || p->is_thread == TRUE) {
		return q;
	}	//오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환

	while (q->left != NULL) {
		q = q->left;
	}	//오른쪽 포인터가 자식을 가리키면 가장 왼쪽 노드로 이동

	return q;
}

void thread_inorder(TreeNode* t) {
	TreeNode* q;

	q = t;
	while (q->left) {
		q = q->left;
	}	//q의 왼쪽 자식 노드가 TRUE이면 왼쪽 링크를 타고 이동

	do {
		printf("%c -> ", q->data);	//데이터 출력
		q = find_successor(q);	//후속자 함수 호출
	} while (q);	//NULL이 아니면
}

int main(void) {
	//스레드 설정
	n1.right = &n3;
	n2.right = &n7;
	n4.right = &n6;

	//중위 순회
	thread_inorder(exp);
	printf("\n");

	return 0;
}

>>