3.3.4 队列在层次遍历中的应用
原书定位
印刷页P93起,对应PDF第105页。下文为目视整理的知识提要;完整内容见原书对照。
根结点先入队;循环取出队头并访问,再按顺序将其孩子入队,直到队空。FIFO 保证先发现的同层结点先处理,下一层排在当前层之后。树的层次遍历时间为 ;队列最坏占 空间,实际最大长度由遍历过程决定。

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

表3.3 层次遍历二叉树的队列过程,原书P93。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P93起,对应PDF第105页。下文为目视整理的知识提要;完整内容见原书对照。
根结点先入队;循环取出队头并访问,再按顺序将其孩子入队,直到队空。FIFO 保证先发现的同层结点先处理,下一层排在当前层之后。树的层次遍历时间为 ;队列最坏占 空间,实际最大长度由遍历过程决定。

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

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

