改进我们的代码
上一小节实现了向二分搜索树中插入元素这一操作，这一小节改进一下我们的代码，让我们对递归有更深的理解。
// 向以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);
}
首看一下这个插入操作有没有什么问题，先理解一下插入操作的算法过程。
整体上以node为根的这个二分搜素树插入新的元素e，具体插入的过程相当于把新的元素e插入给node的左孩子或者node的右孩子。
如果对于当前的node来说，你想插入到左边但左孩子不为空的话，就递归调用将新的元素插入到左子树中，相应的右侧也一样。
// 向二分搜索树中添加新的元素e
public void add(E e){
if(root == null){
root = new Node(e);
size ++;
}
else
add(root, e);
}
再来看一下对于我们递归add方法的初始调用部分，也就是用户看到的add接口。
我们对根节点进行了特殊的处理：如果根为空的话，根就直接是一个新的节点，否则的话再调用递归函数。
在递归调用中，我们都是把新的元素作为node的子节点插入进去的。
这里形成了一个逻辑上的不统一，再仔细观察一下前面的递归函数，就会发现对于e这个元素和node.e这个元素进行了两轮比较。
第一轮在比较完两个元素大小的同时还要看一下node的左右两个孩子是不是为空，如果是空的话直接插进去就好了。
第二轮比较我们不能直接作为node的孩子插入这个元素e，我们只好递归的再去调用add函数。
还有一点现在我们的递归函数中止条件是非常臃肿的，这是因为我们要考虑node的左孩子是不是为空又要考虑右孩子是不是为空。
不过之前曾说过，“空”本身就是一个二叉树。
换句话说，想象一下如果我们递归函数走到了一个node为空的地方，此时就一定要形成一个节点。
在我们现在写的代码中，这种情况其实还没有递归到底，既然我们看到了e小于node.e，那么我们不管node.left是不是为空，就再递归一层。
如果递归的这一层为空的话，也就是现在新插入一个元素到空这个二叉树上，那么很显然这个位置本身就应该是这个节点，所以用这种想法的话，代码就可以修改为如下所示：
// 向以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;
}
那么我们初始调用的时候就不需要对root为空这种情况进行判断了，因为在我们递归的add函数中对node为空已经进行了考虑，所以初始调用的代码可以更改如下：
// 向二分搜索树中添加新的元素e
public void add(E e){
root = add(root, e);
}
源码下载
下载地址导航目录
查看导航本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接：数据结构笔记总结（5.4）改进添加操作：深入理解递归终止条件
