BST.h

#pragma once

#include <utility>

#include "TreeNode.h"

#define ITERATIVE

template <typename K, typename E> class BST
{
public:
	BST() : root(nullptr) {}
	~BST();

public:
	bool Insert(std::pair<K, E> data);

#ifdef ITERATIVE
	std::pair<K, E>* Get(const K& k);
	
#else // RECURSIVE
	std::pair<K, E>* Get(const K& k);

private:
	std::pair<K, E>* Get(TreeNode <std::pair<K, E>> *p, const K& k);
#endif

private:
	void destroy(TreeNode<std::pair<K, E>> * root);
	
private:
	TreeNode<std::pair<K, E>> * root;
};

template<typename K, typename E>
BST<K, E>::~BST()
{
	if (this->root == nullptr)
		return;
	destroy(this->root);
}

template<typename K, typename E>
inline bool BST<K, E>::Insert(std::pair<K, E> data)
{
	TreeNode<std::pair<K, E>> * pp = nullptr;
	auto p = this->root;

	while (p)
	{
		pp = p;
		if (p->getData().first < data.first)
			p = p->getRightChild();
		else if (p->getData().first > data.first)
			p = p->getLeftChild();
		else 
		{ 
			p->getData().second = data.second;
			return true;
		}
	}

	p = new TreeNode<std::pair<K, E>>;
	p->setData(data);
	if (this->root)
	{
		if (pp->getData().first < data.first)
			pp->setRightChild(p);
		else
			pp->setLeftChild(p);
	}
	else
	{
		this->root = p;
	}
	
	return true;
}

#ifdef ITERATIVE
template<typename K, typename E>
std::pair<K, E>* BST<K, E>::Get(const K & k)
{
	auto currentNode = this->root;
	while (currentNode)
	{
		if (k < currentNode->getData().first)
			currentNode = currentNode->getLeftChild();
		else if (k > currentNode->getData().first)
			currentNode = currentNode->getRightChild();
		else
			return &currentNode->getData();
	}
	return nullptr;
}
#else	// RECURSIVE
template<typename K, typename E>
std::pair<K, E>* BST<K, E>::Get(const K & k)
{
	return this->Get(this->root, k);
}

template<typename K, typename E>
std::pair<K, E>* BST<K, E>::Get(TreeNode<std::pair<K, E>>* p, const K & k)
{
	if (!p) return nullptr;
	if (k < p->getData().first)	return this->Get(p->getLeftChild(), k);
	if (k > p->getData().first)	return this->Get(p->getRightChild(), k);

	return &p->getData();
}
#endif


template<typename K, typename E>
void BST<K, E>::destroy(TreeNode<std::pair<K, E>>* root)
{
	if (root->getLeftChild())
		this->destroy(root->getLeftChild());
	if (root->getRightChild())
		this->destroy(root->getRightChild());
	delete root;

	root->setLeftChild(nullptr);
	root->setRightChild(nullptr);
	root = nullptr;
}

main.cpp

#include <iostream>

#include <vector>
#include <utility>

#include "BST.h"

int main(void)
{
	std::vector<std::pair<int, int>> data;
	BST<int, int> bst;
	
	for (int i = 0; i < 8; i++)
	{
		auto v = std::pair<int, int>(i, 0);
		data.push_back(v);
		bst.Insert(v);
	}

	for (int i = 0; i < 10; i++, [&]() {
		auto o = bst.Get(i);
		if (o == nullptr)
			std::cout << "없어요" << std::endl;
		else
			std::cout<< o->first << std::endl;
	}());


	return 0;
}

TreeNode.h

#pragma once

template <typename T> class TreeNode
{
public:
	TreeNode() : leftChild(nullptr), rightChild(nullptr) {}
	~TreeNode(){}

public:
	T& getData(void);
	TreeNode<T> *getLeftChild(void);
	TreeNode<T> *getRightChild(void);

public:
	void setData(T& data);
	void setLeftChild(TreeNode<T> *left);
	void setRightChild(TreeNode<T>* right);

private:
	T data;
	TreeNode<T> *leftChild;
	TreeNode<T> *rightChild;
};

template <typename T> 
T& TreeNode<T>::getData(void)
{
	return this->data;
}

template <typename T> 
TreeNode<T> *TreeNode<T>::getLeftChild(void)
{
	return this->leftChild;
}

template <typename T>
TreeNode<T> *TreeNode<T>::getRightChild(void)
{
	return this->rightChild;
}

template<typename T>
void TreeNode<T>::setData(T & data)
{
	this->data = data;
}

template<typename T>
void TreeNode<T>::setLeftChild(TreeNode<T>* left)
{
	this->leftChild = left;
}

template<typename T>
void TreeNode<T>::setRightChild(TreeNode<T>* right)
{
	this->rightChild = right;
}

recursive <-> iterative