Binary Search Tree

생성일: 2021년 11월 12일 오후 6:39

TreeType.h

#pragma once
#include <fstream>
#include <iostream>
#include "QueType.h"

template <class ItemType>
struct TreeNode
{
	ItemType info;
	TreeNode* left;
	TreeNode* right;
};

enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };

template <class ItemType>
class TreeType
{
public:
	TreeType();
	~TreeType();
	TreeType(const TreeType<ItemType>&);	//deep copy
	void operator=(const TreeType<ItemType>&);	//deep copy
	void MakeEmpty();
	bool IsEmpty() const;
	bool IsFull() const;
	int LengthIs() const;
	void RetrieveItem(ItemType&, bool& found);
	void InsertItem(ItemType);
	void DeleteItem(ItemType);
	void ResetTree(OrderType);	//OrderType은 왼쪽으로 갈지 오른쪽으로 갈지 선택
	void GetNextItem(ItemType&, OrderType, bool&);
	void PrintTree(std::ostream&) const;

private:
	TreeNode<ItemType>* root;
};

template <class ItemType>
void Destroy(TreeNode<ItemType>*& tree)
{
	if (tree != NULL)
	{
		Destroy(tree->left);
		Destroy(tree->right);
		delete tree;
	}
}

template <class ItemType>
TreeType<ItemType>::TreeType()
{
	root = NULL;
}

template <class ItemType>
TreeType<ItemType>::~TreeType()
{
	Destroy(root);
}

template <class ItemType>
void CopyTree(TreeNode<ItemType>*& copy, const TreeNode<ItemType>* originalTree)	//Preorder 순서 (본인, 왼쪽, 오른쪽)
{
	if (originalTree == NULL)
		copy = NULL;
	else
	{
		copy = new TreeNode<ItemType>;	//자동연결
		copy->info = originalTree->info;
		CopyTree(copy->left, originalTree->left);
		CopyTree(copy->right, originalTree->right);
	}
}

// Copy Constructor
template <class ItemType>
TreeType<ItemType>::TreeType(const TreeType<ItemType>& originalTree)
{
	CopyTree(root, originalTree.root);
}

template <class ItemType>
bool TreeType<ItemType>::IsFull() const
{
	TreeNode<ItemType>* location;
	try
	{
		location = new TreeNode<ItemType>;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception)
	{
		return true;
	}
}

template <class ItemType>
bool TreeType<ItemType>::IsEmpty() const
{
	return root == NULL;
}

//노드 개수 세기
template <class ItemType>
int CountNodes(TreeNode<ItemType>* tree)
{
	if (tree == NULL)
		return 0;
	else
		return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}

template <class ItemType>
int TreeType<ItemType>::LengthIs() const
{
	return CountNodes(root);
}

template <class ItemType>
void Retrieve(TreeNode<ItemType>* tree, ItemType& item, bool& found)
{
	if (tree == NULL)
		found = false;
	else if (item < tree->info)
		Retrieve(tree->left, item, found);
	else if (item > tree->right)
		Retrieve(tree->right, item, found);
	else
	{
		item = tree->info;
		found = true;
	}
}

template <class ItemType>
void TreeType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
	Retrieve(root, item, found);
}

template <class ItemType>
void Insert(TreeNode<ItemType>*& tree, ItemType item) // tree를 레퍼런스로 받음 => insert한 노드와 자동 연결 가능
{
	if (tree == NULL) // Insert할 자리를 찾았을 때
	{
		tree = new TreeNode<ItemType>; // 자동 연결
		tree->right = NULL;
		tree->left = NULL;
		tree->info = item;
	}
	else if (item < tree->info)
		Insert(tree->left, item);
	else
		Insert(tree->right, item);
}

template <class ItemType>
void TreeType<ItemType>::InsertItem(ItemType item)
{
	Insert(root, item);
}

template <class ItemType>
void DeleteNode(TreeNode<ItemType>*& tree);

template <class ItemType>
void Delete(TreeNode<ItemType>*& tree, ItemType item);

template<class ItemType>
void GetPredecessor(TreeNode<ItemType>* tree, ItemType& data);

template <class ItemType>
void TreeType<ItemType>::DeleteItem(ItemType item)
{
	Delete(root, item);
}

template <class ItemType>
void Delete(TreeNode<ItemType>*& tree, ItemType item)	//지울 위치 찾기, 찾으면 지우기
{
	if (item < tree->info)
		Delete(tree->left, item);
	else if (item > tree->info)
		Delete(tree->right, item);
	else //지울 노드 찾았을 때
		DeleteNode(tree);
}

template <class ItemType>
void DeleteNode(TreeNode<ItemType>*& tree)  //자동 연결 위해 레퍼런스로 받아 옴
{
	ItemType data;
	TreeNode<ItemType>* tempPtr;
	tempPtr = tree;

	if (tree->left == NULL)	//right child와 자리 바꾸고 지우기
	{
		tree = tree->right; //자동 연결
		delete tempPtr;
	}
	else if (tree->right == NULL) //left child와 자리 바꾸고 지우기
	{
		tree = tree->left; //자동 연결
		delete tempPtr;
	}
	else  //지우고자 하는 노드의 child가 두개 일 때
	{
		GetPredecessor(tree->left, data); //left subtree에서 가장 큰 녀석을 찾는다
		tree->info = data; //찾은 녀석을 지우고자 하는 노드에 위치시킨다.
		Delete(tree->left, data); //방금 찾아온 녀석을 다시 찾아서 밑에 있는 녀석을 지운다.
	}
}

template<class ItemType>
void GetPredecessor(TreeNode<ItemType>* tree, ItemType& data)
{
	while (tree->right != NULL)
		tree = tree->right;
	data = tree->info;
}

//Tree 출력
template<class ItemType>
void Print(TreeNode<ItemType>* tree, std::ostream& out)
{
	if (tree != NULL)
	{
		Print(tree->left, out);
		out << tree->info;
		Print(tree->right, out);
		out << std::endl;
	}
	
}

template<class ItemType>
void TreeType<ItemType>::PrintTree(std::ostream& out) const
{
	Print(root, out);
}

//교재의 Tree 출력 함수 (파일로)
//template<class ItemType>
//void Print(TreeNode<ItemType>* tree, std::ostream& outFile)
//{
//	if (tree != NULL)
//	{
//		Print(tree->left, outFile);
//		outFile << tree->info;
//		Print(tree->right, outFile);
//	}
//}
//
//template<class ItemType>
//void TreeType<ItemType>::PrintTree(std::ofstream& outFile) const
//{
//	Print(root, outFile);
//}

//Tree Traversal Methods
template <class ItemType>
void InOrder(TreeNode<ItemType>* tree, QueType<ItemType>& inQue)	//왼쪽 => 본인 => 오른쪽
{
	if (tree != NULL)
	{
		InOrder(tree->left, inQue);
		inQue.Enqueue(tree->info);
		InOrder(tree->right, inQue);
	}
}

template <class ItemType>
void PostOrder(TreeNode<ItemType>* tree, QueType<ItemType>& postQue)	//왼쪽 => 오른쪽 => 본인
{
	if (tree != NULL)
	{
		PostOrder(tree->left, postQue);
		PostOrder(tree->right, postQue);
		postQue.Enqueue(tree->info);
	}
}

template <class ItemType>
void PreOrder(TreeNode<ItemType>* tree, QueType<ItemType>& preQue)	//본인 => 왼쪽 => 오른쪽
{
	if (tree != NULL)
	{
		preQue.Enqueue(tree->info);
		PreOrder(tree->left, preQue);
		PreOrder(tree->right, preQue);	
	}
}

template <class ItemType>
void TreeType<ItemType>::ResetTree(OrderType order)
{
	switch (order)
	{
	case PRE_ORDER:
		PreOrder(root, preQue);
		break;
	case IN_ORDER:
		InOrder(root, inQue);
		break;
	case POST_ORDER:
		PostOrder(root, postQue);
		break;
	}
}

template <class ItemType>
void TreeType<ItemType>::GetNextItem(ItemType& item, OrderType order, bool& finished)
{
	finished = false;
	switch (order)
	{
	case PRE_ORDER:
		preQue.Dequeue(item);
		if (preQue.IsEmpty())
			finished = true;
		break;
	case IN_ORDER:
		inQue.Dequeue(item);
		if (inQue.IsEmpty())
			finished = true;
		break;
	case POST_ORDER:
		postQue.Dequeue(item);
		if (postQue.IsEmpty())
			finished = true;
		break;
	}
}

//재귀를 반복문으로 바꾸어 구현한 함수들 !!

template <class ItemType>
void FindNode(TreeNode<ItemType> tree, ItemType item, TreeNode<ItemType>*& nodePtr, TreeNode<ItemType>*& parentPtr)	//재귀로 구현한 것과 다르게 자동연결이 불가능하다 => 부모 노드를 트래킹해야함
{
	nodePtr = tree;
	parentPtr = NULL;
	bool found = false;
	while (nodePtr != NULL && !found)
	{
		if (item < nodePtr->info)
		{
			parentPtr = nodePtr;
			nodePtr = nodePtr->left;
		}
		else if (item > nodePtr->info)
		{
			parentPtr = nodePtr;
			nodePtr = nodePtr->right;
		}
		else
			found = true;
	}
}

//template <class ItemType>
//void TreeType<ItemType>::InsertItem(ItemType item)
//{
//	TreeNode<ItemType>* newNode;
//	TreeNode<ItemType>* nodePtr;
//	TreeNode<ItemType>* parentPtr;
//
//	newNode = new TreeNode<ItemType>;
//	newNode->info = item;
//	newNode->left = NULL;
//	newNode->right = NULL;
//
//	FindNode(root, item, nodePtr, parentPtr);
//	if (parentPtr == NULL) // 비어 있는 트리일 때
//		root = newNode;
//	else if (item < parentPtr->info)
//		parentPtr->left = newNode;
//	else
//		parentPtr->right = newNode;
//}

//template <class ItemType>
//void TreeType<ItemType>::DeleteItem(ItemType item)
//{
//	TreeNode<ItemType>* nodePtr;
//	TreeNode<ItemType>* parentPtr;
//	FindNode(root, item, nodePtr, parentPtr);
//	if (nodePtr == root) //root 노드가 지워야 할 노드일 때
//		DeleteNode(root);
//	else
//	{
//		if (parentPtr->left == nodePtr)
//			DeleteNode(parentPtr->left);
//		else
//			DeleteNode(parentPtr->right);
//	}
//}

Main.cpp

#include <iostream>
#include "TreeType.h"
using namespace std;

int main()
{
	TreeType<int> tree;
	tree.InsertItem(5);
	tree.InsertItem(3);
	tree.InsertItem(6);
	tree.InsertItem(1);
	tree.InsertItem(9);
	tree.InsertItem(4);

	tree.PrintTree(cout);
	tree.DeleteItem(3);
	tree.PrintTree(cout);
}