这是一棵适合搜索二叉树

template<class K, class V>
struct BSTreeNode
{
	BSTreeNode(const K& key = K(), const V& value = V())
		: _left(nullptr), _right(nullptr), _key(key), _value(value)
	{}
	BSTreeNode<K,V>* _left;
	BSTreeNode<K,V>* _right;
	K _key;							//关键码,用于比较大小的,按key比较
	V _value;						//用于存储数据
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;		//注意这里的类型重命名
public:
	bool Insert(const K& key, const V& value);
	Node* Find(const K& key);
	bool Erase(const K& key);
	void _InOrder(Node* root);
	void InOrder();
private:
	Node* _root = nullptr;
};

//插入操作
template<class K, class V>
bool BSTree<K,V>::Insert(const K& key, const V& value)
{
	//如果是空树,则直接赋值给根节点
	if (_root == nullptr)
	{
		//没看清node结构的,可以翻到上面在看一下构造函数.
		_root = new Node(key,value);	//用值构建结点,并赋给根节点
		return true;
	}

	//如果不是 空树
	Node* cur = _root;			//代替根节点遍历树,寻找插入位置.
	Node* pnode = nullptr;		//记录目标位置的父亲结点
	while (cur)				//一直找到nullptr为止
	{
		pnode = cur;				//更新父节点
		if (key > cur->_key)		//如果插入的键值对 key 比当前元素的key大,则往右走
		{
			cur = cur->_right;
		}
		else if (key < cur->_key)		//如果插入的值比当前元素小,则往左走
		{
			cur = cur->_left;
		}
		else return false;			//相等则返回false
	}

	//判断插入在左边还是右边
	Node* newnode = new Node(key, value);
	if (key < pnode->_key)
	{
		pnode->_left = newnode;
	}
	else
	{
		pnode->_right = newnode;
	}
	return true;
}

template<class K, class V>
typename BSTree<K,V>::Node* BSTree<K, V>::Find(const K& key)
{
	Node* cur = _root;			//代替根节点遍历树.
	while (cur)
	{
		if (key > cur->_key)		//如果查找的值比当前元素大,则往右走
		{
			cur = cur->_right;
		}
		else if (key < cur->_key)		//如果查找的值比当前元素小,则往左走
		{
			cur = cur->_left;
		}
		else return cur;			//相等则说明找到了
	}
	return nullptr;
}

template<class K, class V>
bool BSTree<K, V>::Erase(const K& key)
{
	if (_root == nullptr)
	{
		cout << "空树不可删除" << endl;//空树无法删除
		return false;
	}

	//寻找目标结点的位置

	Node* pnode = nullptr;		//记录当前结点的父亲结点
	Node* cur = _root;			//当前结点:代替根节点遍历树.

	//寻找目标结点
	while (cur)
	{

		if (key > cur->_key)		//如果插入的值比当前元素大,则往右走
		{
			pnode = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)		//如果插入的值比当前元素小,则往左走
		{
			pnode = cur;
			cur = cur->_left;
		}
		else  break;			//相等则说明找到了
	}

	//表示在树中 未找到
	if (cur == nullptr) { return false; }
	
	//这里采取与右子树的最小结点替换的方法
	if (cur->_right && cur->_left)//如果有两个孩子
	{
		Node* p_left_max = nullptr;			//右树 的最小节点的父亲
		Node* left_max = cur->_right;		//右树 的最小节点
		//寻找目标结点 右树 的最小节点
		while (left_max->_left)
		{
			p_left_max = left_max;
			left_max = left_max->_left;
		}
		//替换
		cur->_key = left_max->_key;		//其实覆盖即可
		cur->_value = left_max->_value;

		//将原右子树的最小结点的父亲与 右树最小结点断绝关系
		p_left_max->_left = nullptr;
		delete left_max;					//删除右树最小结点
		return true;
	}

	// 要删除的节点只有一个子节点或没有子节点
	Node* child = nullptr;
	//这样child就是孩子
	if (cur->_left)	//只有左孩子
	{
		child = cur->_left;
	}
	else//只有右孩子或者没有孩子
	{
		child = cur->_right;
	}

	if (pnode == nullptr) // 根节点要删除的情况
		_root = child;
	else if (pnode->_left == cur) // 要删除的节点是父节点的左子节点
		pnode->_left = child;
	else // 要删除的节点是父节点的右子节点
		pnode->_right = child;
	delete cur;
	return true;
}

template<class K, class V>
void  BSTree<K, V>::InOrder()
{
	if (_root == nullptr)
	{
		cout << "空树" << endl;
		return;
	}
	_InOrder(_root);		//这里调用即可
}

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:

	void _InOrder(Node* root);
	void InOrder();
private:
	Node* _root = nullptr;
};

template<class K, class V>
void  BSTree<K, V>::_InOrder(Node* root)
{
	if (root == nullptr)return;
	_InOrder(root->_left);
	cout << root->_key << "->" << root->_value << endl;
	_InOrder(root->_right);
}