数据结构笔记总结（5.4）改进添加操作：深入理解递归终止条件

改进我们的代码

上一小节实现了向二分搜索树中插入元素这一操作，这一小节改进一下我们的代码，让我们对递归有更深的理解。

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

源码下载

导航目录

喜欢 (0)赏

[247507792@qq.com]

分享 (0)