二叉排序树（BST）

末蓝、 2023-07-11 11:20 13阅读 0赞

### 二叉排序树基本介绍 ###

二叉排序树：BST（Binary Sort(Search) Tree），**对于 一个二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点小，右子节点的值比当前节点的值大**。  
特别说明：如果右相同的值，可以将该节点放在左子节点或者右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]

## 二叉排序树的创建和遍历 ##

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ， 创建成对应的二叉排序树为 :

节点类（重点是添加和遍历的方法）

public class Node { 
        private int data;
        public Node left;
        public Node right;
    
        // 二叉排序数添加方法
        public void add(Node node) { 
            if (node == null) { 
                return;
            }
            // 如果要添加的节点，小于当前节点
            if (node.getData() < this.data) { 
                // 如果当前节点的左子节点不为空，则向左递归
                if (this.left != null) { 
                    this.left.add(node);
                } else { 
                    // 当前节点的左子节点为空，就让添加的节点挂在当前节点的左子节点上
                    this.left = node;
                    return;
                }
            } else {  // 要添加的节点大于或等于当前节点
                // 如果当前节点的右子节点部不为空，则递归添加
                if (this.right != null) { 
                    this.right.add(node);
                }else { 
                    // 当前节点右子节点为空，则直接把要添加的节点挂上
                    this.right = node;
                    return;
                }
            }
        }
    
        /** * 中序遍历 */
        public void midList() { 
            if (this.left != null) { 
                this.left.midList();
            }
            // 输出当前节点
            System.out.println(this);
            if (this.right != null) { 
                this.right.midList();
            }
        }
    
        public Node(int data) { 
            this.data = data;
        }
    
        public int getData() { 
            return data;
        }
    
        public void setData(int data) { 
            this.data = data;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

排序树类

public class BinarySortTree { 
        private Node root;
    
        /** * 添加节点 * @param node */
        public void add(Node node) { 
            if (root == null) { 
                root = node;
            }else { 
                root.add(node);
            }
        }
    
        /** * 中序遍历 */
        public void midList() { 
            if (root != null) { 
                root.midList();
            }
        }
    }

测试

public class MyTest { 
        public static void main(String[] args) { 
            BinarySortTree binarySortTree = new BinarySortTree();
    
            int[] array = { 7, 3, 10, 12, 5, 1, 9};
            for (int i : array) { 
                binarySortTree.add(new Node(i));
            }
            // 遍历
            System.out.println("中序遍历：");
            binarySortTree.midList();
        }
    }

测试结果 ：

中序遍历：
    Node{ data=1}
    Node{ data=3}
    Node{ data=5}
    Node{ data=7}
    Node{ data=9}
    Node{ data=10}
    Node{ data=12}

从输出结果看已经是有序的了

## 二叉排序树的删除 ##

二叉排序树删除情况比较复杂，有下面3种情况要考虑  
示意图图：  
![在这里插入图片描述][2020030517383586.png]

1.  删除叶子节点（如：2,5,9,12）
2.  删除只有一颗子树的的节点(如：1)
3.  删除有两颗子树的节点，（如：7,3,10）

不管是上面的哪一种情况，我们先必须的找到**要删除的节点**和**要删除节点的父节点**。

代码如下（详情请看注释） :

二叉树类：（主要看`delNode`方法和`getMinNodeAndDelMinNode`方法）

public class BinarySortTree { 
        private Node root;
    
        /** * 删除节点， * @param value */
        public void delNode(int value) { 
            // 先找到要删除的节点
            Node node = root.search(value);
            // 找到要删除节点的父节点
            Node parent = root.searchParent(value);
            if (node == null) { 
                System.out.println("没有找到要删除的节点");
                return;
            }
            // 第一种情况：删除的节点是叶子节点，
            // 即该节点没有左子节点和右子节点
            if (node.left == null && node.right == null) { 
                // 如果要删除节点的父节点为null,说明该节点是root节点,直接让root=null
                if (parent == null) { 
                    root = null;
                    return;
                }
                // 要删除的节点是父节点的左子节点
                if (parent.left != null && parent.left.getData() == value) { 
                    // 删除节点，就是让其父节点的引用为null
                    parent.left = null;
                    return;
                }
                if (parent.right !=  null &&  parent.right.getData() == value) { 
                    parent.right = null;
                    return;
                }
             // 第二种情况：要删除的节点只有一颗子树
            } else if ((node.left != null && node.right == null) || (node.right != null && node.left == null)) { 
                // 如果其父节点为null,说明要删除的是root节点，且该root节点只有一个子节点
                if (parent == null) { 
                    // 删除root节点，让其子节点为root节点
                    if (root.left != null) { 
                        root = root.left;
                        return;
                    }
                    if (root.right != null) { 
                        root = root.right;
                        return;
                    }
                } else { 
                    // 其父节点不为null
                    // 要删除的节点是其父节点的左节点
                    if (parent.left != null && parent.left.getData() == value) { 
                        // 要删除的节点有左子节点
                        if (node.left != null) { 
                            parent.left = node.left;
                            return;
                        }
                        // 要删除的节点有右子节点
                        if (node.right != null) { 
                            parent.left = node.right;
                            return;
                        }
                    } else { 
                        // 要删除节点时其父节点的右节点
                        // 要删除的节点有左子节点
                        if (node.left != null) { 
                            parent.right = node.left;
                            return;
                        }
                        // 要删除的节点有右子节点
                        if (node.right != null) { 
                            parent.right = node.right;
                            return;
                        }
                    }
                }
            // 第3种情况：删除的节点有2个子节点,
            } else { 
                // 先找到要删除节点右子树最小的值并删除它，该节点用来填充该删除的节点
                Node minNode = getMinNodeAndDelMinNode(node.right);
                // 如果要删除的节点没有父节点，则其就是根节点
                if (parent == null) { 
                   minNode.left = root.left;
                   minNode.right = root.right;
                   root = minNode;
                   return;
                } else { 
                    minNode.left = node.left;
                    minNode.right = node.right;
                    // 如果要删除的节点在其父节点的左边
                    if (parent.left != null && parent.left.getData() == value) { 
                        parent.left = minNode;
                        return;
                    }else { 
                        parent.right = minNode;
                        return;
                    }
                }
            }
        }
    
        /** * 查找返回最小的节点并删除该最小的节点 * @param node 二叉排序树 * @return 返回最小的节点 并且其有且只有一个节点 */
        private Node getMinNodeAndDelMinNode(Node node) { 
            Node target = node;
            while (target.left != null) { 
                target = node.left;
            }
            // 代码到这，说明已经找到最小值，删除该最小值
            delNode(target.getData());
            target.right = null;
            return target;
        }
    
        /** * 查找节点 * @param value 要查找的值 * @return 返回要查找的节点 */
        public Node search(int value) { 
            if (root == null) { 
                return null;
            }
            return root.search(value);
        }
    
        /** * 查找要查找的值的父节点 * @param value * @return */
        public Node searchParent(int value) { 
            if (root == null) { 
                return null;
            }
            return root.searchParent(value);
        }
    
        /** * 添加节点 * @param node */
        public void add(Node node) { 
            if (root == null) { 
                root = node;
            }else { 
                root.add(node);
            }
        }
    
        /** * 中序遍历 */
        public void midList() { 
            if (root != null) { 
                root.midList();
            }
        }
    }

节点类：（主要看`search`方法和`searchParent`方法）

public class Node { 
        private int data;
        public Node left;
        public Node right;
    
        /** * 根据值查找要找的节点 * @param value 要查找的值 * @return 返回找到的节点 */
        public Node search(int value) { 
            // 如果当前节点就是要查找的值，就直接返回
            if (this.data == value) { 
                return this;
            }
            // 查找的值小于当前节点,
            if (value < this.data) { 
                // 如果当前节点的左子节点不为空，则递归
                if (this.left != null) { 
                    return this.left.search(value);
                } else { 
                    // 当前节点的左子节点为空，说明没有找到，直接返回null
                    return null;
                }
            } else { 
                // 走进这个分支，说明要查找的值大于当前节点的值
                // 如果当前节点的右子节点不为空，则递归
                if (this.right != null) { 
                    return this.right.search(value);
                } else { 
                    // 当前右子节点为空 ，则没有找到，返回null
                    return null;
                }
            }
        }
    
        /** * 查找要查找节点的父节点 * @param value 要查找的值 * @return 返回要查找值的父节点 */
        public Node searchParent(int value) { 
            // 当前节点的左子节点或者右子节点的值等于要查找的值，说明当前节点就是其父节点
            if ((this.left != null && this.left.data == value) ||
                    (this.right != null && this.right.data == value)) { 
                return this;
            }
    
            // 如果当前节点的值大于value
            if (this.data > value) { 
                if (this.left != null) { 
                    // 向左递归
                    return this.left.searchParent(value);
                }else { 
                    // 如果其左子节点为空，说明没有找到，返回null
                    return null;
                }
            } else { 
                // 当前节点值小于或等于value,
                if (this.right != null) { 
                    // 向右递归查找
                    return this.right.searchParent(value);
                }else { 
                    return null;
                }
            }
        }
    
        // 二叉排序数添加方法
        public void add(Node node) { 
            if (node == null) { 
                return;
            }
            // 如果要添加的节点，小于当前节点
            if (node.getData() < this.data) { 
                // 如果当前节点的左子节点不为空，则向左递归
                if (this.left != null) { 
                    this.left.add(node);
                } else { 
                    // 当前节点的左子节点为空，就让添加的节点挂在当前节点的左子节点上
                    this.left = node;
                    return;
                }
            } else {  // 要添加的节点大于或等于当前节点
                // 如果当前节点的右子节点部不为空，则递归添加
                if (this.right != null) { 
                    this.right.add(node);
                }else { 
                    // 当前节点右子节点为空，则直接把要添加的节点挂上
                    this.right = node;
                    return;
                }
            }
        }
    
        /** * 中序遍历 */
        public void midList() { 
            if (this.left != null) { 
                this.left.midList();
            }
            // 输出当前节点
            System.out.println(this);
            if (this.right != null) { 
                this.right.midList();
            }
        }
    
        public Node(int data) { 
            this.data = data;
        }
    
        public int getData() { 
            return data;
        }
    
        public void setData(int data) { 
            this.data = data;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

测试类：

public class MyTest { 
        public static void main(String[] args) { 
            BinarySortTree binarySortTree = new BinarySortTree();
    
            int[] array = { 7, 3, 10, 12, 5, 1, 9,2};
            for (int i : array) { 
                binarySortTree.add(new Node(i));
            }
            // 遍历
            System.out.println("中序遍历：");
            binarySortTree.midList();
    
            System.out.println("删除测试：");
    
    // System.out.println("删除叶子节点5：");
    // binarySortTree.delNode(5);
    // binarySortTree.midList();
    
    // System.out.println("删除只有一颗子树的节点1：");
    // binarySortTree.delNode(1);
    // binarySortTree.midList();
    
            System.out.println("删除有2颗子树的节点7：");
            binarySortTree.delNode(7);
            binarySortTree.midList();
        }
    }

运行结果

中序遍历：
    Node{ data=1}
    Node{ data=2}
    Node{ data=3}
    Node{ data=5}
    Node{ data=7}
    Node{ data=9}
    Node{ data=10}
    Node{ data=12}
    删除测试：
    删除有2颗子树的节点7：
    Node{ data=1}
    Node{ data=2}
    Node{ data=3}
    Node{ data=5}
    Node{ data=9}
    Node{ data=10}
    Node{ data=12}

从结果看看出，已经删除了7节点，并保持排序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200305130933809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[2020030517383586.png]: https://img-blog.csdnimg.cn/2020030517383586.png