《恋上数据结构与算法》笔记（九）：二叉搜索树 II

拼搏现实的明天。 2022-12-20 02:51 55阅读 0赞

> 由于篇幅, 此篇和上篇文章无缝衔接 : [二叉搜索树 I][I]

## 目录 ##

> 代码下载地址 : [https://github.com/coderZYGui/tree-structure.git][https_github.com_coderZYGui_tree-structure.git], 欢迎`star`

*  五、二叉搜索树练习
    
     *  LeetCode : 计算二叉搜索树的高度
     *  2、判断一棵二叉树是否为完全二叉树
     *  LeetCode : 翻转一个二叉树
     *   六、重构二叉树
 *  七、二叉搜索树的前驱和后继
    
     *  1、前驱节点
     *  2、后驱节点
 *  八、二叉排序树删除节点

# 五、二叉搜索树练习 #

跳转到目录

### 1、计算二叉搜索树的高度 ###

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

##### `思路:` #####

*  **递归方式:** 因为我们发现`根节点`的高度就是整课二叉树的高度; `根节点的高度 = Math.max(其左右子树的高度) + 1`;
 *  **迭代方式:** 通过`层序遍历`我们可以发现, 当每一层遍历完之后我们就对定义的height++, 这样就可以计算出树的高度了, 此时又出现一个问题, 怎么判断`每一层节点遍历完呢`, 可以发现`queue.size()`就是下一层的节点数量

// 方式一: 递归的方式
    public int height() { 
        return height(root);
    }
    
    public int height(Node<E> node) { 
        if (node == null) return 0;
        // 左子节点或右子节点中高度最高的值 + 1
        return 1 + Math.max(height(node.left), height(node.right));
    }
    
    // 方式二: 迭代的方式
    /** * 使用层序遍历的方式, 计算树的高度 */
    public int height2() { 
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);	// 往队列中放节点
        // 当前队列中节点个数
        int elementCount = 1;
        // 树的高度
        int height = 0;
        while (!queue.isEmpty()) { 
            // 取出节点
            Node<E> node = queue.poll();
            // 队列中节点个数-1
            elementCount--;
            if (node.left != null) { 
                queue.offer(node.left);
            }
            if (node.right != null) { 
                queue.offer(node.right);
            }
            // 当 elementCount = 0, 说明当前层的节点遍历完成
            if (elementCount == 0) { 
                // 记录下一层节点个数
                elementCount = queue.size();
                // 高度+1
                height++;
            }
        }
        return height;
    }

### 2、判断一棵二叉树是否为完全二叉树 ###

跳转到目录  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center]

// 首先给内部的Node节点增加两个方法
    private static class Node<E> { 
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
    
        // 这里不初始化左,右结点,因为不常用,比如所叶子结点,就灭有左右结点
        // 父节点,除了根节点外,都有父节点
        public Node(E element, Node<E> parent) { 
            this.element = element;
            this.parent = parent;
        }
    
        /** * 判断是否为叶子节点 * @return */
        public boolean isLeaf() { 
            return left == null && right == null;
        }
    
        /** * 判断是否为左右节点都不为空的节点 * @return */
        public boolean hasTwoChildren() { 
            return left != null && right != null;
        }
    }

// 使用这种方式更加清晰
    public boolean isCompleteTree2() { 
        if (root == null) return false;
    
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root); // 将根节点先入队
    
        boolean leaf = false;
        while (!queue.isEmpty()) { 
            Node<E> node = queue.poll(); // 取出队头节点
    
            if (leaf && !node.isLeaf()) return false;
    
            if (node.left != null) {     // 如果该节点左节点不为空,则将该左节点入队
                queue.offer(node.left);
            } else if (node.right != null) { 
                // node.left == null && node.right != null
                return false;
            }
    
            if (node.right != null) {    // 如果该节点右节点不为空,则将该右节点入队
                queue.offer(node.right);
            } else { 
                // 能来到这里, 说明后面的节点都是叶子节点
                // node.left == null && node.right == null
                // node.left != null && node.right == null
                leaf = true;
            }
        }
        return true;
    }
    
    // 判断一棵二叉树是否为完全二叉树(方式一, 推荐方式二)
    public boolean isCompleteTree() { 
        if (root == null) return false;
    
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root); // 将根节点先入队
    
        boolean leaf = false;
        while (!queue.isEmpty()) { 
            Node<E> node = queue.poll(); // 取出队头节点
    
            // node不是叶子节点的情况
            if (leaf && !node.isLeaf()) return false;
    
            if (node.hasTwoChildren()) {     // 左右节点都不为空
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {    // 不符合完全二叉树的要求
                return false;
            } else {     // 这里的节点都是叶子节点
                leaf = true;
                if (node.left != null) { 
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }

##### `注意:` #####

以后使用到二叉树的`层序遍历`, 首先要保证可以`遍历到所有的节点`, 模板如下

// 层序遍历
    public void levelOrder(r) { 
        if (root == null) return;
    
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root); // 将根节点先入队
    
        while (!queue.isEmpty()) { 
            Node<E> node = queue.poll(); // 取出队头节点
    		
    		// TODO 
    
            if (node.left != null) {     // 如果该节点左节点不为空,则将该左节点入队
                queue.offer(node.left);
            }
            if (node.right != null) {    // 如果该节点右节点不为空,则将该右节点入队
                queue.offer(node.right);
            }
        }
    }

### 3、翻转一个二叉树 ###

跳转到目录  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 1]

public class TreeNode { 
    
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { 
            val = x;
        }
    }
    
    class Solution { 
         public TreeNode invertTree(TreeNode root) { 
            if (root == null) return root;
    		
    		// 递归实现
    		
            // 前序遍历, 交换结点
    /* TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right);*/
    
    
            // 后序遍历, 交换结点
    /* invertTree(root.left); invertTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp;*/
    
            // 中序遍历, 交换节点
    
            invertTree(root.left);
    
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
    
            //invertTree(root.right);
            invertTree(root.left);  // 之所以改为root.left, 在交换左右结点的时候已经更改了right
    
            return root;
        }
    }

# 六、重构二叉树 #

跳转到目录  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 3]

# 七、二叉搜索树的前驱和后继 #

跳转到目录

`前提: 中序遍历`

### 1、前驱节点（predecessor） ###

跳转到目录

*  `中序遍历`时的`前`一个节点。
 *  如果是二叉搜索树，**前驱节点就是前一个比它小的节点**。

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

**寻找前驱节点分三种情况：**

1、左子树不为空

*  举例：`6，13，8`
 *  `predecessor = node.left.right.right.right...`
 *  终结条件：`right = null`

2、左子树为空，父节点不为空

*  举例：`7，11，9，1`
 *  `predecessor = node.parent.parent.parent...`
 *  终结条件：`node`在`parent`的`右子树`中。

3、左子树为空且父节点为空

*  那就没有前驱节点
 *  举例：没有`左子树`的根节点。

/** * 根据传入的节点, 返回该节点的前驱节点 (中序遍历) * * @param node * @return */
    private Node<E> predecessor(Node<E> node) { 
        if (node == null) return node;
    
        // (中序遍历)前驱节点在左子树当中(node.left.right.right.right...)
        Node<E> p = node.left;
        // 左子树存在
        if (p != null) { 
            while (p.right != null) { 
                p = p.right;
            }
            return p;
        }
    
        // 程序走到这里说明左子树不存在; 从父节点、祖父节点中寻找前驱节点
        /* * node的父节点不为空 && node是其父节点的左子树时. 就一直往上寻找它的父节点 * 因为node==node.parent.right, 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 */
        while (node.parent != null && node == node.parent.left) { 
            node = node.parent;
        }
    
        // 能来到这里表示: 两种情况如下
        // node.parent == null 表示没有父节点(根节点),返回空 ==> return node.parent;
        // node==node.parent.right 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 ==> return node.parent;
        return node.parent;
    }

### 2、后继节点（successor） ###

跳转到目录

*  `中序遍历`时的`后`一个节点。
 *  如果是二叉搜索树，后继节点就是前一个比它`大`的节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 5]

**寻找后继节点分三种情况：**

1、右子树不为空

*  举例：`1，4，4`
 *  `successor = node.right.left.left.left...`
 *  终结条件：`left = null`

2、右子树为空，父节点不为空

*  举例：`7，6，3，11`
 *  `successor = node.parent.parent.parent...`
 *  终结条件：`node在parent的左子树`中。

3、右子树为空且父节点为空

*  那就没有前驱节点
 *  举例：没有`右子树`的根节点。

/** * 根据传入的节点, 返回该节点的后驱节点 (中序遍历) * * @param node * @return */
    private Node<E> successor(Node<E> node) { 
        if (node == null) return node;
    
        Node<E> p = node.right;
        if (p != null) { 
            while (p.left != null) { 
                p = p.left;
            }
            return p;
        }
    
        // node.right为空
        while (node.parent != null && node == node.parent.right) { 
            node = node.parent;
        }
    
        return node.parent;
    }

# 八、二叉排序树删除节点 #

跳转到目录

`提示`：删除元素会使用`前驱`，`后继`的知识，可以先阅读: **二叉搜索树（Binary Search Tree）的前驱和后继**

*  删除节点分为`删除叶子节点`，`删除度为1的节点`，`删除度为2的节点`。

**删除叶子结点**

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

*  删除`叶子节点`，直接`删除`即可。
    
     *  如果`node == node.parent.left`
        
         *  `node.parent.left = null`
     *  如果`node == node.parent.right`
        
         *  `node.parent.right = null`
     *  如果`node.parent == null`
        
         *  `root = null`

**删除度为1的结点**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 7]  
`删除度为1的节点`，用子节点替代原节点的位置。`child = node.left或者child = node.right`

*  用child替代node的位置。
 *  如果node是左子节点：
    
     *  `child.parent = node.parent`
     *  `node.parent.left = child`
 *  如果node是右子节点：
    
     *  `child.parent = node.parent`
     *  `node.parent.right = child`
 *  如果node是根节点：
    
     *  `root = child`

**删除度为2的结点**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 8]  
`删除度为2的节点`，先`用前驱或后继节点的值覆盖原节点的值`，然后`删除相应的前驱或者后继节点`。（如果这个节点的度为2，那么它的前驱，后继节点的度只能是1和0）

public void add(E element) { 
        elementNotNullCheck(element);
    
        // 添加第一个节点
        if (root == null) { 
            // 给根节点赋值,且根节点没有父节点
            root = new Node<>(element, null);
            size++;
            return;
        }
    
        // 添加的不是第一个节点
        Node<E> parent = root; // 这个是第一次比较的父节点
        Node<E> node = root;
        int cmp = 0;
        while (node != null) { 
            cmp = compare(element, node.element);   // 两者具体比较的方法
            parent = node; // 记录其每一次比较的父节点
            if (cmp > 0) { 
                // 插入的元素大于根节点的元素,插入到根节点的右边
                node = node.right;
            } else if (cmp < 0) { 
                // 插入的元素小于根节点的元素,插入到根节点的左边
                node = node.left;
            } else {  // 相等
                node.element = element;
                return;
            }
        }
        // 看看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) { 
            parent.right = newNode;
        } else { 
            parent.left = newNode;
        }
        size++;
    }
    
    public void remove(E element) { 
        remove(node(element));
    }
    
    /** * 删除结点的逻辑 * * @param node */
    private void remove(Node<E> node) { 
        if (node == null) return;
        // node 不为空, 必然要删除结点, 先size--;
        size--;
        // 删除node是度为2的结点
        if (node.hasTwoChildren()) { 
            //1 找到后继(也可以找到前驱)
            Node<E> successor = successor(node);
            //2 用后继结点的值覆盖度为2结点的值
            node.element = successor.element;
            //3 删除后继节点
            node = successor;
        }
        // 删除node,即删除后继节点 (node节点必然是度为1或0)
        // 因为node只有一个子节点/0个子节点, 如果其left!=null, 则用node.left来替代, node.left==null, 用node.right来替代,
        // 若node为叶子节点, 说明, node.left==null, node.right也为null, 则replacement==null;
        Node<E> replacement = node.left != null ? node.left : node.right;
    
        // 删除node是度为1的结点
        if (replacement != null) { 
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) {   // node是度为1且是根节点
                root = replacement;
            } else if (node == node.parent.left) { 
                node.parent.left = replacement;
            } else if (node == node.parent.right) { 
                node.parent.right = replacement;
            }
            // 删除node是叶子节点, 且是根节点
        } else if (node.parent == null) { 
            root = null;
        } else {  // node是叶子结点, 且不是根节点
            if (node == node.parent.left) { 
                node.parent.left = null;
            } else {   // node == node.parent.right
                node.parent.right = null;
            }
        }
    }
    
    /** * 传入element找到对应element对应的结点 * * @param element * @return */
    private Node<E> node(E element) { 
        Node<E> node = root;
        while (node != null) { 
            int cmp = compare(element, node.element);
            if (cmp == 0) return node;
            if (cmp > 0) {   // 说明element对应的结点, 比node的element大, 所以去它的右子树找
                node = node.right;
            } else { 
                node = node.left;
            }
        }
        return null; // 没有找到element对应的结点
    }
    
    
    // 实现contains和clear方法
    public boolean contains(E element) { 
        return node(element) != null;
    }
    public void clear() { 
        root = null;
        size = 0;
    }

--------------------

[I]: https://blog.csdn.net/m0_37989980/article/details/106415853
[https_github.com_coderZYGui_tree-structure.git]: https://github.com/coderZYGui/tree-structure.git
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/566b0eb00ba943dba98f949187356fc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f22e630165e9445e9958d363d9c0794f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201116233328145.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201116234118201.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201116234147983.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201116234741971.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201116234936961.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201116235401211.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201116235439858.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201116235453855.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw,size_16,color_FFFFFF,t_70#pic_center