二叉树 的遍历实质问题就是，将二维结构线性化。
深度优先遍历对应的是前序、中序、后续遍历；广度优先对应的是层序遍历。
今天深入学习一下层序遍历，层序遍历也是面试中出现频率较多的一个知识点。
如下二叉树，它的层序遍历结果为：1 – 2 – 5 – 3 – 4 – 6
二叉树
我们用队列对它进行层序遍历：
用队列进行层序遍历过程
得出层序遍历的基本过程如下：
- 把根节点放入队列中
- 从队列中取出一个元素
- 访问该元素所有节点
- 若该元素左右节点非空，则将其左右节点顺序入队列
用C++和 Python 实现层序遍历的基本过程：
C++：
void leverOrder(pTree node &Tree)
{
queue<pTreeNode> q;
if(Tree != NULL)
{
q. push (Tree);//root 进队列
}
while(q.empty() == false )
{
q.pop();//已经遍历郭的队列元素出队列
cout << q.front()->data<<“->”;//输出遍历结果
if(q.front()->leftPtr != NULL)
{//如果有左孩子，左孩子入队列
q.push(q.front()->leftPtr);
}
if(q.front()->rightPtr != NULL)
{//如果有右孩子，右孩子入队列
q.push(q.front()->rightPtr);
}
}
}
Python：
from collections import deque
#导入双向队列
class BTree( object ):
#定义二叉树
def __init__(self):
self._root = None
self._size = 0
def leverOrder(self):
#创建一个队列
q = deque()
#root加入队列
q.append(self._root)
btree = []
#队列不空
while q:
#队列头出队列
node = q.popleft()
#输出列表，追加
btree.append(node.data)
#如果有左孩子，左孩子入队列
if node.lft:
q.append(node.lft)
#如果有右孩子，右孩子入队列
if node.rgt:
q.append(node.rgt)
return btree
层序遍历的应用：
- 可以用来求二叉树的高度和宽度
- 判断二叉树是否为完全二叉树
层序遍历应用场景丰富，很受面试官青睐。
