BST中的接口 - void add(E e)

• 完全将问题抛给递归算法，即将问题转化为一个递归问题；
• 直接将问题丢给一个更厉害的递归方法，从而省掉判断 BST 中 root == null 的情况；
• 先拎着 BST 中 root，把整棵树丢进递归方法中，返回的新树再让 root 接着；

// 向二分搜索树中添加新的元素e
public void add(E e){
    root = add(root, e);
}

更厉害的递归方法 - Node add(Node node, E e)

• 向以 node 为根的二分搜索树中插入元素 e，并返回插入新节点后二分搜索树的根；
• 不能再缩小的基本问题是：向 null 中插入新的节点；
• 规模更小的同一个问题是：将元素 e 插入 node 的左子树或右子树；

// 向以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;
}

特别注意

• 新节点和整棵树的连接是通过将添加新节点后的新树的根返回到外层实现的；
• 在 BST 中添加元素，新添加的节点，只会成为 BST 的叶子节点；