二叉查找树 (Java)

归纳自《数据结构与算法分析——Java 语言描述》

概念

对于数中的每个节点 X，它的左子树中所有项的值小于 X 中的项，而它的右子树中所有项的值大于 X 中的项。

从概念中我们可以得到两个信息：

1. 该树的所有元素是按照【左子树<父节点<右子树】的方式排序好的，我们可以通过某种方法把所有元素按顺序输出
2. 该树所存储的元素必须是可以比较大小的，这就需要该类型元素实现 Comparable 接口。

代码实现（Java）

二叉查找树节点（类）

很清楚的节点类，三个成员变量，一个该节点所存储的元素（element），一个指向左子树（left），一个指向右子树（right）

class BinaryNode{
    BinaryNode(Comparable theElement){
        this(theElement,null,null);
    }

    BinaryNode(Comparable theElement,BinaryNode lt,BinaryNode rt){
        element = theElement;
        left = lt;
        right = rt;
    }

    Comparable element;
    BinaryNode left;
    BinaryNode right;
}

二叉查找树（类）

类的结构还是比较清楚的，私有成员 root 表示树的根节点，构造函数初始化 root=null，构造了一颗空树，isEmpty()和 makeEmpty()都很直观，不再细说，下面会详细讲解二叉查找树的插入、删除等方法。

class BinarySearchTree{
    public BinarySearchTree(){
        root = null;
    }

    public boolean isEmpty(){
        return root == null;
    }

    public void makeEmpty(){
        root = null;
    }

    public Comparable find(Comparable x){
        return elementAt(find(x,root));
    }

    public Comparable findMin(){
        return elementAt(findMin(root));
    }

    public Comparable findMax(){
        return elementAt(findMax(root));
    }

    public void insert(Comparable x){
        root = insert(x,root);
    }

    public void remove(Comparable x){
        root = remove(x,root);
    }

    public void printTree(){
        if(isEmpty()){
            System.out.println("Empty Tree!");
        }else{
            printTree(root);
        }
    }

    private BinaryNode root;

    private Comparable elementAt(BinaryNode t){
        return t == null?null:t.element;
    }

    private BinaryNode find(Comparable x,BinaryNode t){
        //请看下面
    }

    private BinaryNode findMin(BinaryNode t){
        //请看下面
    }

    private BinaryNode findMax(BinaryNode t){
        //请看下面
    }

    private BinaryNode insert(Comparable x,BinaryNode t){
        //请看下面
    }

    private BinaryNode remove(Comparable x,BinaryNode t){
        //请看下面
    }

    private void printTree(BinaryNode t){
        //请看下面
    }
}

find（方法）

形参列表传入两个量，我们要实现的是从 t 树中找到值为 x 的节点并返回该节点。这里我们使用了递归调用，如果 x 小于当前节点的值，就 return find(x,t.left)，继续从该节点的左子树中查找 x，直到 x 与某一节点的值相等，return t，返回该节点，如果是空，就表示树中没有 x，返回 null。

private BinaryNode find(Comparable x,BinaryNode t){
    if(t == null){
        return null;
    }
    if(x.compareTo(t.element) < 0){
        return find(x,t.left);
    }else if(x.compareTo(t.element) > 0){
        return find(x,t.right);
    }else{
        return t;
    }
}

findMax（方法）

if 判断 t!=null 只是为了确定该树是否为空，当然我们可以用 !isEmpty() 来替代，主体部分是一个很简单的循环，二叉排序树的定义就是右子树的元素要大于父节点的元素，所以我们只要找到树最右边的那个节点就一定是最大的。

private BinaryNode findMax(BinaryNode t){
    if(t != null){
        while(t.right != null){
            t = t.right;
        }
    }
    return t;
}

findMin（方法）

与 findMax 方法不同，我们在 findMin 方法中采用递归的思路来实现，当然你也可以采用和 findMin 一样的思路来实现 findMax 方法，最终目的是要找到树最左边的节点。

private BinaryNode findMin(BinaryNode t){
    if(t == null){
        return null;
    }else if(t.left == null){
        return t;
    }
    return findMin(t.left);
}

insert（方法）

方法要实现的是将元素 x 插入树 t 中，先看后两部分判断，如果 x 小于当前节点的值，就将 x 插入 t 的左子树，这里需要注意的是，将 x 插入 t 的左子树后，其左子树应变成插入之后的左子树，所以不能简单的调用 insert(x,t.left) ，而应该是 t.left=insert(x,t.left) ，插入右子树同样如此，直到 t==null ，表示该部分没有新的节点，那么 t 就是这个新节点了，我们可以看出来，t 没有左右子树，是一片叶子。

private BinaryNode insert(Comparable x,BinaryNode t){
    if(t == null){
        t = new BinaryNode(x,null,null);
    }else if(x.compareTo(t.element) < 0){
        t.left = insert(x,t.left);
    }else if(x.compareTo(t.element) > 0){
        t.right = insert(x,t.right);
    }
    return t;
}

remove（方法）

private BinaryNode remove(Comparable x,BinaryNode t){
    if(t == null){
        return null;
    }
    if(x.compareTo(t.element) < 0){
        t.left = remove(x,t.left);
    }else if(x.compareTo(t.element) > 0){
        t.right = remove(x,t.right);
    }else if(t.left != null && t.right != null){
        t.element = findMin(t.right).element;
        t.right = remove(t.element,t.right);
    }else{
        t = (t.left != null)?t.left:t.right;
    }
    return t;
}