• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(5.10)二分搜索树的层序遍历

极客笔记 Geekerstar 11个月前 (05-16) 440次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

二分搜索树的层序遍历

层序遍历很好理解,对于二分搜索树每一个节点有相应深度值,通常把根节点叫做深度为0的节点。

所谓的层序遍历就是这样一层一层的,先遍历第0层的节点也就是28,再遍历第一层的节点也就是16和30,再遍历第2层的节点也就是13、22、29、42,这样一种方式又称为“广度优先遍历”。

相当于逐层向下遍历的节点,在广度上进行拓展,而不像之前的顺着枝杈先向一个方向走。

通常对于这种遍历方式不是通过递归来实现的,而是通过非递归的方式进行实现,并且在其中要借助另外的数据结构也就是队列。

从跟节点排着队进入这个队列,队列中存储的就是待遍历的元素,每次遍历一个元素之后,再将它们的左右孩子也排进队列中,这个过程依次类推。

原理演示

如图,右侧的通道就是队列,队首在上,队尾在下,每次一个元素入队,就是从队尾的位置进入队列,在初始化的时候将根节点入队。

之后每一次做的事情就是先看一下队首,看谁该进行遍历了,初始的时候就是这个根节点28,所以对28进行相应的操作,28就遍历完了,之后将28的左右孩子分别入队,也就是将16和30入队。

对于队列来说是先到先得,先进先出,所以按照从左到右的顺序进行入队,先入队16,再入队30,现在的队首是16,把16拿出来访问,之后要做的事情就是将16的两个孩子入队,将左孩子13和右孩子22入队。

此时30在队首,将30拿出来访问,之后将30的两个孩子29和42入队。

下面,队首元素就是13了,我们把13拿出来访问,之后应该讲13的左右孩子入队,不过由于13是叶子节点,没有孩子所以也就没有元素入队了,这里13就访问完了。

然后看现在队首是22,22出队进行访问,接下来原理相同,依次类推。

现在整个队列都为空了,没有队首元素了,说明我们这个层序遍历(广度优先遍历)也就结束了。

代码演示

// 二分搜索树的层序遍历
public void levelOrder(){

    if(root == null)
        return;

    Queue q = new LinkedList<>();
    q.add(root);
    while(!q.isEmpty()){
        Node cur = q.remove();
        System.out.println(cur.e);

        if(cur.left != null)
            q.add(cur.left);
        if(cur.right != null)
            q.add(cur.right);
    }
}

接下来做一个简单的测试,下图就是层序遍历的结果

广度优先遍历的意义

对于深度优先遍历,如图箭头所示,从根节点一股脑的一下子跑到非常深的地方,但很有可能我们问题的解就在红点所示的位置上。

深度优先遍历由于先顾及左子树,所以要花很长时间才能访问到这里,这样一来广度优先遍历就有意义了,能更快的找到问题的解,常用于算法设计中的最短路径问题。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(5.10)二分搜索树的层序遍历
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

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

客服QQ


QQ:2248886839


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