[Data Structure] 스레드 이진 트리

이진 트리

- 이진 트리에 n개의 노드가 있을 경우

• 2n개의 링크 존재
• 2n개의 링크 중, n+1개의 링크 = NULL
• 2n개의 링크 중, n-1개의 링크 = 다른 노드를 가리킨다
• NULL 링크에 중위 선행자/후속자를 저장해 놓은 트리 = 스레드 이진 트리 

 

스레드 이진 트리

- NULL 링크를 이용해서 순환호출 없이 트리의 노드들을 순회 가능

- 단말 노드 / 비단말 노드를 구분하기 위해 is_thread 필드 필요

- 노드의 right를 후속자를 가리키게 설정, is_thread = 1로 설정

typedef struct treenode {
	char data;
	struct treenode* left;
	struct treenode* right;
	int is_thread; // 1이면 ->right는 중위 후속자, 0이면, ->right는 그냥 오른쪽 자식 가리키는 포인터
}treenode;

treenode n1 = {'A', NULL, NULL, 1};
treenode n2 = {'B', NULL, NULL, 1};
treenode n3 = {'D', NULL, NULL, 1};
treenode n4 = {'E', NULL, NULL, 0};
treenode n5 = {'C', &n1, &n2, 0};
treenode n6 = {'F' ,&n3, &n4, 0};
treenode n7 = {'G', &n5, &n6, 0};
treenode* root = &n7;

// 스레드 설정
n1.right = &n5;
n2.right = &n7;
n3.right = &n6;

 

 

중위 후속자 반환 함수 find_successor

• is_thread = 1이면, right는 후속자를 가리키고 있는 상태 ∴ 해당 노드의 right 반환
• 해당 노드의 right = NULL이면, 그냥 NULL 반환 (NULL = 해당 노드의 right)
• is_thread != 1이면, 해당 노드에서 서브트리의 가장 왼쪽 노드로 가야 한다

treenode* find_successor(treenode* node) {
	// 중위 후속자 리턴하는 함수 ( 오른쪽 자식 리턴)
	treenode* q = node->right; // p = node의 오른쪽 포인터
	
	if (q == NULL || node->is_thread == 1)
		return q;
	if (node->is_thread == 0) 
		while (q->left != NULL) q = q->left;
	return q;
}

 

 

스레드 이진 트리에서 중위 순회

• 중위 순회는 LVR순으로 순회 → left가 NULL이 될 때까지 왼쪽 링크를 타고 왼쪽 끝으로 이동
• 이 다음에 해당 노드의 data를 출력
• 그리고, find_successor를 호출해서 후속자가 NULL이 아니면 계속 루프 반복

void inorder_thread(treenode* root) {
	treenode* q;
	q = root;
	while (q->left) q = q->left;
	do {
		printf("%c -> ", q->data);
		q = find_successor(q);
	} while (q);
}