#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;
};

坚守“ 做人真诚 · 做事靠谱 · 口碑至上 · 高效敬业 ”的价值观，专业网站建设服务10余年为成都成都混凝土泵车小微创业公司专业提供成都企业网站定制营销网站建设商城网站建设手机网站建设小程序网站建设网站改版，从内容策划、视觉设计、底层架构、网页布局、功能开发迭代于一体的高端网站建设服务。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网站名称：c++搜索二叉树/排序二叉树-创新互联
转载注明：http://scyanting.com/article/dgisec.html