#pragma once

#include 

using namespace std;

template

struct BsTreeNode{//二叉树 节点
	K _key;
	V _value;
	BsTreeNode* _left;
	BsTreeNode* _right;
	
	BsTreeNode(const K& key,const V& value)
		:_key(key)
		, _value(value)
		, _left(NULL)
		, _right(NULL)
	{}
};


template
class BsTree{

public:
typedef BsTreeNode Node;
	BsTree()
		: _root(NULL)
	{
	}

	~BsTree(){}

	bool Insert(const K& key, const V& value)//插入 非递归
	{
		if (_root == NULL){
			_root = new Node(key, value);
			return true;
		}
		Node* cur = _root;
		while (1){
			if (cur->_key > key)
			{
				if (cur->_left)
					cur = cur->_left;
				else{
					cur->_left = new Node(key, value);
					return true;
				}
			}
			else if (cur->_key < key)
			{
				if (cur->_right)
					cur = cur->_right;
				else{
					cur->_right = new Node(key, value);
					return true;
				}
			}//以上为找 插入位置 并插入
			else if (cur->_key == key)//存在  插入失败
				return false;
		}


	}

	bool InsertR(const K& key,const V& value)//插入 递归
	{
		return _InsertR(_root,key,value);
	}

	Node* Find(const K& key){//查找
		Node * cur = _root;
		while (cur){
			if (cur->_key > key)
				cur = cur->_left;
			else if (cur->_key < key)
				cur = cur->_right;
			else
				return cur;
		
		}
		return NULL;
	}

	bool RemoveR(const K& key)//删除 递归
	{
		if (_root == NULL)
			return false;
		return _RemoveR(_root,key);
	}

	bool Remove(K key){//删除 非递归
		Node* cur=_root, *prev=NULL;
		while (cur){
			if (cur->_key > key)
			{
				prev = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				prev = cur;
				cur = cur->_right;
			}// 以上为 找到要删除的 节点
			else
			{
				if (cur->_left == NULL)//如果节点左或右为空，直接删除该节//点将之后的节点 连接在其父节点
				{
					if (prev == NULL)
					{
						_root = cur->_right;
					
					}
					else if (prev->_left == cur)
					{
						prev->_left = cur->_right;

					}
					else
						prev->_right = cur->_right;
				}

				else if (cur->_right == NULL)//同上 右为空
				{
					if (prev == NULL)
					{
						_root = cur->_left;
						delete cur;
					}
					else if (prev->_right == cur)
					{
						prev->_right = cur->_left;

					}
					else
						prev->_left = cur->_left;
				}
				else//如果左右都不为空 找右孩子最左 或 左孩子最右 节点替
				//代删除
				{

					prev = cur;
					cur = cur->_right;
					while (cur->_left){
						cur = cur->_left;
						
					}
					prev->_key = cur->_key;
					prev->_value = cur->_value;
					prev->_right =cur->_right;
					
				}

				delete cur;
				return true;
			}
		}
		return false;
	}
	bool modification(K key,V value){//修改
		
		Node* ret = Find(key);
		if (ret == NULL)
			return false;
		ret->_value = value;
		return true;

	}

private:
	bool _InsertR(Node* & root,const K& key,const V& value)//插入 递归函数
	{
		if (root == NULL)
		{
			root = new Node(key,value);
			return true;
		}

		if (root->_key == key)
			return false;
		else if (root->_key > key)
			return _InsertR(root->_left,key,value);
		else 
			return _InsertR(root->_right,key,value);
			
	}

	bool _RemoveR(Node* & root,const K& key)//删除 递归函数
	{
		if (root->_key < key)
			return _RemoveR(root->_right, key);
		if (root->_key>key)
			return _RemoveR(root->_left, key);
		if (root->_left == NULL)
		{
			Node* dev = root;
			root = root->_right;
			delete dev;
			return true;
		}
		else if (root->_right == NULL)
		{
			Node* dev = root;
			root = root->_left;
			delete dev;
			return true;
		}
		else
		{
			root->_key = root->_right->_key;
			root->_value = root->_right->_value;
			return _RemoveR(root->_right,root->_key);
		}
	}

	Node* _root;
};

分享名称：c++搜索二叉树/排序二叉树
分享网址：http://cdweb.net/article/jjchcp.html