/*
쓰레드 이진 트리, Threaded Binary Trees
*/
#include <iostream>
using namespace std;
class ThreadedTree;
class ThreadedNode
{
private:
//기본적으로 쓰레드는 말단노드(leaf node)에만 해당
bool leftThread; //중위순회할 때 다음에 올 데이터
ThreadedNode *leftChild;
char data;
ThreadedNode *rightChild;
bool rightThread; //중위순회할 때 그 전에 온 데이터
public:
ThreadedNode() :leftChild(NULL), rightThread(NULL)
{
}
ThreadedNode(char temp, ThreadedNode *left, ThreadedNode *right, bool leftT, bool rightT) :data(temp), leftChild(NULL), rightChild(NULL), leftThread(leftT), rightThread(rightT)
{
}
friend class ThreadedTree;
friend class ThreadedInorderIterator;
};
class ThreadedTree
{
private:
ThreadedNode *root;
public:
ThreadedTree()
{
root = new ThreadedNode; // dummy 노드
root->rightChild = root->leftChild = root;
root->leftThread = true; //더미노드의 왼쪽노드에 실질적인 root가 오므로 leftThread만 true
root->rightThread = false;
}
void Initialize() //트리를 초기화
{
ThreadedNode *A, *B, *C, *D, *E, *F, *G, *H, *I, *J, *K;
root->leftChild = A = new ThreadedNode('A', 0, 0, false, false);
root->leftThread = false;
A->leftChild = B = new ThreadedNode('B', 0, 0, false, false);
A->rightChild = C = new ThreadedNode('C', 0, 0, false, false);
B->leftChild = D = new ThreadedNode('D', 0, 0, false, false);
B->rightChild = E = new ThreadedNode('E', 0, 0, true, true);
D->leftChild = H = new ThreadedNode('H', 0, 0, true, true);
D->rightChild = I = new ThreadedNode('I', 0, 0, true, true);
C->leftChild = F = new ThreadedNode('F', 0, 0, true, true);
C->rightChild = G = new ThreadedNode('G', 0, 0, true, true);
//쓰레드를 연결시킨다
//dummy노드가 없었더라면 H의 왼쪽 쓰레드, G의 오른쪽 쓰레드가 갈 곳을 잃었을 것이다
//허나 dummy노드가 있기 때문에 위의 문제를 root를 가리키면서 해결가능하다
H->leftChild = root;
H->rightChild = D;
I->leftChild = D;
I->rightChild = B;
E->leftChild = B;
E->rightChild = A;
F->leftChild = A;
F->rightChild = C;
G->leftChild = C;
G->rightChild = root;
J = new ThreadedNode('J', 0, 0, false, false); //A의 왼쪽에 입력할 것이기 때문에 Thread는 fasle
K = new ThreadedNode('K', 0, 0, false, false); //A의 오른쪽에 입력할 것이기 때문에 Thread는 false
InsertLeft(A, J);
InsertRight(A, K);
}
void InsertLeft(ThreadedNode *s, ThreadedNode *l)
{
//r을 s의 왼쪽 자식으로 입력
l->leftChild = s->leftChild;
l->leftThread = s->leftThread;
l->rightChild = s;
l->rightThread = true;
s->leftChild = l;
s->leftThread = false;
if (!l->leftThread)
{
ThreadedNode *temp = InorderSucc(l->leftChild);
temp->rightChild = l;
}
}
void InsertRight(ThreadedNode *s, ThreadedNode *r)
{
//r을 s의 오른쪽 자식으로 입력
r->rightChild = s->rightChild;
r->rightThread = s->rightThread;
r->leftChild = s;
r->leftThread = true; //leftChild는 쓰레드
s->rightChild = r;
s->rightThread = false;
if (!r->rightThread)
{
ThreadedNode *temp = InorderSucc(r); //중위순회 했을 때 r 다음으로 오는 노드
temp->leftChild = r;
}
}
ThreadedNode *InorderSucc(ThreadedNode *cur)
{
ThreadedNode *temp = cur->rightChild;
if (!cur->rightThread)
while (!temp->leftThread)
temp = temp->leftChild;
return temp;
}
friend class ThreadedInorderIterator;
};
class ThreadedInorderIterator
{
private:
ThreadedTree tree;
ThreadedNode *currentNode;
public:
ThreadedInorderIterator(ThreadedTree t) :tree(t)
{
currentNode = tree.root;
}
char *Next()
{
ThreadedNode *temp = currentNode->rightChild;
if (!currentNode->rightThread)
while (!temp->leftThread)
temp = temp->leftChild;
currentNode = temp;
if (currentNode == tree.root)
return 0;
else
return ¤tNode->data;
}
void Inorder()
{
for (char *ptr = Next(); ptr; ptr = Next())
cout << *ptr << endl;
}
};
int main(void)
{
ThreadedTree tree;
tree.Initialize();
ThreadedInorderIterator iterator(tree);
iterator.Inorder();
return 0;
}
[출력된 쓰레드 이진 트리]
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, http://www.crocus.co.kr/366, http://cs.sungshin.ac.kr/~jpark/DS1-2/SOURCE/CH5/thread.cpp
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*쓰레드 이진트리 개념을 http://www.crocus.co.kr/366 링크를 통해 완벽히 이해했습니다.
*Initialize() 함수와 main 함수는 http://cs.sungshin.ac.kr/~jpark/DS1-2/SOURCE/CH5/thread.cpp 링크에 있는 함수를 가져다 썼습니다.