스레드 이진트리

노드의 개수가 n 이면 전체 링크의 수는 2n.

루트를 제외한 n-1 개의 노드가 부모와 연결됨(간선).

2n 중에 n-1 개를 제외한 n+1 개의 링크가 항상 NULL.

 

n+1개의 NULL 링크에 중위 순회 시에 선행 노드인 중위선행자(inorder predecessor)나

중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리

 

class ThreadBinNode
{
private:
    int data;
    ThreadBinNode* left;
    ThreadBinNode* right;
public:
    bool bThread;
 
public:
    ThreadBinNode(int value, ThreadBinNode* l, ThreadBinNode* r, bool bTh)
        : data(value), left(l), right(r), bThread(bTh)
    {}
    int getData()
    {
        return data;
    }
    void setRight(ThreadBinNode* r)
    {
        right = r;
    }
    ThreadBinNode* getLeft()
    {
        return left;
    }
    ThreadBinNode* getRight()
    {
        return right;
    }
};
 
 
#include "ThreadBinNode.h"
 
class ThreadBinTree
{
private:
    ThreadBinNode* root;
public:
    ThreadBinTree(): root(NULL)
    {}
    void setRoot(ThreadBinNode* node)
    {
        root = node;
    }
    bool isEmpty()
    {
        return root == NULL;
    }
    // 스레드 방식의 inorder 방문 함수
    void threadInorder()
    {
        if (!isEmpty())
        {
            printf("스레드 이진트리: ");
            ThreadBinNode* q = root;
            
            while (q->getLeft())
            {
                q = q->getLeft();
            }
            do
            {
                printf("%c ", q->getData());
                q = findSuccessor(q);
            } while (q);
            printf("\n");
        }
    }
    // 후속자 함수 호출
    ThreadBinNode* findSuccessor(ThreadBinNode* p)
    {
        ThreadBinNode* q = p->getRight(); // 오른쪽 자식 포인터
 
        // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
        if (q == NULL || p->bThread) return q;
        // 만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
        while (q->getLeft() != NULL) q = q->getLeft();
        return q;
    }
};