全面理解二进制排序树

当我以前学习数据结构时，我学习了二进制排序树. 但是，由于只是纸上谈兵，虽然我知道插入和删除二进制排序树的操作过程，但是由于没有特定的实现，因此请考虑一下当实现时，会出现一个尴尬的情况“所有人都了解真相，但做不到”. 利用最近的时间，我花时间认真研究二进制排序树构造二叉排序树，并手动编写了实现代码. 我真的很了解二进制排序树的操作过程

二叉排序树，是二叉树的一种变体，主要特征是该树的值在分布时具有非常明显的特征，左子树的值小于根节点的值，并且该值子树的值小于右节点的值. 子树的值在搜索和搜索时非常有优势，因为其平均操作时间接近O（h），h是树的高度，而二叉排序树本身是动态的，可以动态删除和插入节点. 接下来，我们将通过具体示例学习二进制排序树

首先构建一个二进制排序树，然后我们将演示如何通过代码生成树

从图片中可以看到，生成的树相对平衡

树的生成过程

class Tree{
    private Node root;
    public Node getRoot() {
        return root;
    }
    // 构造树，构造的过程相当于将data中的数据插入
    public void construct(int[] data){
        for (int i = 0; i < data.length; i++){
            insert(data[i]);
        }
    }
    /**
     * 插入节点
     * @param value 节点的值
     */
    public void insert(int value){
        Node pre = null;
        Node current = root;
        // 插入的过程：
        //      每次都从根节点开始查找
        //      如果值比根节点小，则插入的节点应该在根节点的左侧
        //      否则，应该在根节点的右侧
        while (current != null){
            pre = current;
            // 如果根节点的值比value大，
            // 则新节点应该插入在根节点的左侧
            if (current.value > value){
                current = current.left;
            //否则，应该插入在右侧
            }else {
                current = current.right;
            }
        }
        current = new Node(value, pre, null, null);
        // 如果pre是null，说明此时是空树
        if (pre == null){
            root = current;
        }else {
            // 如果current的值比pre大，则current是pre的右节点
            if (current.value > pre.value){
                pre.right = current;
            // 否则，current是pre的左节点
            }else {
                pre.left = current;
            }
        }
    }
    /**
     * 中序遍历树，可以用于校验树是否成功创建
     * @param current 当前节点
     */
    public void show(Node current){
        if (current != null){
            show(current.left);
            System.out.print(current.value + " ");
            show(current.right);
        }
    }
    /**
     * 树的节点
     */
    private class Node{
        int value;
        Node parent;
        Node left;
        Node right;
        public Node(int value, Node parent, Node left, Node right) {
            this.value = value;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }
}

完成上述步骤后，我们成功创建了二进制排序树. 可以使用简单的测试来确定树是否正确建立. 一种较简单的方法是遍历树的中间顺序. 交叉排序树的特征，中阶遍历的结果应该是从小到大排序的一系列值

获取树中的最小值和最大值

由于二进制排序树的特性，最小值必须在最左边的子树中，最大值必须在最右边的子树中. 当然，如果它是一棵空树，那么就没有，如果它是一个只有节点的树，那么最小值和最大值就是根节点本身

    // 获取树中的最小值
    public Integer getMin(){
        Node current = root;
        if (current == null){
            return null;
        }
        // 寻找最左子树
        while (current.left != null){
            current = current.left;
        }
        return current.value;
    }
    // 获取树中的最大值
    public Integer getMax(){
        Node current = root;
        if (current == null){
            return null;
        }
        // 寻找最右子树
        while (current.right != null){
            current = current.right;
        }
        return current.value;
    }

查找包含特定值的节点

    // 查找包含某一值的节点
    public Node search(int value){
        Node current = root;
        while (current != null){
            // 如果该值比当前节点的值小，则
            // 找当前节点的左子树
            if (current.value > value){
                current = current.left;
            // 如果该值比当前节点的值大，则
            // 找当前节点的右子树
            }else if (current.value < value){
                current = current.right;
            }else {
                return current;
            }
        }
        // 找不到则返回null
        return null;
    }

查找某个节点的前任和后任

根据二元排序树的特征，某个节点的前体只能是

根据二进制排序树的特性，如果target.parent.left == target，则target.parent的值大于target的值，因此应始终查找. 如果红色箭头显示，则在找到第一个Target.parent.right == target时，如果显示黑框，则表示target.parent的值是刚通过的路径的最小值，而target是倒数第二个最小值（（记住，目标.parent的右子树是最左子树吗？）

对后继节点的搜索类似，但方向应相反，因此在此我不再重复

    // 前驱
    public Node getPre(Node target){
        if (target == null){
            return null;
        }
        // 如果左子树非空，则前驱为左子树的最右子树
        if (target.left != null){
            target = target.left;
            // 寻找最右子树
            while (target.right != null){
                target = target.right;
            }
            return target;
        }else {
            // 否则，查找该节点是某个节点的右子树的最左子树的节点
            // 也就是沿着父亲路径往上走，第一个该节点不是其父亲节点的左节点的节点
            Node parent = target.parent;
            while (parent != null && target == parent.left){
                target = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }
    // 后继
    public Node getSuc(Node target){
        if (target == null){
            return null;
        }
        // 查找右子树的最左子树
        if (target.right != null){
            target = target.right;
            while (target.left != null){
                target = target.left;
            }
            return target;
        }else {
            // 沿着父亲路径向上走，第一个该节点不是父亲节点的右子树的节点
            Node parent = target.parent;
            while (parent != null && target == parent.right){
                target = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-255931-1.html