25. 스레드 이진트리 (Threaded Binary Tree)

스레드 이진트리란?

이진 트리에 삽입, 삭제 등의 연산을 보다 빠르고 간단하게 수행하기 위해 추가된 자료구조이다.

스레드 이진트리는 각 노드에 스레드라는 추가적인 링크를 추가하여 구현된다.

 

스레드 링크는 이진트리의 노드에서 왼쪽이나 오른쪽 자식이 NULL 일 때, 해당 방향으로 직접 다음 순서의 노드를 가리키는 포인터이다. 이렇게 스레드 링크를 추가함으로써, 이진 트리에서 전위, 중위, 후위 순회를 수행할 때 재귀 호출 없이 스레드 링크로 순회가 가능해진다.

---

스레드 이진 트리 구조체

leftThread, rightThread가 1이라면 해당 링크는 스레드 링크이고, 0이면 자식의 포인터를 저장한다.

typedef struct Node *Nodepointer;
typedef struct Node{
    int leftThread;
    Nodepointer leftchild;
    int data;
    int rightThread;
    Nodepointer rightchild;
}Node;

---

스레드 이진 트리 삽입

기본적으로 이진 탐색트리의 형태로 구성하기 위해 작으면 왼쪽 자식, 크면 오른쪽 자식을 가리키게 된다.

삽입이 될 위치에 도달하게 되면 기존 스레드 링크를 가진 노드와 삽입될 노드의 링크를 업데이트한다.

Nodepointer CreateNode(int data){
    Nodepointer new = (Nodepointer)malloc(sizeof(Node));
    new->data = data;
    new->leftThread = 1;
    new->leftchild = NULL;
    new->rightThread = 1;
    new->rightchild = NULL;
    return new;
}

Nodepointer insert(Nodepointer root, int data){
    if(root == NULL) return CreateNode(data);
    
    Nodepointer temp = root;
    while(1){
        if(data < temp->data){
            if(!(temp->leftThread)) temp = temp->leftchild;
            else{
                Nodepointer new_node = CreateNode(data);
                new_node->leftchild = temp->leftchild;
                new_node->rightchild = temp;
                temp->leftchild = new_node;
                temp->leftThread = 0;
                return root;
            }
        }
        else if(data > temp->data){
            if(!(temp->rightThread)) temp = temp->rightchild;
            else{
                Nodepointer new_node = CreateNode(data);
                new_node->leftchild = temp;
                new_node->rightchild = temp->rightchild;
                temp->rightchild = new_node;
                temp->rightThread = 0;
                return root;
            }
        }
        else
            return root;
    }
}

---

스레드 이진트리 순회

이전에 이야기했던 것처럼 재귀 없이 순회가 가능하다는 것을 확인할 수 있다.

void inorder(Nodepointer root){
    Nodepointer temp = root;
    
    while(!(temp->leftThread)) temp = temp->leftchild;
    while(temp){
        printf("%d ", temp->data);
        if(temp->rightThread) temp = temp->rightchild;
        else{
            temp = temp->rightchild;
            while(!(temp->leftThread)) temp = temp->leftchild;
        }
    }
}