本文共 8684 字，大约阅读时间需要 28 分钟。

引言

公众号原文链接：  希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

完整项目我已经上传到我的码云git仓库上了，如果就需要的话请访问我的码云git仓库获取，附上地址：。或者点击公众号底部菜单->资源汇总->仓库汇总。或者联系我。

 

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
   
     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
    
      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}

 

生成的图片如下。

 

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

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

 

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

 

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

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

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

 

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

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

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

 

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

 

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

1. 如果删除的是叶子结点，则直接删除该结点，不会对树的结构造成影响

2. 如果删除的结点只有一个孩子，则会对树的结构造成影响，但也还好办，将被删除的结点替换为该节点的孩子即可

3. 如果删除的结点左右孩子都有，那情况就有点复杂了，稍有不慎就会破坏树的结构使之不满足二叉查找树的定义。

 

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

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

下面用图来描述一下。

 

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

 

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方法，生成的图片如下，这正是我们想要的结果。

 

 

 

 

 

我的二维码

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

 

转载地址：http://wvpkf.baihongyu.com/