document.write('为了实现对二叉树的层序遍历，就要求在遍历一个结点的同时记录下它的孩子结点的信息，然后按照这个记
录的顺序来访问结点的数据，在实现的时候可以采用队列来存储当前遍历到的结点的孩子结点，从而实现二
叉树的层序遍历，遍历过程如下图所示。
在上图中，图(1)首先把根结点1放到队列里面，然后开始遍历。图(2)队列首元素(结点1)出队列，同时它的
孩子结点2和结点3进队列；图(3)接着出队列的结点为2，同时把它的孩子结点4和结点5放到队列里，依此类
推就可以实现对二叉树的层序遍历。
实现代码如下：
from collections import deque
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rchild=None
#方法功能: 把有序数组转换为二叉树
def arraytotree(arr,start,end):
roo=None
if end＞=start:
root=BiTNode();
mid=(start+end+1)/2;
#树的根结点为数组中间的元素
root.data=arr[mid];
#递归的用左半部分数组构造root的左子树
root.lchild=arraytotree(arr,start,mid-1);
#递归的用右半部分数组构造root的右子树
root.rchild=arraytotree(arr, mid+1, end);
else:
root=None
return root
"""
方法功能: 用层序遍历的方式打印出二叉树结点的内容
输入参数: root:二叉树根结点
"""
def printTreeLayer(root):
if root==None:
return;
queue=deque()
#树根结点进队列
queue.append(root)
while len(queue)＞0:
p=queue,popleft()
#访问当前结点
print(p.data),
#如果这个结点的左孩子不为空则入队列
if p.lchild!=None:
queue.append(p.lchild)
#如果这个结点的右孩子不为空则入队列
if p.rchild!=None:
queue.append(p.rchild);
if __name__=="__main__":
arr=[1,2,3,4,5,6,7,8,9,10]
root=arraytotree(arr, 0,len(arr)-1);
print "树的层序遍历结果为:",
printTreeLaver (root);
程序的运行结果为：
树的层序遍历结果为：6 3 9 2 5 8 10 1 47
算法性能分析：
在二叉树的层序遍历过程中，对树中的各个结点只进行了一次访问，因此，时间复杂度为O(N)，此外，这
种方法还使用了队列来保存遍历的中间结点，所使用队列的大小取决于二叉树中每一层中结点个数的最大
值。具有N个结点的完全二叉树的深度为h=log2N+1。而深度为h的这一层最多的结点个数为2h-1=n/2。也
就是说队列中可能的最多的结点个数为N/2。因此，这种算法的空间复杂度为O(N)。
');
![\"360截图20190815220727407.jpg\"](\"http://www.alatiku.com/d/file/shiti/29741350039910a89fd322a41ccba393.jpg\")