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

改进我们的代码

数据结构笔记总结(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);
    }

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(5.4)改进添加操作:深入理解递归终止条件
分享到:
赞(0)

评论抢沙发

评论前必须登录!