数据结构 -二分搜索树 -BinarySearchTree

定义：任意左节点 < root；任意右节点 > root

public class Node {
    public E e;
    public Node left;
    public Node right;

    public Node(E e){
        this.e = e;
        left = null;
        right = null;
    }
}
复制代码

二、添加新元素 -递归

// 向以node为根的二分搜索树中插入元素e，递归算法
private void add(Node node, E e){
    if(e.equals(node.e))
        return;
    else if(e.compareTo(node.e) < 0 && node.left == null){
        node.left = new Node(e);
        size ++;
        return;
    }
    else if(e.compareTo(node.e) > 0 && node.right == null){
        node.right = new Node(e);
        size ++;
        return;
    }

    if(e.compareTo(node.e) < 0)
        add(node.left, e);
    else //e.compareTo(node.e) > 0
        add(node.right, e);
}

复制代码

三、改进

以上的代码出现的问题：e和node.e进行了两轮比较以及终止条件太臃肿

// 向以node为根的二分搜索树中插入元素e，递归算法
// 返回插入新节点后二分搜索树的根
private Node add(Node node, E e){
    if(node == null){
        size ++;
        return new Node(e);
    }

    if(e.compareTo(node.e) < 0)
        node.left = add(node.left, e);
    else if(e.compareTo(node.e) > 0)
        node.right = add(node.right, e);

    return node;
}

复制代码

四、二分搜索树的遍历

前序遍历

先根节点，然后左节点，然后右节点

private void preOrder(Node node){
    if(node == null)
        return;

    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}

复制代码

中序遍历

1. 先左节点，然后根节点，然后右节点

2. 二分搜索树的中序遍历是顺序的

private void preOrder(Node node){
    if(node == null)
        return;
    preOrder(node.left);
    System.out.println(node.e);
    preOrder(node.right);
}

复制代码

后续遍历

先左节点，然后右节点，然后根节点

private void preOrder(Node node){
    if(node == null)
        return;
    preOrder(node.left);
    preOrder(node.right);
    System.out.println(node.e);
}

复制代码

五、删除任意节点

1. 要删除的节点d ->右子树中最小值s，也就是 s = minimum(node.right)
2. s 的 d 的后继 ->要删除这个最小节点 s.right = removeMin(d.right) 也就是s和d 互换位置
3. s.left = d.left -> 补充s的left

// 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node){
        if(node.left == null)
            return node;
        return minimum(node.left);
    }
复制代码

// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
    // 返回删除节点后新的二分搜索树的根
    private Node remove(Node node, E e){

        if( node == null )
            return null;

        if( e.compareTo(node.e) < 0 ){
            node.left = remove(node.left , e);
            return node;
        }
        else if(e.compareTo(node.e) > 0 ){
            node.right = remove(node.right, e);
            return node;
        }
        else{   // e.compareTo(node.e) == 0

            // 待删除节点左子树为空的情况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }
复制代码