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

 

이진 트리는 순환적으로 트리 전체를 방문한다. 순환 횟수는 트리의 높이에 비례하기 때문에 반복보다 비효율적이다.

스레드 이진트리는 일반적인 이진 트리의 순회 방법과 달리 효율적이고 스택을 사용하지 않는 순회 방법이다.

 

 

일반적으로, 이진 트리에서 노드의 개수가 n일 때 루트 노드를 제외한 n-1개 링크는 다른 노드를 가리키고 n+1개의 링크는 NULL임을 알 수 있다.

 

이것을 이용해서 NULL 링크에 중위 후속자(successor)를 저장해놓고 순회할 수 있게 만들 것이다.

이진 트리의 정의

1) 공집합

2) 루트와 왼쪽, 오른쪽 서브 트리로 구성된 노드들의 유한집합

3) 서브 트리 또한 이진 트리여야 한다. 

 

 

이제 함수를 정의해보자.

 

1. 트리 노드 구조체

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

 

2. find_successor() // 중위 후속자를 찾는 함수

TreeNode* find_successor(TreeNode* node) {
	TreeNode* q = node->right; // node의 오른쪽 자식을 가리킴
    
    	if (q == NULL || q->is_thread)
    		return q;
        
   	while (q->left != NULL) q = q->left;
    		return 	q;
}

이 함수는 q가 node의 오른쪽 자식을 가리키고, q의 is_thread가 TRUE일 때 반환하도록 한다.

 

3. thread_inorder // 중위 순회

void thread_inorder(TreeNode* node) {
	TreeNode* q;
    
    	q = node;
    	while (q->left != NULL) q = q->left;
    	do {
    		printf("%c", q->data);
        	q = find_successor(q);
    	} while (q);
}

중위 순회는 왼쪽-루트-오른쪽 순으로 방문하기 때문에 왼쪽 노드가 NULL일 때까지 반복하고 중위 후속자를 찾는 함수를 호출한다.

 

 

전체 코드

 

#include <stdio.h>

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


TreeNode* find_successor(TreeNode* node) {
	TreeNode* q = node->right; // node의 오른쪽 자식을 가리킴
    
    	if (q == NULL || q->is_thread == TRUE)
    		return q;
        
   	while (q->left != NULL) q = q->left;
    		return q;
}

void thread_inorder(TreeNode* node) {
	TreeNode* q;
    
    	q = node;
    	while (q->left != NULL) q = q->left;
    	do {
    		printf("%c", q->data);
        	q = find_successor(q);
    	} while (q);
}

//        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, 0 };
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode *exp = &n7;
 
void main()
{
  // 스레드 설정
  n1.right = &n3;
  n2.right = &n7;
  n4.right = &n6;
 
  // 중위 순회
  thread_inorder(exp);
  return 0;
}

 

thread_inorder(exp)	find_successor(node)	q = node->right	is_thread	return q
G	node = A	q = C	TRUE	C
	node = C	q = B	FALSE	B
	node = B	q = G	TRUE	G
	node = G	q = F	FALSE	D
	node = D	q = F	TRUE	F
	node = F	q = E	FALSE	E
	node = E	q = NULL	FALSE, NULL	NULL

출력 결과 : A - C - B - G - D - F - E

 

스레드 이진 트리에서 NULL에 저장되는 것은?

=> 중위 후속자(successor)

 

이진 트리의 노드 개수가 n이라면 NULL 링크의 개수는?

=> n+1개