当然还有以下这种传统写法

发布时间：2025-06-24 18:15:25  作者：北方职教升学中心  阅读量：478

bool _InsertR(Node*& root, const K& key){	if (root == nullptr)	{		root = new Node(key);		return true;	}	if (root->_key < key)	{		return _InsertR(root->_right, key);	}	else if (root->_key > key)	{		return _InsertR(root->_left, key);	}	else	{		return false;	}}

2.8删除函数

二叉搜索树的删除函数情况比较复杂，场景比较多。

2.7插入函数

插入的具体过程如下：

• 树为空，则直接新增节点，赋值给root指针；
• 树不空，按二叉搜索树性质查找插入位置，插入新节点。

  若待删除结点的右子树为空，那么找到待删除结点后，只需先让其父结点指向该结点的左孩子结点，然后再将该结点释放。

  注意：只能是待删除结点左子树当中值最大的结点，或是待删除结点右子树当中值最小的结点代替待删除结点被删除，因为只有这样才能使得进行删除操作后的二叉树仍保持二叉搜索树的特性。

  比如以下场景，要删除节点『 7』。

非递归方式： 

使用非递归方式实现二叉搜索树的插入函数时，找到插入位置后我们需要new新节点，然后将该节点与对应的父节点进行连接，所以我们需要定义一个parent指针，该指针用于标记待插入结点的父结点。左指针、

若是在二叉树当中没有找到待删除结点，则直接返回false表示删除失败即可，但若是找到了待删除结点，此时就有以下三种情况：

• 待删除结点的左子树为空（待删除结点的左右子树均为空包含在内）。

  //拷贝构造函数BSTree(const BSTree<K>& t){    _root = Copy(t._root);}//设置private限定，不要暴露该接口Node* Copy(Node* root){	if (root == nullptr)		return nullptr;	Node* newRoot = new Node(root->_key);	newRoot->_left = Copy(root->_left);	newRoot->_right = Copy(root->_right);	return newRoot;}

  ---

  2.4赋值运算符重载

  在之前数据结构的模拟实现中，一般对于赋值运算符这块我们已经学习了现代写法，直接swap即可。

3.2『 KV模型』

每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。

//传统写法const BSTree<K>& operator=(const BSTree<K>& t){	if (this != &t) //防止自己给自己赋值	{		_Destory(_root); //先将当前的二叉搜索树中的结点释放		_root = _Copy(t._root); //拷贝t对象的二叉搜索树	}	return *this; //支持连续赋值}

namespace key_value{	template<class K, class V>	struct BSTreeNode	{		typedef BSTreeNode<K, V> Node;		Node* _left;		Node* _right;		K _key;		V _value;		BSTreeNode(const K& key, const V& value)			:_left(nullptr)			,_right(nullptr)			,_key(key)			,_value(value)		{}};	template<class K, class V>	class BSTree	{		typedef BSTreeNode<K, V> Node;	public:		bool Insert(const K& key, const V& value)		{			if (_root == nullptr)			{				_root = new Node(key, value);				return true;			}			Node* parent = nullptr;			Node* cur = _root;			while (cur)			{				if (cur->_key < key)				{					parent = cur;					cur = cur->_right;				}				else if (cur->_key > key)				{					parent = cur;					cur = cur->_left;				}				else				{					return false;				}			}			cur = new Node(key, value);			if (parent->_key < key)			{				parent->_right = cur;			}			else			{				parent->_left = cur;			}			return true;		}		Node* Find(const K& key)		{			Node* cur = _root;			while (cur)			{				if (cur->_key < key)				{					cur = cur->_right;				}				else if (cur->_key > key)				{					cur = cur->_left;				}				else				{					return cur;				}			}			return nullptr;		}		bool Erase(const K& key)		{			Node* parent = nullptr;			Node* cur = _root;			while (cur)			{				if (cur->_key < key)				{					parent = cur;					cur = cur->_right;				}				else if (cur->_key > key)				{					parent = cur;					cur = cur->_left;				}				else				{					if (cur->_left == nullptr)					{						if (cur == _root)						{							_root = cur->_right;						}						else						{							if (cur == parent->_right)							{								parent->_right = cur->_right;							}							else							{								parent->_left = cur->_right;							}						}						delete cur;						return true;					}					else if (cur->_right == nullptr)					{						if (cur == _root)						{							_root = cur->_left;						}						else						{							if (cur == parent->_right)							{								parent->_right = cur->_left;							}							else							{								parent->_left = cur->_left;							}						}						delete cur;						return true;					}					else					{						// 替换法						Node* rightMinParent = cur;						Node* rightMin = cur->_right;						while (rightMin->_left)						{							rightMinParent = rightMin;							rightMin = rightMin->_left;						}						cur->_key = rightMin->_key;						if (rightMin == rightMinParent->_left)							rightMinParent->_left = rightMin->_right;						else							rightMinParent->_right = rightMin->_right;						delete rightMin;						return true;					}				}			}			return false;		}		void InOrder()		{			_InOrder(_root);			cout << endl;		}	private:		void _InOrder(Node* root)		{			if (root == nullptr)				return;			_InOrder(root->_left);			cout << root->_key << " ";			_InOrder(root->_right);		}	private:		Node* _root = nullptr;	};}

4.二叉树的性能分析

『 查找效率』代表了二叉搜索树中各个操作的性能，因为插入和删除操作都必须先查找。

//构造函数BSTree()	:_root(nullptr){}

bool _EraseR(Node*& root, const K& key){	if (root == nullptr) 		return false;	if (key < root->_key) //key值小于根结点的值		return _EraseR(root->_left, key); //待删除结点在根的左子树当中	else if (key > root->_key) //key值大于根结点的值		return _EraseR(root->_right, key); //待删除结点在根的右子树当中	else //找到了待删除结点	{		if (root->_left == nullptr) //待删除结点的左子树为空		{			Node* del = root; //保存根结点			root = root->_right; //根的右子树作为二叉树新的根结点			delete del; //释放根结点		}		else if (root->_right == nullptr) //待删除结点的右子树为空		{			Node* del = root; //保存根结点			root = root->_left; //根的左子树作为二叉树新的根结点			delete del; //释放根结点		}		else //待删除结点的左右子树均不为空		{			Node* minParent = root; //标记根结点右子树当中值最小结点的父结点			Node* minRight = root->_right; //标记根结点右子树当中值最小的结点			//寻找根结点右子树当中值最小的结点			while (minRight->_left)			{				//右子树中最小一定在最左面				minParent = minRight;				minRight = minRight->_left;			}			root->_key = minRight->_key; //将根结点的值改为minRight的值			//注意一个隐含条件：此时minRight的_left为空			if (minRight == minParent->_left) //minRight是其父结点的左孩子			{				minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树即可			}			else //minRight是其父结点的右孩子			{				minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树即可			}			delete minRight; //释放minRight		}		return true; //删除成功，返回true	}}bool EraseR(const K& key){	return _EraseR(_root, key); //删除_root当中值为key的结点}

template<class K>struct BSTreeNode{	BSTreeNode<K>* _left;	BSTreeNode<K>* _right;	K _key;	BSTreeNode(const K& key = 0)		:_left(nullptr)		, _right(nullptr)		, _key(key)	{}};

2.2构造函数

因为这里的构造不需要特定的要求，只需要构造一棵空树，即给root赋值为nullptr即可。

如果退化成单支树，二叉搜索树的性能就失去了。

非递归方式： 

bool Find(const K& key){	Node* cur = _root;	while (cur)	{		if (cur->_key < key)		{			cur = cur->_right;		}		else if (cur->_key > key)		{			cur = cur->_left;		}		else		{			return true;		}	}	return false;}

 递归方式：

bool FindR(const K& key){    return _FindR(_root, key);}//设置为private，不要暴露该接口bool _FindR(Node* root, const K& key){	if (root == nullptr)		return false;	if (root->_key < key)	{		return _FindR(root->_right, key);	}	else if (root->_key > key)	{		return _FindR(root->_left, key);	}	else	{		return true;	}}

思考：为什么要设计成子函数这种形式呢？

因为当外部调用FindR时，我们没法直接传递根节点『 根节点是private域』，所以我们需要通过FindR获取到*this从而获取到_root，然后再调用_FindR，_FindR设计的参数为root和key就可以实现逻辑了，包括后面的递归方式都是这个思路。