教你玩转二叉查找树的结点插入和删除操作

红太狼 2023-01-09 06:27 80阅读 0赞

### 引言 ###

公众号原文链接：[教你玩转二叉查找树的结点插入操作][Link 1] [压轴出场-二叉查找树的结点删除操作][-] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

完整项目我已经上传到我的码云git仓库上了，如果就需要的话请访问我的码云git仓库获取，附上地址：[https://gitee.com/bobo\_tea/datastructure][https_gitee.com_bobo_tea_datastructure]。或者点击公众号底部菜单->资源汇总->仓库汇总。或者联系我。

### 1、二叉查找树的结点插入 ###

现有只有一个结点的二叉查找树，该结点的值为50，现在我要往这颗二叉查找树依次插入9个结点：42,57,13,72,47,65,88,93,26。

这个就是典型的二叉查找树的插入操作了，最后生成的树一共有10个结点，插入过程中不能违背二叉查找树的定义，即每插入一个结点后它仍然是一颗二叉查找树。

下面展示一下用Java代码实现二叉查找树的插入操作核心代码。

**ADTInsert，插入操作核心实现类**

import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 二叉查找树结点插入操作类
     */
    public class ADTInsert {
    
        /**
         * 存放插入的结点
         * 这种插入算法最终会将要插入的值会生成一个叶子结点，也就是说不会破坏原来树的结构，虽然简单，但会导致树越来越不平衡
         */
        private List<ADTNode> insertNodes = new ArrayList();
    
        /**
         * 插入操作核心方法
         * @param adtNode 从该结点开始搜索
         * @param key 要插入的值
         */
        private void insert(ADTNode adtNode,int key){
            // 如果节点指针是null，就没法插入，直接返回
            if(adtNode == null){ return; }
    
            if(key < adtNode.getVal()){
                // 作为左孩子，找一个叶子结点插入
                if(adtNode.getLeft() == null){
                    adtNode.setLeft(new ADTNode(key));
                    insertNodes.add(adtNode.getLeft());
                    return;
                }
                insert(adtNode.getLeft(),key);
            }
            if(key > adtNode.getVal()){
                // 作为右孩子，找一个叶子结点插入
                if(adtNode.getRight() == null){
                    adtNode.setRight(new ADTNode(key));
                    insertNodes.add(adtNode.getRight());
                    return;
                }
                insert(adtNode.getRight(),key);
            }
        }
    
    
        /**
         * 插入操作入口
         * @param root 从该结点开始搜索
         * @param keys 要插入的值数组
         */
        public void insertEntrance(ADTNode root,int[] keys){
            insertNodes.add(root);
            for (int key:keys){
                this.insert(root,key);
            }
        }
    
        public List<ADTNode> getInsertNodes() {
            return insertNodes;
        }
    
    }

**ADTMain，二叉查找树结点插入示例类**

import com.bobo.group.common.CommonUtil;
    import com.bobo.group.tree.draw.DrawTree;
    
    /**
     * 二叉查找树main方法
     */
    public class ADTMain {
    
        public static void main(String[] args) {
            //根结点
            ADTNode root = new ADTNode(50);
            ADTInsert adtInsert = new ADTInsert();
            //依次插入9个结点
            adtInsert.insertEntrance(root,new int[]{42,57,13,72,47,65,88,93,26});
            //遍历打印各结点
            adtInsert.getInsertNodes().forEach(item->{
                System.out.println(item == null?"null":item.toString());
            });
            //生成二叉树图片
            DrawTree drawTree = new DrawTree();
            drawTree.drawEntrance(root, CommonUtil.getResourceRoot() +"tree/adt/insert_10.png",10);
          
        }
    }

运行main方法，输出结果如下。

ADTNode{val=50, left=42, right=57}
    ADTNode{val=42, left=13, right=47}
    ADTNode{val=57, left=null, right=72}
    ADTNode{val=13, left=null, right=26}
    ADTNode{val=72, left=65, right=88}
    ADTNode{val=47, left=null, right=null}
    ADTNode{val=65, left=null, right=null}
    ADTNode{val=88, left=null, right=93}
    ADTNode{val=93, left=null, right=null}
    ADTNode{val=26, left=null, right=null}

生成的图片如下。

![图片][90c3c03f0ffac95631a851f11a3f1f22.png]

如果中序遍历这棵树的话，其结果是一个从小到大排好序的序列。

但是有没有觉得这棵树的形状有点奇怪，看起来有点斜（主要是右边）、有点不平衡。

其实二叉查找树的极端恶劣的情况就是一颗斜树，如下图所示。

![图片][47883a6be338c3fd1bf030fee140b8aa.png]

这样的树也符合二叉查找树的定义，但无异于一个单链表，对查找速度并没有任何提升，因此，要避免二叉查找树出现过多的斜树。

而怎样才算一颗好的二叉查找树呢？当然是树的高度越小，查找速度越快。

上面代码中的插入算法，并不是一个好的插入算法，因为最后树的形状完全取决于结点的插入顺序，并且插入过程中不会改变树原来的结构，也就是说新插入的结点始终会被当成叶子结点插入。

比如现在二叉查找树只有一个值是50的结点，我要依次插入50,70,80,90四个结点，那最后生成的树就是一颗斜树，如下图所示。

![图片][e83820dfe4855b7d322fc1f301f1241d.png]

而如果我的插入算法足够好，那生成的树应该是下面这个样子，当然，插入的结点越多，效果差距越大。

![图片][add231b2f25cc15d42beb671044d9422.png]

本文暂不介绍好的插入算法，后面我会讲平衡二叉树来解决这个问题。

### 2、二叉查找树的结点删除 ###

前面介绍了二叉查找树的查找和插入，还算比较简单，因为它们均不会破坏树的结构。而二叉查找树的删除，可就不是那么简单了。

1.  如果删除的是叶子结点，则直接删除该结点，不会对树的结构造成影响
2.  如果删除的结点只有一个孩子，则会对树的结构造成影响，但也还好办，将被删除的结点替换为该节点的孩子即可
3.  如果删除的结点左右孩子都有，那情况就有点复杂了，稍有不慎就会破坏树的结构使之不满足二叉查找树的定义。

对于第三种情况，我们下面来探讨一下解决办法：

*  因为二叉查找树的中序遍历的结果是从小到大的，如果将其中某个结点删除，则可以用该结点的前驱或后继来替代该结点，使之仍然能保持二叉查找树的结构，用前驱代替还是用后继代替都可以。

下面用图来描述一下。

![图片][38ae839409aad1c6d25da13f741aa085.png]

算法大概就是这样，下面主要看实现过程吧，相比于查找和插入两种操作而言，删除操作的代码量比较大，也比较难于理解。

**ADTDelete,二叉查找树结点删除核心代码**

/**
     * 二叉查找树结点删除操作类
     */
    public class ADTDelete {
        /**
         * 是否使用前驱结点代替被删除结点
         */
        private static final boolean USE_BEFORE = true;
    
        /**
         * 删除操作入口
         */
        public void deleteEntrance(ADTNode adtNode,int key){
            //空树，不删除
            if(adtNode == null){
                return;
            }
            //删除根结点
            if(adtNode.getVal() == key){
                System.out.println("天啊，要删除根结点，暂不支持！");
                return;
            }
            searchForDelete(adtNode,key);
        }
    
        /**
         * 删除结点核心方法
         * @param parentNode 父结点
         * @param keyNode 要删除的结点
         * @param isLeft 是否是左孩子
         */
        private void delete(ADTNode parentNode,ADTNode keyNode,boolean isLeft){
            //叶子结点，删除轻而易举
            if(keyNode.getLeft() == null && keyNode.getRight()==null){
                if(isLeft){
                    parentNode.setLeft(null);
                }else{
                    parentNode.setRight(null);
                }
                return;
            }
    
            //只有一个孩子结点，删除也容易
            if(keyNode.getLeft() == null && keyNode.getRight()!=null){
                if(isLeft){
                    parentNode.setLeft(keyNode.getRight());
                }else{
                    parentNode.setRight(keyNode.getRight());
                }
                return;
            }
            if(keyNode.getLeft() != null && keyNode.getRight()==null){
                if(isLeft){
                    parentNode.setLeft(keyNode.getLeft());
                }else{
                    parentNode.setRight(keyNode.getLeft());
                }
                return;
            }
    
            //左右孩子都有，比较复杂
            if(keyNode.getLeft() != null && keyNode.getRight() != null){
                //先找到替代者，前驱和后继都可以是替代者
                //前驱要么是叶子结点，要么只有左子树；后继要么是叶子结点，要么只有右子树
    
                if(USE_BEFORE){
                    if(keyNode.getLeft().getRight() == null){
                        //备份右子树
                        ADTNode rightNode = keyNode.getRight();
                        //替换
                        keyNode = keyNode.getLeft();
                        //续接
                        keyNode.setRight(rightNode);
                    }else{
                        //先找到替代者的父亲
                        ADTNode maxBeforNodeParent = searchMaxForDelete( keyNode.getLeft());
                        //备份左子树、右子树
                        ADTNode leftNode = keyNode.getLeft();
                        ADTNode rightNode = keyNode.getRight();
                        ADTNode replacement = maxBeforNodeParent.getRight();
                        ADTNode replacementLeft = maxBeforNodeParent.getRight().getLeft();
                        //将替代者从原来的地方删除，并接上它的左孩子
                        maxBeforNodeParent.setRight(replacementLeft);
                        //替换
                        if(isLeft){
                            parentNode.setLeft(replacement);
                        }else{
                            parentNode.setRight(replacement);
                        }
                        //第四步：将被删除结点的左子树与右子树与替代者结点连接上
                        replacement.setLeft(leftNode);
                        replacement.setRight(rightNode);
                    }
                }else{
                    System.out.println("暂不支持替换后继");
                }
    
            }
        }
    
        /**
         * 查找前驱
         * @param adtNode 开从该结点开始搜索
         * @return 前驱结点的父亲
         */
        private ADTNode searchMaxForDelete(ADTNode adtNode){
            if(adtNode.getRight().getRight() != null){
                return searchMaxForDelete( adtNode.getRight());
            }
            return adtNode;
        }
    
        /**
         * 查找后继
         * @param adtNode 从该结点开始搜索
         * @return 后继结点的父亲
         */
        private ADTNode searchMinForDelete(ADTNode adtNode){
            if(adtNode.getLeft().getLeft() != null){
                return searchMaxForDelete( adtNode.getLeft());
            }
            return adtNode;
        }
    
        /**
         * 在二叉查找树上递归搜索要删除的结点，找到了就调用delete方法删除
         * @param adtNode 从该结点开始搜索
         * @param key 要删除的结点的值
         */
        private void searchForDelete(ADTNode adtNode,int key){
            if(key < adtNode.getVal()){
                if(adtNode.getLeft() == null){
                    System.out.println("死胡同了-找不到要删除的结点-"+key);
                    return;
                }
                if(key == adtNode.getLeft().getVal()){
                    //找到了，执行删除
                    delete(adtNode, adtNode.getLeft(),true);
                }else{
                    //否则，向下走一个结点
                    searchForDelete( adtNode.getLeft(),key);
                }
            }
            if(key > adtNode.getVal()){
                if(adtNode.getRight() == null){
                    System.out.println("死胡同了-找不到要删除的结点-"+key);
                    return;
                }
                if(key == adtNode.getRight().getVal()){
                    //找到了，执行删除
                    delete(adtNode,adtNode.getRight(),false);
                }else{
                    //否则，向下走一个结点
                    searchForDelete(adtNode.getRight(),key);
                }
    
            }
        }
    
    }

**ADTMain，二叉查找树删除示例代码**

import com.bobo.group.common.CommonUtil;
    import com.bobo.group.tree.draw.DrawTree;
    
    /**
     * 二叉查找树main方法
     */
    public class ADTMain {
        public static void main(String[] args) {
            ADTDelete adtDelete = new ADTDelete();
            ADTNode root = ADTBuilder.buildBySample_2();
            adtDelete.deleteEntrance(root,47);
            DrawTree drawTree = new DrawTree();
            drawTree.drawEntrance(root,CommonUtil.getResourceRoot()+"tree/adt/删除47.png",false);
        }
    }

运行main方法，生成的图片如下，这正是我们想要的结果。

![图片][a8961cb3b04f9aebdfe36bf9c2430c4e.png]

### 我的二维码 ###

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

![20210121085816775.jpg][]

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484614&idx=1&sn=597dfe696790b8ec23f4837f244259cc&chksm=ea307c04dd47f512ef00eb58723d14440fffc9b69ff563e0e880d100eec611499c17032af95e&token=1909849060&lang=zh_CN#rd
[-]: http://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484635&idx=1&sn=af44410aaae41779062b80afe9eaaa05&chksm=ea307c19dd47f50f4184b54c1c3f453035d6d0a5b45ab9c7b3d160fca3da6f6366262aaf7bf3&token=1909849060&lang=zh_CN#rd
[https_gitee.com_bobo_tea_datastructure]: https://gitee.com/bobo_tea/datastructure
[90c3c03f0ffac95631a851f11a3f1f22.png]: /images/20221119/fa6341cc26224c1c8532524f7cafae25.png
[47883a6be338c3fd1bf030fee140b8aa.png]: /images/20221119/a6252bc103c04c279ac6317bca4ee710.png
[e83820dfe4855b7d322fc1f301f1241d.png]: https://img-blog.csdnimg.cn/img_convert/e83820dfe4855b7d322fc1f301f1241d.png
[add231b2f25cc15d42beb671044d9422.png]: https://img-blog.csdnimg.cn/img_convert/add231b2f25cc15d42beb671044d9422.png
[38ae839409aad1c6d25da13f741aa085.png]: https://img-blog.csdnimg.cn/img_convert/38ae839409aad1c6d25da13f741aa085.png
[a8961cb3b04f9aebdfe36bf9c2430c4e.png]: https://img-blog.csdnimg.cn/img_convert/a8961cb3b04f9aebdfe36bf9c2430c4e.png
[20210121085816775.jpg]: https://img-blog.csdnimg.cn/20210121085816775.jpg