二叉排序树的JAVA实现

二叉排序树

定义

又称二叉查找树

一个空树或者满足以下性质的二叉树

• 若它的左子树不为空，则左子树上所有的结点的值均小于它的根结点的值；
• 若它的右子树不为空，则左子树上所有的结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树。

核心过程 查找过程

用给定值从根结点的关键字进行比较，

• 若相等，则查找成功，

• 若给定值比根结点关键字大，则从根结点的右子树中继续比较查询

• 若给定值比根结点关键字小，则从根结点的左子树中继续比较查询

  查询出则返回， 查询不到则返回NULL。

插入过程

在查询给的值的时候，最后的位置结点是树的叶子结点，那么包含给定值的新结点根据大小作为叶子结点的左子结点或右子结点。 通过使用二叉排序树对动态查找表做查找和插入的操作，同时在中序遍历二叉排序树时，可以得到有关所有关键字的一个有序的序列。

删除过程

在查找过程中，如果在使用二叉排序树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉排序树。

假设要删除的为结点 p，则对于二叉排序树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：

1. 结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可；

   比如上图中删除结点52：

2. 结点 p 只有左子树或者只有右子树，如果 p 是其双亲节点的左孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的左子树；反之也是如此，如果 p 是其双亲节点的右孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的右子树；

   比如删除结点4：

3. 结点 p 左右子树都有，用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉排序树中对其直接前驱（或直接后继）做删除操作。

   比如删除结点30：

结点的前驱：该结点左子树中拥有最大值的结点，亦或采用中序遍历树，在当前结点之前的结点即是当前结点的前驱。

结点的后继：该结点右子树中拥有最小值的结点，亦或采用中序遍历树，在当前结点之后的结点即是当前结点的后继。

存储结构 二叉链表 leftchilddatarightchild

package tree;

public class TreeNode {
    /**
     * 结点上的值
     */
    private int value;
    /**
     * 左节点
     */
    private TreeNode left;
    /**
     * 右节点
     */
    private TreeNode right;

    public TreeNode() {

    }

    public TreeNode(TreeNode left, TreeNode right, int value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }

    public TreeNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

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

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

JAVA实现

package tree;

import org.apache.commons.lang.StringUtils;

public class BinarySearchTree {

    public static final StringBuilder VALUES = new StringBuilder();
    public static final String SEPARATOR = "->";
    public static final int SEPARATOR_LENGTH = SEPARATOR.length();

    public TreeNode root;

    public void insertBinarySearchTree(int key) {
        TreeNode p = root;
        // 新增节点的父节点
        TreeNode prev = null;

        // 找到新增节点的父节点
        while (p != null) {
            prev = p;
            if (key  p.getValue()) {
                p = p.getRight();
            } else {
                return;
            }
        }
        if (root == null) {
            root = new TreeNode(key);
        } else if (key >>>    24     90
         *  /  \    / \                 /       / \
         * 3   27  62  100             3      62  100
         */
        System.out.println("inorder:" + binarySearchTree.orderPrint(binarySearchTree.root));
    }

    /**
     * 构建如下的二叉树，同时是个满二叉树
     * 45
     * /    \
     * 24     90
     * /  \    / \
     * 3   27  62  100
     */
    public static BinarySearchTree init() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] ints = {45, 24, 90, 3, 27, 100, 62};
        for (int a : ints) {
            binarySearchTree.insertBinarySearchTree(a);
        }
        return binarySearchTree;
    }
}