算法学习之二叉排序树

为了使二叉树的查找效率更高，我们对二叉树进行了优化，如此产生了对于查找效率比较高的二叉排序树（也叫二叉搜索树）

目录

概念

原理

创建二叉排序树

二叉排序树的查找

概念

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

原理

因二叉排序树满足上述特点，其查找操作如下：

先检查当前节点是否与要查找的值匹配

• 若匹配则返回该节点

• 若节点值小于查找值，则遍历其右子树（右子树的值均大于根结点）

• 若节点值大于查找值，则遍历其左子树（左子树的值均小于根结点）

创建二叉排序树

这里我们给出一个数组，根据数组中的值构建二叉排序树

构建的步骤：

• 我们默认数组中的第一个值为根结点

• 从根节点开始遍历

  • 若有左节点且插入的值比节点值小，则向左遍历

  • 若有右节点且插入的值节点值大，则向右遍历

• 遍历到相应位置后，根据节点值的大小，将插入的节点放到其左右节点

class BinaryNode {
    private int value;
    BinaryNode left;
    BinaryNode right;

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        if (left != null && right != null) {
            return "HuffNode{ " +
                    " value=" + value +
                    " left=" + left.value +
                    " right=" + right.value +
                    " }";
        } else if (left != null && right == null) {
            return "HuffNode{ " +
                    " value=" + value +
                    " left=" + left.value +
                    " }";
        }
        else if (right != null && left == null) {
            return "HuffNode{ " +
                    " value=" + value +
                    " right=" + right.value +
                    " }";
        }else {
            return "HuffNode{ " +
                    " value=" + value +
                    " }";
        }
    }

    public BinaryNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    public BinaryNode() {
        this.left = null;
        this.right = null;
    }
}

class BinarySortTree {
    private BinaryNode root;

    public BinaryNode getRoot() {
        return root;
    }

    
    public void createBinarySortTree(int []arr) {
        BinaryNode node = new BinaryNode(arr[0]);
        this.root = node;
        for (int i = 1; i < arr.length; i++) {
            // 1.从根节点开始
            node = root;
            // 2.比节点值小且有左节点,向左移动
            while (node.left != null && arr[i] <= node.getValue() || node.right != null && arr[i] > node.getValue()) {
                if (node.left != null && arr[i] <= node.getValue()) {
                    node = node.left;
                }
                // 3.比节点值大且有右节点,向右移动
                if (node.right != null && arr[i] > node.getValue()) {
                    node = node.right;
                }
            }
            // 4.移动到相应位置后,与节点值做比较
            // 比节点值大放在右边
            if (arr[i] > node.getValue()) {
                BinaryNode temp = new BinaryNode(arr[i]);
                node.right = temp;
            }
            // 小于等于节点值放在左边
            if (arr[i] <= node.getValue()) {
                BinaryNode temp = new BinaryNode(arr[i]);
                node.left = temp;
            }
        }
    }

}

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {10,11,7,6,8,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        // 创建二叉排序树
        binarySortTree.createBinarySortTree(arr);
    }
}

此时我们根据数组{5,10,9,6,1,11,3,8}构建出来的二叉排序树如图：

二叉排序树的查找

 查找方法原理已将说明，这里不再赘述，直接上代码（其中附带前序遍历的代码）

class BinaryNode {

    
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    
    public BinaryNode binaryFind(int value) {
        BinaryNode node = null;
        // 找到则返回该节点
        if (this.value == value) {
            node = this;
            return  node;
        } else if (this.left != null && this.value > value) {
            // 比节点值小,向左查询
            node = this.left.binaryFind(value);
        }else if (this.right != null && this.value < value){
            // 比节点值大,向右查询
            node = this.right.binaryFind(value);
        }
        return node;
    }

}
class BinarySortTree {
   
    
    public void preOrder() {
        if (root == null) {
            System.out.println("k");
        }else {
            root.preOrder();
        }
    }

    
    public BinaryNode binaryFind(int value) {
        if (root == null) {
            return null;
        } else {
            BinaryNode node = root.binaryFind(value);
            return node;
        }
    }
}

节点的删除

为了使删除节点后的二叉树依旧是一个二叉排序树，我们的删除操作要复杂一点

当我们删除二叉排序树中的一个节点时，为了使其仍然构成排序树，我们需要将删除节点的

• 左子树中最大的节点放到删除节点的位置

  • 左子树中的最大值比左子树中任意值都大，比右子树中任意值都小

• 或者右子树中最小的节点放到删除节点的位置

  • 右子树中的最小值比右子树中任意值都小，比左子树中任意值都大

class BinaryNode {
    
    public boolean delBinary(int value) {
        boolean flag = false;
        // 方案2
        // 1. 找到父节点
        while (this.left != null && value <= this.getValue() || this.right != null && value > this.getValue()) {
            // 如果该节点的左子节点或者右子节点为该值,则找到其父节点
            if (this.left != null && this.left.value == value || this.right != null && this.right.value == value) {
                break;
            }
            // 节点值大于查找值,并且左子树不为空,向左遍历
            if (this.value > value && this.left != null) {
                flag = this.left.delBinary(value);
                return flag;
            }
            // 节点值小于查找值,并且右子树不为空,向右遍历
            if (this.value < value && this.right != null) {
                flag = this.right.delBinary(value);
                return flag;
            }
        }
        // 如果父节点的左子节点是叶子节点或者右子节点是叶子节点,即要删除的节点是叶子节点,直接删除即可
        if (this.left != null && this.left.value == value && this.left.left == null && this.left.right == null || this.right != null && this.right.value == value && this.right.left == null && this.right.right == null) {
            if (this.left != null) {
                this.left = null;
            }
            if (this.right != null) {
                this.right = null;
            }
            flag = true;
        } else {
            //删除该节点后将该节点左子树中最大的节点或者右子树最小的节点放到该节点的位置
            // 这里我们的思路是新建一个节点与最大节点的值相同,然后让最大节点的父节点的右子树指向最大节点的左子树(即删除了最大节点)
            // 在让新建节点的左节点指向删除节点的左子树,再将删除节点的父节点指向新建节点(最大节点替换了删除节点)
            // 要删除的节点
            System.out.println("-----"+this);
            // 如果要删除的节点是父节点的左节点
            if (this.left != null && this.left.value == value) {
                // 要删除的节点
                BinaryNode node = this.left;
                // 如果删除的节点没有左子树,直接将右子树放过来
                if (node.left == null) {
                    this.left = node.right;
                    return true;
                }
                // 如果删除的节点没有右子树,直接将左子树放过来
                if (node.right == null) {
                    this.right = node.left;
                    return true;
                }
                // 左子树的根结点
                BinaryNode index = node.left;
                // 找到左子树中最大的节点的父节点
                while (index.right != null) {
                    if (index.right.right == null) {
                        break;
                    }
                    index = index.right;
                }
                // 创建一个新的节点,新节点的值与最大值相同
                BinaryNode maxNode = new BinaryNode(index.right.value);
                // 让最大节点的父节点右节点指向最大节点的左子树
                index.right = index.right.left;
                maxNode.left = node.left;
                this.left = maxNode;
            }else {
                BinaryNode node = this.right;
                // 如果删除的节点没有左子树,直接将右子树放过来
                if (node.left == null) {
                    this.left = node.right;
                    return true;
                }
                // 如果删除的节点没有右子树,直接将左子树放过来
                if (node.right == null) {
                    this.right = node.left;
                    return true;
                }
                BinaryNode index = node.left;
                while (index.right != null) {
                    if (index.right.right == null) {
                        break;
                    }
                    index = index.right;
                }
                // 创建一个新的节点,新节点的值与最大值相同
                BinaryNode maxNode = new BinaryNode(index.right.value);
                // 让最大节点的父节点右节点指向最大节点的左子树
                index.right = index.right.left;
                // 新建节点的左节点指向删除节点的左子树
                maxNode.left = node.left;
                this.right = maxNode;
            }
        }
        return flag;
    }
}
class BinarySortTree {
    
    public boolean delBinary(int value) {
        boolean flag = false;
        if (root == null) {
            return false;
        } else {
            flag = root.delBinary(value);
        }
        return flag;
    }
}