二叉搜索树详讲

目录

1. 二叉搜索树

1.1 二叉搜索树的概念

1.2 二叉搜索树的操作

 1.2.1 二叉树的查找

 1.2.2 二叉树的插入

 1.2.3  二叉树的删除

总结

1. 二叉搜索树

1.1 二叉搜索树的概念

二叉搜索树又被称为二叉排序树，它可能是一个空树，也可能是满足一下特征的二叉树：

• 若它的左子树不为空，则左子树的所有节点上的值都小于根节点上的值
• 若它的右子树不为空，则右子树的所有节点上的值都大于根节点上的值
• 它的左右子树也满足上述特征

这就是一个标准的二叉搜索树

1.2 二叉搜索树的操作

 1.2.1 二叉树的查找

    实现步骤：

• 从根节点出发开始查找，如果当前值比目标值要大，则在右子树上进行查找
• 如果当前值比目标值要小，则在左子树上进行查找
• 如果当前值等于目标值，则返回true
• 如果当走到了空节点仍没有找到，则返回false

让我们来看看代码是如何实现的：

1. 非递归写法

	bool Find(const K& val)
	{
        //从root开始查找
		Node* cur = root;
        //如果当cur为空，仍没有找到则返回false
		while (cur)
		{
            //比当前值小则在左子树查找
			if (cur->val > val)
			{
				cur = cur->left;
			}
            //比当前值大则在右子树查找
			else if (cur->val < val)
			{
				cur = cur->right;
			}
            //相等则直接返回true
			else
			{
				return true;
			}
		}
		return false;
	}

2. 递归写法

因为在类内不能直接传参，因此封装了一层函数

bool FindR(const K&val)
{
     return _FindR(root,val);
}
bool _FindR(Node*& root, const K& val)
{       
        //如果root为空则表示没有找到，返回空
		if (!root)
		{
			return false;
		}
        //如果小于模板值，则在左子树中查找
		if (root->val < val)
		{
			return _FindR(root->right, val);
		}
        //如果大于模板值，则在右子树中查找
		else if (root->val > val)
		{
			return _FindR(root->left, val);
		}
        //如果等于目标值，则返回true
		else
		{
			return true;
		}
}

1.2.2 二叉树的插入

实现步骤：

acm二叉搜索树参考代码

zip 0星 超过10%的资源 17KB

下载

• 如果树为空，则将插入的节点直接赋值给root
• 如果树不为空，则根据二叉搜索树的性质找到插入位置

 如果我们需要插入9这个节点，那么我们的步骤是什么呢？

1. 从根节点出发开始查找，如果当前值比9要大，则在右子树上进行查找
2. 如果当前值比9要小，则在左子树上进行查找
3. 如果当前值等于9，则返回false（当前设置不允许插入相同的元素）
4. 如果当走到了空节点，则此时就是要插入的位置

那我们的代码是怎么实现的呢？

1. 非递归写法

bool insert(const K& val)
	{
		//如果是空树
		if (!root)
		{
			root = new Node(val);
			return true;
		}
		//如果不是空树
		else
		{ 
            //需要建立一个父节点来链接插入的节点
			Node* parent = nullptr;
			Node* cur = root;
			while (cur)
			{
				if (cur->val < val)
				{
					parent = cur;
					cur = cur->right;
				}
				else if (cur->val > val)
				{
					parent = cur;
					cur = cur->left;
				}
				else
				{
					return false;
				}
			}
           //cur走到了空节点，也就是我们要插入的位置
			Node* newnode = new Node(val);
            //还需要判断插入的是左子树还是右子树
			if (parent->val < val)
			{
				parent->right = newnode;
			}
			else
			{
				parent->left = newnode;
			}
			return true;
		}
	}

2. 递归写法

bool InsertR(const K& val)
{
	return _InsertR(root, val);
}
 
bool _InsertR(Node*& root, const K& val)
{
		//如果为空，就是插入的位置
		if (!root)
		{
			root = new Node(val);
			return true;
		}
        //如果当前值小于目标值，则在左子树处查找位置
		if (root->val < val)
		{
			return _InsertR(root->right, val);
		}
        //如果当前值大于目标值，则在右子树处查找位置
		else if (root->val > val)
		{
			return _InsertR(root->left, val);
		}
        //如果当前值等于目标值,返回false
		else
		{
			return false;
		}
}

与普通的非递归写法不同的是，不需要判断要插入左子树还是右子树

 如果我们以递归写法来插入9这个值，我们会发现9最后要插入的位置就是10这个节点的左边，又因为root的10的左节点的别名，因此我们只需要将root的值赋成9这个节点即可

1.2.3  二叉树的删除

Java 实现二叉搜索树的查找、插入、删除、遍历

pdf 0星 超过10%的资源 108KB

下载

实现步骤：

1. 首先查找元素是否在二叉搜索树中，如果不存在，则返回false,
2. 否则要删除的结点可能分下面四种情况：

• 要删除的结点无孩子结点
• 要删除的结点只有左孩子结点
• 要删除的结点只有右孩子结点
• 要删除的结点有左、右孩子结点
   

而我们可以发现当无孩子结点这种情况也可以归纳在只有左结点或者右结点这个情况中

那么代码实现如下：

1. 非递归写法

bool erase(const K& val)
	{
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->val < val)
			{
				parent = cur;
				cur = cur->right;
			}
			else if (cur->val > val)
			{
				parent = cur;
				cur = cur->left;
			}
			//如果找到了目标值
			else
			{
                //记录一下删除的节点
				Node* del = cur;
				if (!cur->left)
				{
					if (!parent)
					{
						cur = cur->right;
					}
					else
					{
						if (parent->left == cur)
						{
							parent->left = cur->right;
						}
						else
						{
							parent->right = cur->right;
						}
					}
					delete del;
				}
				else if (!cur->right)
				{
					if (!parent)
					{
						cur = cur->left;
					}
					else
					{
						if (parent->left == cur)
						{
							parent->left = cur->left;
						}
						else
						{
							parent->right = cur->left;
						}
					}
					delete del;
				}
				//左右子树都不为空
				else
				{
					Node* minparent = cur;
					Node* minright = cur->right;
					//找到右子树的最小值
					while (minright->left)
					{
						minparent = minright;
						minright = minright->left;
					}
					//交换最小值和目标值的大小
					swap(cur->val, minright->val);
				    
					if (minparent->left == minright)
					{
						minparent->left = minright->right;
					}
					else
					{
						minparent->right = minright->right;
					}
					//删除替换的节点
					delete minright;
				}
				return true;
			}
		}
		return false;
	}

2. 递归写法

bool EraseR(const K& val)
{
		return _EraseR(root, val);
}
bool _EraseR(Node*& root, const K& val)
{
		//如果为空，则说明目标值不存在，返回false
		if (!root)
		{
			return false
		}
 
		if (root->val < val)
		{
			return _EraseR(root->right, val);
		}
		else if (root->val > val)
		{
			return _EraseR(root->left, val);
		}
		//找到目标结点
		else
		{
			//如果左子树为空
			if (!root->left)
			{
				root = root->right;
			}
			else if (!root->right)
			{
				root = root->left;
			}
			else
			{
				Node* minright = root->right;
				while (minright->left)
				{
					minright = minright->left;
				}
				swap(root->val, minright->val);
 
				return _EraseR(root->right, minright->val);
			}
		}
}

总结

递归写法和非递归写法的区别：

1. 递归写法在删除和插入操作中不需要去判断目标值为其父值的左子树还是右子树
2. 递归写法突出的就是代码量少
3. 如果二叉搜索树不太均匀，递归写法可能会造成栈溢出

   ---