[科普中国]-逐层遍历

二叉树的层次遍历 ，顾名思义就是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问。

算法思想用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。

在进行层次遍历的时候，设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

1、访问该元素所指向的节点

2、若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。

实现Java语言import java.util.*;class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }public class Solution { private ArrayList list=new ArrayList(); private Queue queue=new LinkedList(); public ArrayList PrintFromTopToBottom(TreeNode root) { if(root!=null){ queue.offer(root); } while(queue.peek()!=null){ removeNext(); } return list; } /* *每次在队列中取出一个节点，并将其值插入到List中， *此外每次取出一个节点需要把这个节点的子节点插入队列 */ public void removeNext(){ TreeNode temp=queue.poll(); if(temp!=null){ list.add(temp.val); if(temp.left!=null){ queue.offer(temp.left); } if(temp.right!=null){ queue.offer(temp.right); } } else return; }}1

C++语言由于遍历中所使用的数据结构是一个队列而不是栈，因此写一个按层遍历的递归程序很困难。如下程序用来对二叉树进行逐层遍历，它采用了队列数据结构。队列中的元素指向二叉树节点。当然，也可以采用公式化队列。

template void LevelOrder(BinaryTreeNode *t){// 对* t逐层遍历L i n k e d Q u e u e Q;while (t) {Visit(t); // 访问t// 将t的右孩子放入队列if (t->LeftChild) Q.Add(t->LeftChild);if (t->RightChild) Q.Add(t->RightChild);// 访问下一个节点try {Q.Delete(t);}catch (OutOfBounds) {return;}}}程序中，仅当树非空时，才进入w h i l e循环。首先访问根节点，然后把其子节点加到队列中。当队列添加操作失败时，由Add引发NoMem异常，由于没有捕获该异常，因此当异常发生时LevelOrder函数将退出。在把t的子节点加入队列后，要从队列中删除t元素。若队列为空，则由Delete引发OutOfBounds异常，这由catch语句来处理。因为一个空队列意味着遍历的结束，所以执行return语句。若队列非空，则Delete把所删除的元素返回至变量t。被删除的元素指向下一个欲访问的节点。2

复杂性分析设二叉树中元素数目为n。逐层遍历的空间复杂性均为O (n)，时间复杂性为O(n)。当t为满二叉树时，逐层遍历所需要的队列空间为O(n)。每个遍历算法花在树中每个节点上的时间为O(1) (假设访问一个节点的时间为( 1 ) )。2

本词条内容贡献者为:

王伟 - 副教授 - 上海交通大学