二叉树学习(二) BST插入,查找与删除

末蓝、 2022-03-19 11:23 254阅读 0赞

### 二叉排序树 ###

**定义**:大小关系:**左孩子<根<右孩子** 的二叉树  
**特点**:中序遍历得到有序序列(升序)  
节点的删除:无论是什么情况,都需要保证删除后的中序遍历结果仍然是有序  
比如删除前;a,b,c,d,e,f  
**如果删除c:需要保证删除c后,得到的中序遍历是a,b,d,e,f**

**删除大体分三种情况**:

1.  待删除节点无孩子(待删除节点是叶子节点),只需要将父节点将对应指针域置为null
2.  待删除节点有一个孩子(左孩子或者是右孩子):以左孩子为例,将父节点指向待删除的节点的指针指向待删除节点的孩子节点(这里是左孩子)
3.  待删除节点有两个孩子:这就比较麻烦,需要找到被删除节点的后继节点,将key值拷贝到被删除节点的数据域,然后删除被删除 节点的后继节点
4.  还有一点比较特殊的:如果待删除节点是根节点,那么删除后的的二叉树根是变化了

java 代码实现:  
BTreeNode.java 的定义,参见上一篇博文,[传送][Link 1]

### 1.构建排序二叉树: ###

/** * @author wangwei * @date 2019/2/15 16:18 * @classDescription 二叉排序树 * 定义:满足左<根<右关系的二叉树 */
    public class BST { 
        /** * 1.插入节点 */
        public static BTreeNode insertNode(BTreeNode tree, Integer newKey) { 
           if(null==tree){ 
               return new BTreeNode(newKey);
           }
            //如果节点已经存在,则返回,不再插入
            if (null != searchNode(tree, newKey)) { 
                System.out.println("---- found ---" + newKey);
                return tree;
            }
            BTreeNode currNode = tree;
            BTreeNode preNode = null;
            BTreeNode newNode = new BTreeNode(newKey);
            while (currNode != null) { 
                preNode = currNode;
                //newKey 较小,往左子树查找
                if (newKey < (int) currNode.getData()) { 
                    currNode = currNode.getLChild();
                    //newKey较大,往右子树查找
                } else { 
                    currNode = currNode.getRChild();
                }
            }
            //处理节点插入:新节点应该是插入到preNode 的孩子位置,退出循环时是 currNode=null
            if (newKey < (int) preNode.getData()) { 
                preNode.setLChild(newNode);
                return tree;
            }
            preNode.setRChild(newNode);
            return tree;
    
        }

### 2 节点搜索 ###

/** * 2. 搜索节点 * * @param tree * @param targetKey * @return 搜索节点 */
        public static BTreeNode searchNode(BTreeNode tree, Integer targetKey) { 
    
            if (tree == null || tree.getData() == null) { 
                return null;
            }
            if (targetKey > (int) tree.getData()) { 
                return searchNode(tree.getRChild(), targetKey);
            }
            if (targetKey < (int) tree.getData()) { 
                return searchNode(tree.getLChild(), targetKey);
            }
            if(targetKey==(int)tree.getData()){ 
                return tree;
            }
            return null;
        }

### 3 节点删除 ###

节点的删除比较麻烦:

1.  如果被删除节点是叶子节点,或者是只有一个孩子,那么是很简单的
2.  如果被删除节点是有两个孩子,需要寻找后继,拷贝后继的值到被删除节点,然后实际是删除被删除节点的后继节点
3.  如果被删除节点是根节点,那么又得分上面的三种情况

具体java代码实现:

/** * @param tree * @param targetKey * @return 删除节点, 分为2种情况 * 1, 待删除节点是根节点(继续细分是否有左右孩子的请情况) * 2, 不是跟根节点 * 2.1, 待删除节点只有一个孩子,将父节点的对应孩子指针指向被删除节点的孩子 * 2.2,待删除节点有俩孩子(需要找到被删除节点的后继,将后继的值复制到被删除位置,然后删除后继节点 */
        public static BTreeNode deleteNode(BTreeNode tree, Integer targetKey) { 
    
            if (null == tree) { 
                throw new RuntimeException("不能在空树中删除节点");
            }
            BTreeNode targetNode = searchNode(tree, targetKey);
            if (null == targetNode) { 
                throw new RuntimeException("删除节点不存在");
            }
          
            //寻找被删除节点以及其对应的父节点
             BTreeNode parent = findParentNode(tree,targetKey);
            //如果父节点为null,这个是需要考虑的,表示待删除节点是根节点,那么删除之后后继将作为新的根节点
    
    
            //目前为止找到了待删除节点的父节点
            //需要注意的是 是左孩子还是右孩子
            //1.被删除节点是根节点
            if (null == parent) { 
                //System.out.println("删除节点是根节点,暂时未处理,需要后继节点值覆盖根节点值,然后删除后继节点");
                //1.1 根节点没有右孩子,删除根之后,返回左子树
                if (null == targetNode.getRChild()) { 
                    return targetNode.getLChild();
                }
                // 1.2 根节点没有左孩子,返回右子树
                if (null == targetNode.getLChild()) { 
                    return targetNode.getRChild();
                }
                   //1.3 左右孩子都有,需要查找根节点的后继,将后继的值复制到根节点,同时删除后继节点
                BTreeNode rChild = targetNode.getRChild();
                BTreeNode mostLChild =findSuccessorNode(targetNode);
                BTreeNode mostLChildParent = findParentNode(mostLChild,(int)mostLChild.getData());
                targetNode.setData(mostLChild.getData());
                if (mostLChildParent != null) { 
                    mostLChildParent.setLChild(null);
                } else { 
                    //处理根节点的右孩子没有左子树
                    targetNode.setRChild(rChild.getRChild());
                }
                return targetNode;
            }
    
    
            BTreeNode lChild = parent.getLChild();
            BTreeNode rChild = parent.getRChild();
            //2,处理被删除节点只有一个孩子的情况
            //左孩子节点是被删除节点
            if (lChild != null && lChild.getData().equals(targetKey)) { 
                BTreeNode lLChild = lChild.getLChild();
                BTreeNode lRChild = lChild.getRChild();
                //被删除节点无孩子
                //2.1 被删除节点无孩子
                boolean noChild = (null == lRChild && null == lLChild);
                if (noChild) { 
                    parent.setLChild(null);
                    return tree;
                }
                //2.2被删除节点只有一个孩子
                boolean onlyOneChild = null == lRChild ^ null == lLChild;
                if (onlyOneChild) { 
                    parent.setLChild(null == lRChild ? lLChild : lRChild);
                    return tree;
                }
                // 2.3 被删除节点有两个孩子
                //被删除节点有两个孩子 根据排序二叉树的特性 中序遍历是升序排列,那么删除节点后仍然需要满足升序排列
                //也就是需要找被删除节点的后继作为被删除节点的前驱的后继 ,使用这样找到的节点去替换被删除节点的值,然后删除找到的那个节点
                // 被删除节点的后继应该是 该节点的右孩子的最左孩子
                BTreeNode mostLChild = findSuccessorNode(lChild);// 查找被删除节点的后继
                BTreeNode mostLChildParent = findParentNode(tree,(int)mostLChild.getData());//最左孩子的父节点(被删除节点的后继的父节点)
    
                //将 后继(最左孩子mostLChild)的值拷贝到 被删除节点位置
                //同时删除最左孩子
                lChild.setData(mostLChild.getData());
                if (mostLChildParent != null) { 
                    mostLChildParent.setLChild(null);
                } else { 
                    //这是处理 被删除节点右孩子没有最左子节点的情况,后继就是被删除节点的右孩子
                    lChild.setRChild(lRChild.getRChild());
                }
                return tree;
            }
            //3,待删除节点是右孩子,需要找到被删除节点的右孩子的最左孩子
            if (rChild != null && rChild.getData().equals(targetKey)) { 
    
                BTreeNode rLChild = rChild.getLChild();
                BTreeNode rRChild = rChild.getRChild();
                //3.1 被删除节点无孩子
                boolean noChild = (null == rLChild && null == rRChild);
                if (noChild) { 
                    parent.setRChild(null);
                    return tree;
                }
                //3.2 被删除节点 只有一个孩子
                boolean onlyOneChild = null == rLChild ^ null == rRChild;
                if (onlyOneChild) { 
                    parent.setRChild(null == rLChild ? rRChild : rLChild);
                    return tree;
                }
                // 处理被删除节点带两个孩子节点的情况
                // 3.3 被删除节点有两个孩子
                //被删除节点有两个孩子 根据排序二叉树的特性 中序遍历是升序排列,那么删除节点后仍然需要满足升序排列
                //也就是需要找被删除节点的后继作为被删除节点的前驱的后继 ,使用这样找到的节点去替换被删除节点的值,然后删除找到的那个节点
                // 被删除节点的后继应该是 该节点的右孩子的最左孩子
                BTreeNode mostLChild = findSuccessorNode(rChild);
                BTreeNode mostLChildParent = findParentNode(tree,(int)mostLChild.getData());//后继节点的父节点
                //将 后继(最左孩子mostLChild)的值拷贝到 被删除节点位置
                //同时删除最左孩子
                rChild.setData(mostLChild.getData());
                if (mostLChildParent != null) { 
                    mostLChildParent.setLChild(null);
                } else { 
                    //这是处理 被删除节点的右孩子没有左孩子的情况,那么被删除节点的后继就是被删除节点的右孩子
                    //由于将后继的值拷贝到被删除节点位置了,那么就需要将被删节点的右孩子指向
                    // 原本被删节点的右孩子的右孩子
                    rChild.setRChild(rRChild.getRChild());
                }
                return tree;
            }
            return tree;
        }
    
        /** * 查找key节点的父节点 * * @param root * @param key * @return */
        public static BTreeNode findParentNode(BTreeNode root, Integer key) { 
            if (null == root) { 
                return null;
            }
            if(null==searchNode(root,key)){ 
                throw new RuntimeException("节点不存在");
            }
            BTreeNode parent = null;
            BTreeNode currNode = root;
            while (currNode != null && !currNode.getData().equals(key)) { 
                parent = currNode;
                currNode = key > (int) currNode.getData() ? currNode.getRChild() : currNode.getLChild();
            }
           return parent;
        }
    
        /** * 查找后继节点(中序遍历中的后继节点:即右孩子的最左孩子) * @param startPoint * @return */
        public static BTreeNode findSuccessorNode(BTreeNode startPoint){ 
            if(null==startPoint){ 
                return null;
            }
            BTreeNode successorNode=startPoint.getRChild();
            while (successorNode!=null && successorNode.getLChild()!=null ){ 
                successorNode=successorNode.getLChild();
            }
            return successorNode;
        }

### 4测试代码: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]

#### 测试用例: ####

以下均是通删除节点之后,检查中序遍历结果是否为升序,来判断是否操作成功.

1.  删除10(根节点)  
    ![在这里插入图片描述][20190216200328883.png]
2.  删除叶子节点:1  
    ![在这里插入图片描述][20190216200433649.png]
3.  删除只有一个孩子的节点:7  
    ![在这里插入图片描述][20190216200406369.png]
4.  删除有两个孩子的节点:2  
    ![在这里插入图片描述][20190216200454926.png]

/** * @author wangwei * @date 2019/2/15 17:08 * @classDescription 排序二叉树测试 * */
    
    public class BSTTest { 
       @Test
        public void testInsert(){ 
         int []nums=  { 10,2,5,7,8,9,10,3,1,14};
    
         BTreeNode tree=null;
         for(int num:nums){ 
             System.out.println(num);
           tree= BST.insertNode(tree,num);
         }
         Queue<Integer> queue=new ArrayDeque<>();
         BTreeNode.inorderVisit(tree,queue);
          System.out.println(queue.toString());
           Queue<Integer> queue2=new ArrayDeque<>();
           System.out.println("删除10 之后-----------");
           tree=BST.deleteNode(tree,10);
           BTreeNode.inorderVisit(tree,queue2);
           System.out.println(queue2.toString());
        }
    
    }

**总结:**

1.  节点的删除比较有难度
2.  仔细观察发现,这样完全依赖输入的序列直接构建排序二叉树,高度是不太可控的,比如输入序列有序性非常高,完全升序,那么树的高度就会很高,查找效率由o(lgn )降为 o(n)  
    如何改善这一问题呢?平衡二叉树就是为了保证查找效率而提出的,通过调整旋转使得高度比较统一,下一篇博客将介绍平衡二叉树的代码实现.

[Link 1]: https://mp.csdn.net/mdeditor/86772367#
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]: /images/20220319/b547f01a315b4bbf870073e0409e732d.png
[20190216200328883.png]: /images/20220319/ef71b13f65154637ac6bad9fb517317e.png
[20190216200433649.png]: /images/20220319/3e2faf41ef764ffd9bd79eb11dccf28d.png
[20190216200406369.png]: /images/20220319/9182154bcf2e48aaab23704cceb54b48.png
[20190216200454926.png]: /images/20220319/5df0ba918466479aad57e97da71b22ba.png