16. 이진트리 -c. 스레이드 이진 트리(Threaded Binary Tree)

스레이드 이진 트리

  # 스레이드 이진 트리라는 말보다는 스레드 이진 트리라는 표현이 더 많이 쓰이는 것 같지만, 왠지 운영체제의 스레드와 혼동이 되므로 스레이드라 썼다.

  # 스레이드 이진 트리는 이진트리의 순회를 재귀함수로 구현하면 시스템 스택을 사용하므로 비효율적이기 때문에 이를 영링크를 활용하여 비재귀적으로 바꾼 트리이다.

  # ... 라는데 아래의 구현이 더 효율적일지는 잘 모르겠고, 일단 순회에 있어서 재귀호출을 사용하지 않게 하는데만 집중했다.

  # 아무리 생각해도 구현의 난이도가 쓸데없이 높아서 사용이 많이 될지는 모르겠다.

  # 저번 포스트의 전위, 중위, 후위 순회 부분만 비재귀로 바꿨다.

구현 코드

#pragma once

template <typename T>
struct node
{
	T data;

	node* prev;
	node* next;

	node* left;
	node* right;
};

//트리 관련 전역 함수
template <typename T>
void ChangeData(node<T>* node, T data)
{
	node->data = data;
}

template <typename T>
T& CheckData(node<T>* node)
{
	return node->data;
}

template <typename T>
node<T>* MakeNode(T data)
{
	node<T>* nn = new node<T>;
	nn->data = data;
	nn->left = nullptr;
	nn->right = nullptr;
	nn->prev = nullptr;
	nn->next = nullptr;

	return nn;
}

//작업을 함수포인터로 전달받는 순회 함수
template <typename T>
void preorder(node<T>* _node, void(*action)(T))
{
	node<T>* nptr = _node;

	while (nptr != nullptr) {
		if (nptr->left != nullptr) {
			if (nptr->right != nullptr) {
				nptr->left->next = nptr->right;
			}
			else {
				nptr->left->next = nptr->next;
			}
		}
		if(nptr->right != nullptr) {
			nptr->right->next = nptr->next;
		}

		action(nptr->data);
		if (nptr->left != nullptr) {
			nptr = nptr->left;
		}
		else if (nptr->right != nullptr) {
			nptr = nptr->right;
		}
		else {
			nptr = nptr->next;
		}	
	}
}


template <typename T>
void inorder(node<T>* _node, void(*action)(T))
{
	node<T>* nptr = _node;

	while (nptr->left != nullptr) {
		if (nptr->left != nullptr) {
			nptr->left->next = nptr;
		}
		if (nptr->right != nullptr) {
			nptr->right->next = nptr->next;
		}
		nptr = nptr->left;
	}

	while (nptr != nullptr) {
		if (nptr->left != nullptr) {
			nptr->left->next = nptr;
		}
		if (nptr->right != nullptr) {
			nptr->right->next = nptr->next;
		}

		action(nptr->data);
		 if (nptr->right != nullptr) {
			nptr = nptr->right;
			while (nptr->left != nullptr) {
				if (nptr->left != nullptr) {
					nptr->left->next = nptr;
				}
				if (nptr->right != nullptr) {
					nptr->right->next = nptr->next;
				}
				nptr = nptr->left;
			}
		}
		else {
			nptr = nptr->next;
		}
	}

}


template <typename T>
void postorder(node<T>* _node, void(*action)(T))
{
	node<T>* nptr = _node;

	bool ldsw = false;

	while (nptr != nullptr) {
		if (!ldsw) {
			while (nptr->left != nullptr) {
				if (nptr->left != nullptr) {
					if (nptr->right != nullptr) {
						nptr->left->next = nptr->right;
					}
					else {
						nptr->left->next = nptr;
					}
				}
				if (nptr->right != nullptr) {
					nptr->right->next = nptr;
				}
				nptr = nptr->left;

			}

			if (nptr->left == nullptr && nptr->right != nullptr) {
				if (nptr->left != nullptr) {
					if (nptr->right != nullptr) {
						nptr->left->next = nptr->right;
					}
					else {
						nptr->left->next = nptr;
					}
				}
				if (nptr->right != nullptr) {
					nptr->right->next = nptr;
				}
				nptr = nptr->right;
			}

			ldsw = true;
		}

		if (nptr->left != nullptr && ldsw == true) {
			action(nptr->data);
			nptr = nptr->next;
			ldsw = false;
			if (nptr != nullptr && nptr->next == nullptr) {
				action(nptr->data);
				break;
			}
		}
		else {
			action(nptr->data);
			nptr = nptr->next;
		}
	}
}



template <typename T>
class BinaryTree
{
	node<T>* rootNode;

private:


public:
	//노드 포인터를 리턴하는 함수
	node<T>* getRoot();
	node<T>* getRight(node<T>* node);
	node<T>* getLeft(node<T>* node);

	//src트리를 Dest노드의 자식으로 붙임
	bool  connectLeft(node<T>* DestNode, node<T>* SrcTree);
	bool  connectRight(node<T>* DestNode, node<T>* SrcTree);

public:
	BinaryTree(T data);
	virtual ~BinaryTree();
};

template <typename T>
BinaryTree<T>::BinaryTree(T data)
{
	rootNode = new node<T>;
	rootNode->data = data;
	rootNode->left = nullptr;
	rootNode->right = nullptr;
	rootNode->prev = nullptr;
	rootNode->next = nullptr;
}


template <typename T>
node<T>* BinaryTree<T>::getRoot()
{
	return rootNode;
}

template <typename T>
node<T>* BinaryTree<T>::getLeft(node<T>* node)
{
	return node->left;
}

template <typename T>
node<T>* BinaryTree<T>::getRight(node<T>* node)
{
	return node->right;
}


template <typename T>
bool  BinaryTree<T>::connectLeft(node<T>* DestNode, node<T>* srcTree)
{
	if (DestNode->left == nullptr) {
		DestNode->left = srcTree;
		return true;
	}

	return false;
}

template <typename T>
bool  BinaryTree<T>::connectRight(node<T>* DestNode, node<T>* srcTree)
{
	if (DestNode->right == nullptr) {
		DestNode->right = srcTree;
		return true;
	}

	return false;
}


template <typename T>
BinaryTree<T>::~BinaryTree()
{

}