入门数据结构JAVADS——如何构建一棵简单二叉排序树

前言

什么是二叉排序树

二叉排序树的特点

二叉排序树示意图

构建二叉排序树

插入元素

搜索元素

删除元素

完整代码

结尾

前言

在整个十一月,笔者因为一些原因停笔了,但马上迈入12月进而进入2025年,笔者决定不再偷懒了,继续更新以促进学习的积极性.闲话说到这,今天更新的是如何构建一个简单的二叉排序树

什么是二叉排序树

二叉排序树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它的每个节点都满足以下性质：

左子树上所有节点的值，都小于根节点的值。
右子树上所有节点的值，都大于根节点的值。
左子树和右子树本身也都是二叉排序树（递归定义）。

二叉排序树的特点

值的唯一性：二叉排序树中每个节点的值必须是唯一的（不允许重复值）。
有序性：中序遍历（左-根-右）二叉排序树时，会得到一个递增的有序序列。
动态性：支持动态插入和删除元素，能够随时维护有序性。
时间复杂度：平均情况下插入、查找、删除的时间复杂度为 O(log⁡n),但在极端情况下（树退化为链表），复杂度可能退化到 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;}}}
}