쓰레드 이진트리를 이용한 중위 순회

기존의 트리 순회 알고리즘(중위, 전위, 후위) 은 모두 순환호출(=스택)을 이용한 알고리즘이었습니다.

순환의 특성 상 트리의 높이가 커질수록 순환의 깊이가 깊어져서 상당히 비효율적일 수 있습니다.

쓰레드 이진트리는 노드의 NULL링크를 활용하여 순환 호출없이, 즉 반복문으로 순회할 수 있는 방법입니다.

선행 노드인 중위 선행자나 중위 순회 시 후속노드인 중위 후속자를 저장 시켜놓은 트리가 쓰레드 이진트리입니다.

중위 순회를 한다고 가정하여 중위 후속자를 저장한 쓰레드 이진트리를 구현해 보겠습니다.

일단 treeNode구조체에 쓰레드 정보를 가질 is_thread변수를 추가합니다. 값이 1이면 쓰레드를 가지고, 0이면 일반적인 트리입니다.

구현 함수는 2가지가 있습니다.

1. 쓰레드 중위순회 함수

후속자를 찾아 순서대로 출력합니다.

2. 중위 후속자를 찾는 함수( 중위 후속자를 반환)

=> 노드가 쓰레드를 가지면(is_thread==1) 오른쪽 자식을 반환합니다.

위 트리를 구성하는 과정에서 A와 C, B와G, D와F를 연결시켜놨기 때문에 쓰레드를 갖는 노드의 오른쪽 자식은 후속자가 됩니다.

현재 노드의 오른쪽자식 노드가 NULL이거나 p가 쓰레드를 가지면 q를 반환합니다.

(NULL일경우 1번함수에서 걸러지고, p가 쓰레드를 가지면 오른쪽 자식노드가 있음을 알기 때문)

그리고 G나 F같은 일반 노드 같은경우, 중위순회를 위해 서브 트리의 가장 왼쪽으로 가는 연산식이 필요합니다.

순회 순서는 순환방법과 똑같기 때문에 후속자를 찾는 포인트만 알고 있으면 구현이 어렵지 않습니다.

코드

#include<stdio.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define size 10
typedef struct treeNode
{
    int data;
    struct treeNode* left, * right;
    int is_thread;
}treeNode;
 
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 thread_inorder(treeNode* t);
treeNode* find_successor(treeNode* p);
int main()
{
    //쓰레드를 설정한다.
    n1.right = &n3;
    n2.right = &n7;
    n4.right = &n6;
    thread_inorder(exp);
}
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);
    puts("");
}
treeNode* find_successor(treeNode* p)
{
    treeNode* q = p->right;
    //q가 NULL일 때도 반환(어짜피 중위순회 함수에서 NULL을 받아 걸러짐
    //p가 (q의 오른쪽자식이) 쓰레드면 바로 반환
 
    if (q == NULL || p->is_thread == TRUE)
        return q;
    //G, F 같은 일반 노드의 경우 중위순회를 위해 맨 왼쪽노드를 찾음
    while (q->left != NULL)q = q->left;
    return q;
}

결과