数据结构-二叉搜索树

#PRagma once//K/V模型(key/value) //运用：英汉互译  template<typename K, typename V>struct SearchBinaryTreeNode{	SearchBinaryTreeNode<K,V>* _left;	SearchBinaryTreeNode<K,V>* _right;	const K _key;  //eg：英译汉	V _value;	SearchBinaryTreeNode(const K& key, const V& value)		: _left(NULL)		, _right(NULL)		, _key(key)		, _value(value)	{}};template<typename K, typename V>class SearchBinaryTree{	typedef SearchBinaryTreeNode<K,V> Node;public:	SearchBinaryTree()		:_root(NULL)	{}	~SearchBinaryTree()	{		_Destory(_root);	}	/*bool Insert(const K& key)	{	Node* prev = NULL;	Node* cur = _root;	while (cur)	{	if (key < cur->_key)	{	prev = cur;	cur = cur->_left;	}	else if (key > cur->_key)	{	prev = cur;	cur = cur->_right;	}	else	{	return false;	}	}	if (_root != NULL)	{	if (key < prev->_key)	{	prev->_left = new Node(key);	}	else	{	prev->_right = new Node(key);	}	}	else	{	_root = new Node(key);	}	return true;	}*/	bool Insert(const K& key,const V& value)  //非递归实现插入	{		Node* cur = _root;		Node* node = new Node(key,value);		while (cur)		{			if (key < cur->_key)			{				if (cur->_left == NULL)				{					cur->_left = node;					return true;				}				else				{					cur = cur->_left;				}			}			else if (key > cur->_key)			{				if (cur->_right == NULL)				{					cur->_right = node;					return true;				}				else				{					cur = cur->_right;				}			}			else			{				return false;			}		}		_root = node;		return true;	}	bool Remove(const K& key)//非递归实现删除	{		Node* parent = NULL;		Node* cur = _root;		while (cur)		{			if (cur->_key == key)//已找到要删除的节点			{				if (cur->_left == NULL)//左为空				{					if (cur == _root)					{						_root = _root->_right;					}					else if (parent->_left == cur)					{						parent->_left = cur->_right;					}					else if (parent->_right == cur)					{						parent->_right = cur->_right;					}				}				else if (cur->_right == NULL)//右为空				{					if (cur == _root)//防止斜树删除根节点时parent为NULL导致奔溃					{						_root = _root->_left;					}					else if (parent->_left == cur)					{						parent->_left = cur->_left;					}					else if (parent->_right == cur)					{						parent->_right = cur->_left;					}				}				else if (cur->_right != NULL && cur->_left != NULL)//左右都不为空				{					Node* rightmin = cur->_right;//要删除节点的右子树的最左节点（最小的）					parent = cur;					while (rightmin->_left)//找要删除节点的右子树的最左节点（最小的）					{						parent = rightmin;						rightmin = rightmin->_left;					}					//替换					cur->_key = rightmin->_key;					//假删除					if (parent->_left == rightmin)					{						parent->_left = rightmin->_right;					}					else if (parent->_right == rightmin)					{						parent->_right = rightmin->_right;					}					cur = rightmin;				}				break;			}			else if (cur->_key < key)			{				parent = cur;				cur = cur->_right;			}			else			{				parent = cur;				cur = cur->_left;			}		}		delete cur;		cur = NULL;		return true;	}	Node* Find(const K& key)  //非递归实现查找	{		Node* cur = _root;		while (cur)		{			if (key == cur->_key)			{				return cur;			}			else if (key < cur->_key)			{				cur = cur->_left;			}			else			{				cur = cur->_right;			}		}		return NULL;	}	Node* FindR(const K& key)	{		return _FindR(_root, key);	}	bool InsertR(const K& key,const V& value)	{		return _InsertR(_root, key, value);	}	bool RemoveR(const K& key)	{		return _RemoveR(_root, key);	}	void InOrder()	{		_InOrder(_root);		cout << endl;	}	size_t Size()	{		return _Size(_root);	}protected:	Node* _FindR(Node* root, const K& key)	{		if (root == NULL)			return NULL;		if (root->_key > key)		{			return _FindR(root->_left, key);		}		else if (root->_key < key)		{			return _FindR(root->_right, key);		}		else		{			return root;		}	}	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 _InsertR(root->_left, key, value);		}		else if (root->_key < key)		{			return _InsertR(root->_right, key, value);		}		else		{			return false;		}	}	bool _RemoveR(Node*& root, const K& key)//注意第一个参数加&的道理	{		if (root == NULL)			return false;		if (root->_key > key)			return _RemoveR(root->_left, key);		else if (root->_key < key)			return _RemoveR(root->_right, key);		else		{			Node* del = NULL;			if (root->_left == NULL)			{				del = root;				root = root->_right;  //等号左边root表示上一层递归中root的left指针的别名，右边的root代表当前root节点的右指针所指的节点			}			else if (root->_right == NULL)			{				del = root;				root = root->_left;			}			else			{				Node* parent = root;				Node* newnode = root->_right;  //找root为根其右子树的最左节点				while (newnode->_left)				{					parent = newnode;					newnode = newnode->_left;				}				root->_key = newnode->_key;				del = newnode;				if (newnode == parent->_left)				{					parent->_left = newnode->_right;				}				else if (newnode == parent->_right)				{					parent->_right = newnode->_right;				}			}			delete del;			return true;		}	}	void _InOrder(Node* root)	{		if (root == NULL)		{			return;		}		_InOrder(root->_left);		cout << root->_key << " ";		_InOrder(root->_right);	}	size_t _Size(Node* _root)	{		if (_root == NULL)			return 0;		return _Size(_root->_left) + _Size(_root->_right) + 1;	}	void _Destory(Node* root)	{		if (root == NULL)			return;		_Destroy(root->_left);		_Destroy(root->_right);		delete root;	}protected:	Node* _root;};