从上往下打印二叉树

题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

如图一棵二叉树,从上往下按层打印的顺序为8、6、10、5、7、9、11

 1 #include<iostream>
 2 #include<deque>
 3 
 4 using namespace std;
 5 
 6 typedef struct node
 7 {
 8 char data;//结点数据
 9 struct node *lchild,*rchild;//二叉树结点类型
10 }BSTree;//二叉树结点类型
11 
12 
13 void Createb(BSTree **p)//建立二叉树
14 {
15     char ch;
16     cin>>ch;
17     if(ch!='.')
18     {
19         *p=(BSTree*)malloc(sizeof(BSTree));//申请空间
20         (*p)->data=ch;//空间赋值
21         Createb(&(*p)->lchild);//生成左子树
22         Createb(&(*p)->rchild);//生成右子树
23     }
24     else *p=NULL;//空结点
25 }
26 
27 void PrintfFromTopToBottom(BSTree* root)//从上往下打印二叉树
28 {
29     if(!root)
30         return;
31     std::deque<BSTree *> dequeTreeNode;//选择队列容器，放置数据为二叉树指针
32     dequeTreeNode.push_back(root);//将二叉树的根从尾部入队
33     while(dequeTreeNode.size())//判断队是否为空
34     {
35         BSTree *pNode=dequeTreeNode.front();//pNode为队头指针
36         dequeTreeNode.pop_front();//队头指针出队
37         cout<<pNode->data<<' ';
38         if(pNode->lchild)
39             dequeTreeNode.push_back(pNode->lchild);//把二叉树左子树结点从尾部入队
40         if(pNode->rchild)
41             dequeTreeNode.push_back(pNode->rchild);//把二叉树右子树结点从尾部入队
42 
43     }
44 }
45 
46 void main()
47 {
48     BSTree *root;//二叉树根指针
49     Createb(&root);//生成二叉树
50     PrintfFromTopToBottom(root);//从上到下打印二叉树
51 }