• 近期将进行后台系统升级,如有访问不畅,请稍后再试!
  • 极客文库-知识库上线!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 每日更新优质编程文章!
  • 更多功能模块开发中。。。

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

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(5.4)改进添加操作:深入理解递归终止条件
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

欢迎 注册账号 登录 发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00