二叉排序树的创建和节点删除

曾经终败给现在 2023-05-31 15:29 89阅读 0赞

二叉排序树-BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。  
例如对于一批数据 (7, 3, 10, 12, 5, 1, 9) 对应的二叉排序树如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]

# 二叉排序树的创建 #

其实，二叉排序树创建比较简单，其实就是一个个节点加上，怎么将节点往树上加呢？

1.  与父子树进行进行比较，比父子树大就话，就将右子树当成父子树，再进行同样的操作，直到找到对应方向子树（比如左子树）为空的父子树，那么就将其插在父子树的左子树上；
2.  其他情况也是类似。
3.  例如，在左边的树上添加一个数值为2的节点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]首先，创建一个节点类，来存放我们的数据，并且有左子树和右子树的属性。

/** * 节点类 */
    class Node{ 
        public int val;
        public Node left = null;
        public Node right = null;
    
        public Node(int val){ 
            this.val = val;
        }
    }

/** * 二叉排序树实现代码 */
    public class BinarySortTree { 
    
        private Node root = null;
        private int order = 1;
    
        /** * 节点添加 * @param node */
        public void add(Node node){ 
            // 第一次添加元素时
            if (root == null){ 
                root = node;
                return;
            }
    
            Node temp = root;
            while (temp != null){ 
                if (node.val <= temp.val){ 
                    if (temp.left == null){ 
                        temp.left = node;
                        break;
                    } else{ 
                        temp = temp.left;
                    }
                } else{ 
                    if (temp.right == null){ 
                        temp.right = node;
                        break;
                    } else{ 
                        temp = temp.right;
                    }
                }
            }
        }
    }

# 遍历二叉树 #

因为二叉排序树的特点，我们可以一直往左子树进行遍历，然后开始回溯，打印左子树——>父子树——>右子树，刚好符合我们二叉排序树的排序特点。

/** * 打印整颗二叉树 */
    public void show(){ 
        if (root == null){ 
            System.out.println("二叉树为空！！！");
            return;
        }
    
        showRecusion(root);
    
    }
    
    /** * 打印的递归体 * @param node */
    private void showRecusion(Node node){ 
        // 一直向左递归，直到左叶子节点
        if (node.left != null){ 
            showRecusion(node.left);
        }
        // 然后开始回溯，打印父节点，接着打印右叶子节点，刚好符合二叉排序树的排序
        System.out.println(String.format("第一个%d数值为：%d", order, node.val));
        order ++;
        if (node.right != null){ 
            showRecusion(node.right);
        }
    }

# 节点删除 #

1.  第一种情况：删除的是叶子节点，直接删除即可；
2.  第二种情况：如果删除的是有一颗子树的节点，那么，将其子树代替其位置；
3.  第三种情况：删除的是有两颗子树的节点。  
    **将右子树代替要删除节点的位置，然后左子树放在右子树的最底层左子树；因为整颗左子树都是比右子树小的，所以左子树需要移动到右子树最小的子树上，即右子树上最左的子树，并且还要放在其左边**

/** * 删除节点 * @param node */
        public void del(Node node){ 
            Node parent = root;
            Node temp = null;
            if (root.val == node.val){  // 需要先判断删除的节点是否为根节点
                if (root.left == null && root.right == null){ 
                    root = null;
                } else if (root.left != null && root.right != null){ 
                    Node left = root.left;
                    root = root.right;
                    temp = root.left;
                    while (temp.left != null){ 
                        temp = temp.left;
                    }
                    temp.left = left;
                }
                return;
            } else if (root.val > node.val){ 
                temp = root.left;
            } else { 
                temp = root.right;
            }
            // 迭代找到想删除的节点
            while (temp != null){ 
                if (temp.val == node.val){ 
                    break;
                } else if (temp.val > node.val){ 
                    parent = temp;
                    temp = temp.left;
                } else{ 
                    parent = temp;
                    temp = temp.right;
                }
            }
            if (temp == null){ 
                System.out.println("该节点不存在，无法删除");
                return;
            }
            // 如果要删除的为叶子节点，则直接删除即可
            if (temp.left == null && temp.right == null){ 
                if (parent.left == temp){ 
                    parent.left = null;
                } else{ 
                    parent.right = null;
                }
            } else if (temp.left != null && temp.right != null) { 
                // 删除节点有两个子树
                // 将右子树代替要删除节点的位置，然后左子树放在右子树的最底层左子树
                // 因为整颗左子树都是比右子树小的，所以左子树需要移动到右子树最小的子树上，即右子树上最左的子树
                if (parent.left == temp){ 
                    parent.left = temp.right;
                } else{ 
                    parent.right = temp.right;
                }
                Node left = temp.left;
                temp = temp.right;
                while (temp.left != null) { 
                    temp = temp.left;
                }
                temp.left = left;
            } else{ 
                // 删除的节点只有一颗子树
                // 直接将子树替换其位置即可
                if (temp.right != null){ 
                    if (parent.left == temp){ 
                        parent.left = temp.right;
                    } else{ 
                        parent.left = temp.right;
                    }
                } else{ 
                    if (parent.left == temp){ 
                        parent.left = temp.left;
                    } else{ 
                        parent.left = temp.left;
                    }
                }
            }
        }

# 测试代码 #

/** * 主方法：测试代码 * @param args */
    public static void main(String[] args) { 
        BinarySortTree tree = new BinarySortTree();
        int[] arr = { 7, 3, 10, 12, 5, 1, 9, 2};
        for (int a: arr){ 
            tree.add(new Node(a));
        }
    // tree.del(new Node(2));
        tree.del(new Node(10));
        tree.show();
        }

完整代码已上传至[GitHub][]

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114358377.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: /images/20230531/b18ab58784d34e61a5835c4b7bc9cd43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/82ebd9c52ded407cb1537270759065a5.png
[GitHub]: https://github.com/SGyuanshi/DataStructures/blob/master/src/com/hong/tree/BinarySortTree.java
[20200430114358377.jpg]: /images/20230531/92270ad2c733436dbc69d286116053f1.png