[자료구조] 스레드 이진트리 (Thread Binary Tree)

01. What

• 이진트리의 순회를 위해 queue와 같은 다른 자료구조를 사용하거나, recursive function을 호출하지 않고 순회하기 위해 만들어진 트리

02. Idea

• 이진트리의 노드가 총 N개일 때, 연결(Link)는 총 2N개 존재할 수 있다.
• 이 중 루트를 제외한 N-1개의 링크가 존재하고, 나머지 N+1개는 NULL Link(연결이 없는 상태)이다.
• 스레드 이진트리는 이 NULL Link를 다음 순회 대상을 가리키는 용도로 사용해서 구현한다.
• 노드의 오른쪽 자식이 없는 경우, 다음 순회 대상을 가리키는 순회 후속자(succeedor)를 가리키도록 해서 구현한다.
• 단순한 이진트리와 달리 오른쪽 노드가 Thread인지 아닌지를 구분하기 위한 bool 변수가 Node 클래스에 추가된다.

03. 설명

Thread Binary Tree 구조

스레드 이진트리를 순회하는 알고리즘을 말로 설명하면 다음과 같다.

여기서는 중위 순회 기준으로 설명하겠다. (LVR 순서로 순회)

1. 중위 순회이므로, 더 이상 왼쪽 노드가 없을 때까지 이동한다. (그림에선 4번 노드로)
2. 현재 노드의 오른쪽 노드가 없는 경우 순회가 끝난 것이다.
3. 현재 노드의 오른쪽 노드가 있고, 현재 노드가 Thread가 존재하는 노드인 경우는, 오른쪽 노드로 바로 이동한다.
4. 현재 노드의 오른쪽 노드가 있고, Thread가 아닌 경우는 (그림에서는 5번 노드 같은 경우), 해당 "오른쪽 노드"의 왼쪽 노드가 없을 때 까지 이동한 다음, 왼쪽 끝 노드로 이동한다.

04. 스레드 이진트리 및 중위 순회 구현

#pragma once

class CThreadBTNode
{
public:
	CThreadBTNode(char data);
	CThreadBTNode(char data, CThreadBTNode* left, CThreadBTNode* right, bool thread);

public:
	void Print() const;

	void SetThread(bool thread)
	{
		m_Thread = thread;
	}

	bool IsThread() const
	{
		return m_Thread;
	}

	void SetLeft(CThreadBTNode* node)
	{
		m_Left = node;
	}

	void SetRight(CThreadBTNode* node)
	{
		m_Right= node;
	}

	CThreadBTNode* GetLeft() const
	{
		return m_Left;
	}

	CThreadBTNode* GetRight() const
	{
		return m_Right;
	}

	char GetData() const
	{
		return m_Data;
	}

private:
	char m_Data;
	bool m_Thread;
	CThreadBTNode* m_Left;
	CThreadBTNode* m_Right;
};

Node 헤더, 특별한 건 없으니 구현은 생략

void CThreadBinaryTree::InOrder()
{
	std::cout << "Thread Binary Tree Inorder : ";

	if (m_Root)
	{
		CThreadBTNode* node = m_Root;

		while (node->GetLeft())
		{
			node = node->GetLeft();
		}

		do
		{
			if (!node)
			{
				break;
			}

			node->Print();

			// 후속자를 찾는다.
			CThreadBTNode* successor = node->GetRight();

			// 오른쪽 노드가 nullptr(순회 끝)거나, 현재 노드가 스레드 노드인 경우,
			// 더 이상 탐색하지 않고 nullptr, 현재 노드의 right후속자를 반환한다.
			if (successor == nullptr || node->IsThread())
			{
				node = successor;
			}
			// 현재 노드의 right 노드가 thread가 아닌 경우,
			// right노드의 왼쪽 끝의 노드가 후속노드이다.
			else
			{
				while (successor->GetLeft())
				{
					successor = successor->GetLeft();
				}
			}

			node = successor;
		} while (true);
	}

	std::cout << "\n";
}