6-7. [C++] 스레드 이진 트리

스레드 이진 트리

앞서 알아본 순회 방법은 재귀 함수를 사용(전위/중위/후위 순회)하거나 별도의 자료구조 큐를 사용(레벨 순회)했다.

이런 방법말고는 순회하는 방법이 없을까?

이제 알아 볼 스레드 이진 트리(threaded binary tree)가 그렇다.

 

이진 트리에는 수많은 NULL링크가 존재한다.

노드의 개수가 n개인 이진 트리는 각 노드마다 2개의 링크 필드가 존재한다.

그래서 총 링크 필드의 개수는 2n개이고, 이 중 n-1개의 링크 필드만이 부모 노드와 연결되어 있다.

그러면 남은 n+1개의 링크 필드는 NULL을 가리키게 되는 것이다.

스레드 이진 트리는 NULL 링크 필드를 이용해서 재귀 호출이나 큐 없이 순회할 수 있다.

 

중위 순회를 위한 스레드 이진 트리를 알아 보자.

트리의 노드들을 중위 순회할 때 어떤 노드 바로 앞에 방문되는 노드를 중위 선행자(inorder predecessor),

어떤 노드 바로 다음에 방문되는 노드를 중위 후속자(inorder successor)라고 한다.

스레드 이진 트리의 핵심 개념은 NULL을 가리키는 링크 필드를 중위 선행자나 중위 후속자를 가리키게 하는 것이다. (위 그림은 중위 후속자만 표시한 그림임)

 

그런데 스레드 이진 트리에는 한 가지 문제가 있다.

NULL 링크 필드에 스레드를 저장하면 해당 링크 필드가 자식 노드를 가리키는 건지 스레드인지 알 수가 없다.

그래서 이것을 구분하기 위해 bool 변수가 필요하다.

---

C++로 구현하기

스레드 이진 트리의 노드는 앞서 구현했던 BinaryNode 클래스를 약간 변형해서 구현할 것이다.

https://seongmoahn.tistory.com/95

6-4. [C++] 연결 리스트로 구현한 이진 트리

링크 필드가 자식 노드를 가리키는지 스레드인지를 구분할 멤버 변수 bool bThread를 추가할 것이다.

이 변수는 오른쪽 링크 필드가 스레드이면 true, 자식 노드를 가리키면 false의 값을 갖는다.

// ThreadBiNode.h
#include <iostream>

class ThreadBiNode {
    char nodeName;
    ThreadBiNode *left;
    ThreadBiNode *right;

public:
    bool bThread;

    ThreadBiNode(int nodeName, ThreadBiNode *left, ThreadBiNode *right, bool bThread)
        : nodeName(nodeName), left(left), right(right), bThread(bThread) {}

    char getData() { return nodeName; }
    ThreadBiNode *getLeft() { return left; }
    ThreadBiNode *getRight() { return right; }

    void setRight(ThreadBiNode *right) { this->right = right; }
};

스레드 이진 트리에서 중위 순회는 어떻게 이뤄질까?

먼저 노드 node의 중위 후속자를 반환하는 findSuccessor() 함수를 만들어 node의 bThread 변수가 true로 설정돼 있으면 오른쪽 링크 필드가 중위 후속자가 되므로 node를 반환한다.

만약 오른쪽 링크 필드가 NULL이면 더 이상 후속자가 없다는 것이므로 NULL을 반환한다.

만약 bThread가 false이면 서브트리의 가장 왼쪽 노드로 이동해야 한다. 그 후, 해당 노드를 반환한다.

// ThreadBiTree.h
#include "ThreadBiNode.h"
using namespace std;

class ThreadBiTree {
    ThreadBiNode *root;
    
public:
    ThreadBiTree() : root(NULL) {}

    bool isEmpty() { return (root == NULL); }

    void setRoot(ThreadBiNode *root) { this->root = root; }

    ThreadBiNode *findSuccessor(ThreadBiNode *node) {
        ThreadBiNode *retNode = node->getRight();

        if (retNode == NULL || node->bThread) return retNode;

        else {
            while (retNode->getLeft() != NULL) retNode = retNode->getLeft();
            return retNode;
        }
    }
    void threadInorder() {
        if (!isEmpty()) {
            cout << "Thread Binary Tree : ";

            ThreadBiNode *curNode = root;
            while (curNode->getLeft()) curNode = curNode->getLeft();

            do {
                cout << "[" << curNode->getData() << "] ";
                curNode = findSuccessor(curNode);
            } while (curNode);

            cout << endl;
        }
    }
};

// ThreadBiTree.cpp
#include "ThreadBiTree.h"

int main() {
    ThreadBiTree tree;

    ThreadBiNode *A = new ThreadBiNode('A', NULL, NULL, true);
    ThreadBiNode *B = new ThreadBiNode('B', NULL, NULL, true);
    ThreadBiNode *C = new ThreadBiNode('C', A, B, false);
    ThreadBiNode *D = new ThreadBiNode('D', NULL, NULL, true);
    ThreadBiNode *E = new ThreadBiNode('E', NULL, NULL, false);
    ThreadBiNode *F = new ThreadBiNode('F', D, E, false);
    ThreadBiNode *G = new ThreadBiNode('G', C, F, false);
    A->setRight(C);
    B->setRight(G);
    D->setRight(F);

    tree.setRoot(G);

    tree.threadInorder();

    return 0;
}

/*
실행 결과 :
Thread Binary Tree : [A] [C] [B] [G] [D] [F] [E]
*/

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.