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

二分搜索树的层序遍历

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

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

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

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

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

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

原理演示

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

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

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

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

对于队列来说是先到先得,先进先出,所以按照从左到右的顺序进行入队,先入队16,再入队30,现在的队首是16,把16拿出来访问,之后要做的事情就是将16的两个孩子入队,将左孩子13和右孩子22入队。
数据结构笔记总结(5.10)二分搜索树的层序遍历

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

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

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

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

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

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

代码演示

// 二分搜索树的层序遍历
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);
    }
}

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

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

广度优先遍历的意义

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

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

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

源码下载

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

导航目录

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

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(5.10)二分搜索树的层序遍历
分享到:
赞(0)

评论抢沙发

评论前必须登录!