目录
前言
什么是二叉排序树
二叉排序树的特点
二叉排序树示意图
构建二叉排序树
插入元素
搜索元素
删除元素
完整代码
结尾
前言
在整个十一月,笔者因为一些原因停笔了,但马上迈入12月进而进入2025年,笔者决定不再偷懒了,继续更新以促进学习的积极性.闲话说到这,今天更新的是如何构建一个简单的二叉排序树
什么是二叉排序树
二叉排序树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它的每个节点都满足以下性质：
- 左子树上所有节点的值，都小于根节点的值。
- 右子树上所有节点的值，都大于根节点的值。
- 左子树和右子树本身也都是二叉排序树（递归定义）。
二叉排序树的特点
- 值的唯一性：二叉排序树中每个节点的值必须是唯一的（不允许重复值）。
- 有序性：中序遍历（左-根-右）二叉排序树时，会得到一个递增的有序序列。
- 动态性：支持动态插入和删除元素，能够随时维护有序性。
- 时间复杂度：平均情况下插入、查找、删除的时间复杂度为 O(logn),但在极端情况下（树退化为链表），复杂度可能退化到 O(n)。
举个例子
二叉排序树示意图
假设我们依次插入以下数字：50, 30, 70, 20, 40, 60, 80
构造的二叉排序树如下：
50
/ \
30 70
/ \ / \
20 40 60 80
此时,中序遍历二叉树,即可得到顺序排列.
构建二叉排序树
想要写一棵简单的二叉排序树,大致需要三个方法,分别是 插入结点,查找结点,删除结点
我们首先创建好结点类
static class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root;插入元素
插入元素是比较简单的,思路如下:
1. 首先判断树是不是空的,如果是空的,插入元素即为根
2. 如果不是空的,那么就借助双亲结点,去找需要插入结点的位置,然后再和双亲结点比较,看看左子树还是右子树
public boolean insert(int val)
{
if(root==null)
{
root=new TreeNode(val);
return true;
}
TreeNode parent=null;
TreeNode cur=root;
while(cur!=null)
{
if(cur.val>val)
{
parent=cur;
cur=cur.left;
} else if (cur.val<val) {
parent=cur;
cur=cur.right;
}
else
// 如果是等于就不能插入了,二叉排序树没办法容纳一样的key
{
return false;
}
}
if(parent.val>val)
{
parent.left=new TreeNode(val);
}
else
{
parent.right=new TreeNode(val);
}
return true;
}***************** 需要注意的是,二叉排序树不能插入重复的元素.*********************
搜索元素
搜索元素也很简单,因为二叉排序树本身就是为了提高搜索效率而产生的,
public boolean search(int key)
{
TreeNode cur=root;
while(cur!=null)
{
if(cur.val>key)
{
cur=cur.left;
}
else if(cur.val<key)
{
cur =cur.right;
}
else
{
return true;
}
}
return false;
}删除元素
删除元素是比较难的,如果笔者自己想想就会发现,好像有好多种情况要去想,这里笔者也不绕弯子,前辈们已经替我们总结出来了,大致会有三种情况
但在分情况之前 首先:设待删除结点为 cur, 待删除结点的双亲结点为 parent, 其次,要确定,待删除结点是否存在.
public boolean remove(int val)
{
TreeNode parent=null;
TreeNode cur=root;
while(cur!=null)
{
if(cur.val>val)
{
parent=cur;
cur=cur.left;
}
else if(cur.val<val)
{
parent=cur;
cur =cur.right;
}
else
{
// 找到了
removeNode(cur,parent);
return true;
}
}
return false;
}接下来我们完善 removeNode
第一种情况,待删结点没有左子树
这种情况,我们就让它的右子树结点和双亲结点连接上就好了.
但也有个前提,他不是根节点,所以要考虑到这一点
代码如下:
if(cur.left==null)
// 左边为空
{
if(cur==root)
{
root=root.right;
return;
}
else if(cur==parent.left)
{
parent.left=cur.right;
return ;
}
else
{
parent.right=cur.right;
return ;
}
}如果是双亲结点的左子树,就是 parent.left=cur.right;
如果是双亲结点的右子树,就是 parent.right=cur.right;
第二种情况,待删结点没有右子树
同理,代码如下
else if (cur.right==null)
// 右边为空
{
if(cur==root)
{
root=root.left;
}
else if(cur==parent.left)
{
parent.left=cur.left;
}
else
{
parent.right=cur.left;
}
}第三种,左右都不为空
我们的思路:
1.找到 cur
2.找cur左子树最右边的或者cur右子树最左边的,来替换我们的这个cur结点
3.替换完成以后,再把结点删除,请注意,有两种可能.如图所示
else{
TreeNode ansparent = cur;
TreeNode ans = cur.right;
// 去找右子树最左边的
while(ans.left!=null)
{
ansparent=ans;
ans=ans.left;
}
// 找到以后,也要分情况
cur.val=ans.val;
if(ansparent.left == ans)
{
ansparent.left = ans.right;
}
else
{
ansparent.right=ans.right;
}
}完整代码
package searchtree;
public class SearchTree
// 二叉搜索树
{
static class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root;
public boolean search(int key)
{
TreeNode cur=root;
while(cur!=null)
{
if(cur.val>key)
{
cur=cur.left;
}
else if(cur.val<key)
{
cur =cur.right;
}
else
{
return true;
}
}
return false;
}
public boolean insert(int val)
{
if(root==null)
{
root=new TreeNode(val);
return true;
}
TreeNode parent=null;
TreeNode cur=root;
while(cur!=null)
{
if(cur.val>val)
{
parent=cur;
cur=cur.left;
} else if (cur.val<val) {
parent=cur;
cur=cur.right;
}
else
// 如果是等于就不能插入了,二叉排序树没办法容纳一样的key
{
return false;
}
}
if(parent.val>val)
{
parent.left=new TreeNode(val);
}
else
{
parent.right=new TreeNode(val);
}
return true;
}
public boolean remove(int val)
{
TreeNode parent=null;
TreeNode cur=root;
while(cur!=null)
{
if(cur.val>val)
{
parent=cur;
cur=cur.left;
}
else if(cur.val<val)
{
parent=cur;
cur =cur.right;
}
else
{
// 找到了
removeNode(cur,parent);
return true;
}
}
return false;
}
private void removeNode(TreeNode cur, TreeNode parent)
{
if(cur.left==null)
// 左边为空
{
if(cur==root)
{
root=root.right;
return;
}
else if(cur==parent.left)
{
parent.left=cur.right;
return ;
}
else
{
parent.right=cur.right;
return ;
}
}
else if (cur.right==null)
// 右边为空
{
if(cur==root)
{
root=root.left;
}
else if(cur==parent.left)
{
parent.left=cur.left;
}
else
{
parent.right=cur.left;
}
}
// 左右都不为空
// 思路
// 1.找到 cur
// 2.找cur左子树最右边的或者cur右子树最左边的,来替换我们的这个cur结点
else{
TreeNode ansparent = cur;
TreeNode ans = cur.right;
// 去找右子树最左边的
while(ans.left!=null)
{
ansparent=ans;
ans=ans.left;
}
// 找到以后,也要分情况
cur.val=ans.val;
if(ansparent.left == ans)
{
ansparent.left = ans.right;
}
else
{
ansparent.right=ans.right;
}
}
}
}
结尾
这一篇算是我的笔记,所以写的会比较潦草,提前sorry了
