[Data Structure] 스레드 이진 트리

 스레드 이진 트리라는 것은 무척이나 생소한 개념이다. 허나 이 개념이 등장한 이유는 아주 심플하다. 여태 우리가 배웠던 순회라는 것은 모두 Stack를 사용했기 때문에 효율적이지 않다. 그 노드 수가 많아질 수록 시간이 오래 걸리기 때문이다.
 이러한 점을 해결하고자 나온 개념이 바로 스레드(Thread), 실이다. 하나의 노드를 순회하고 나서 순회 타입에 맞는 다음 노드를 연결시켜놓은 것을 스레드라고 한다. 그래서 이러한 트리를 Thread Binary Tree라고도 부른다.
 여기서는 간단히 개념만을 살펴보기 위해서 중위 순회시 적용된 스레드의 코드만을 볼 것이다. 중위 순회에서는 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리 순서로 순회를 하게 된다. 왼쪽 노드는 부모를 가리키면 되고 오른쪽 노드는 부모의 부모 노드를 가리키면 된다. 이 말이 어려울 수도 있는데 그냥 코드를 보면서 찬찬히 생각해보면 아주 쉽다.

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

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

// Node의 중위 후속자를 반환하는 함수이다. 이때
// 중위 후속자란 중위 순회를 할 때 해당 노드의 다음 노드(후속자)를 의미한다.
TreeNode* find_succesor(TreeNode *p){
    // q는 p의 오른쪽 포인터.
    TreeNode *q = (TreeNode*) p->right;
    // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 변환
    if (q == NULL || p->is_thread == TRUE) {
        // 오른쪽 포인터가 null일 경우는 완전히 모든 순회가 끝났을 때
        return q;
    }
    while (q->left != NULL) {
        q = (TreeNode*) q->left;
    }
    return q;
}

void thread_inorder(TreeNode *t){
    TreeNode *q;
    q=t;
    
    // 중위 순회이기 때문에 가장 먼저 맨 왼쪽 단말 노드로 향한다.
    while (q->left != NULL) q = (TreeNode*) q->left;
    
    do {
        printf("%c ",q->data);
        q = find_succesor(q); // 중위 순회시 다음 노드를 찾아 준다.
    } while (q);
}

int main(){
    TreeNode n1 = {'A',NULL,NULL,TRUE}; // threaded
    TreeNode n2 = {'B',NULL,NULL,TRUE}; // threaded
    TreeNode n3 = {'C',&n1,&n2,FALSE};
    TreeNode n4 = {'D',NULL,NULL,TRUE}; // threaded
    TreeNode n5 = {'E',NULL,NULL,FALSE};
    TreeNode n6 = {'F',&n4,&n5,FALSE};
    TreeNode n7 = {'G',&n3,&n6,FALSE};
    TreeNode *exp = &n7;
    
    n1.right = &n3; // A -> C
    n2.right = &n7; // B -> G
    n4.right = &n6; // D -> F
    
    thread_inorder(exp);
    printf("\n");
    return 0;
}

친절하게도 주석도 달아놨다 :D