3.3.4 队列在层次遍历中的应用

教材导航 · 第3章

原书定位

印刷页P93起,对应PDF第105页。下文为目视整理的知识提要;完整内容见原书对照。

根结点先入队;循环取出队头并访问,再按顺序将其孩子入队,直到队空。FIFO 保证先发现的同层结点先处理,下一层排在当前层之后。树的层次遍历时间为 O(n)O(n);队列最坏占 O(n)O(n) 空间,实际最大长度由遍历过程决定。

图3.17 层次遍历示例二叉树

图3.17 层次遍历示例二叉树,原书P93。

表3.3 层次遍历二叉树的队列过程

表3.3 层次遍历二叉树的队列过程,原书P93。

对应练习

3.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P93,PDF第105页

原书对照,原书P94,PDF第106页