[자료구조] 스레드 이진 트리(threaded binary tree)

NULL 링크에 중위 후속자 (inorder successor)를 저장시켜 놓은 이진 트리입니다. 중위 후속자란 중위 순회의 순서에서 그 다음에 이어질 차례의 노드입니다. 중위 후속자로 인해 순환 호출 없이도 중위 순회가 간편하다는 장점이 있습니다.

 

스레드 이진 트리 구조체

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

중위 후속자를 찾는 함수

TreeNode *find_successor(TreeNode *p)
{
	// q는 p의 오른쪽 포인터
	TreeNode *q = p->right;

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

	// q의 왼쪽 자식이 존재하면 다시 가장 왼쪽 노드로 이동
	while( q->left != NULL ) 
		q = q->left;
	return q;
}

스레드 이진 트리의 중위 순회 함수

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

	while (q->left) q = q->left;		// 가장 왼쪽 노드로 이동

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