题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入

思路：我们从树的根结点开始分析。自然先应该打印根结点8，同时为了下次能够打印8的两个子结点，我们应该在遍历到8时把子结点6和10保存到一个数据容器中。现在数据容器中就有两个元素6 和10了。按照从左往右的要求，我们先取出6访问。打印6的同时要把6的两个子结点5和7放入数据容器中，此时数据容器中有三个元素10、5和7。接下来我们应该从数据容器中取出结点10访问了。注意10比5和7先放入容器，此时又比5和7先取出，就是我们通常说的先入先出。因此不难看出这个数据容器的类型应该是个队列。
既然已经确定数据容器是一个队列，现在的问题变成怎么实现队列了。实际上我们无需自己动手实现一个，因为STL已经为我们实现了一个很好的deque（两端都可以进出的队列），我们只需要拿过来用就可以了



    

  1. #include <deque>  
    2. 

  2.  #include <iostream>  
    3. 

  3.  using namespace std;   
    4. 

  4.  struct BTreeNode // a node in the binary tree  
    5. 

  5.  { int m_nValue; // value of node  
    6. 

  6.  BTreeNode *m_pLeft; // left child of node  
    7. 

  7.  BTreeNode *m_pRight; // right child of node  
    8. 

  8.  };  
    9. 

  9.  
    10. 

  10. void PrintFromTopToBottom(BTreeNode *pTreeRoot)  
    11. 

  11. {  
    12. 

  12.     if(pTreeRoot==NULL)  
    13. 

  13.         return;  
    14. 

  14.     deque<BTreeNode *> queue;  
    15. 

  15.     queue.push_back(pTreeRoot);  
    16. 

  16.     while(queue.size())  
    17. 

  17.     {  
    18. 

  18.         BTreeNode *now=queue.front();  
    19. 

  19.         cout<<now->m_nValue<<"  ";  
    20. 

  20.         queue.pop_front();  
    21. 

  21.         if(now->m_pLeft!=NULL)  
    22. 

  22.             queue.push_back(now->m_pLeft);  
    23. 

  23.         if(now->m_pRight!=NULL)  
    24. 

  24.             queue.push_back(now->m_pRight);  
    25. 

  25.     }  
    26. 

  26. }  
    27. 

  27.  
    28. 

  28. void main()  
    29. 

  29. {  
    30. 

  30.     BTreeNode a[7];  
    31. 

  31.     a[0].m_nValue=8;  
    32. 

  32.     a[1].m_nValue=6;  
    33. 

  33.     a[2].m_nValue=10;  
    34. 

  34.     a[3].m_nValue=5;  
    35. 

  35.     a[4].m_nValue=7;  
    36. 

  36.     a[5].m_nValue=9;  
    37. 

  37.     a[6].m_nValue=11;  
    38. 

  38.     a[0].m_pLeft=&a[1];  
    39. 

  39.     a[0].m_pRight=&a[2];  
    40. 

  40.     a[1].m_pLeft=&a[3];  
    41. 

  41.     a[1].m_pRight=&a[4];  
    42. 

  42.     a[2].m_pLeft=&a[5];  
    43. 

  43.     a[2].m_pRight=&a[6];  
    44. 

  44.     a[3].m_pLeft=NULL;  
    45. 

  45.     a[3].m_pRight=NULL;  
    46. 

  46.     a[4].m_pLeft=NULL;  
    47. 

  47.     a[4].m_pRight=NULL;  
    48. 

  48.     a[5].m_pLeft=NULL;  
    49. 

  49.     a[5].m_pRight=NULL;  
    50. 

  50.     a[6].m_pLeft=NULL;  
    51. 

  51.     a[6].m_pRight=NULL;  
    52. 

  52.  PrintFromTopToBottom(&a[0]);  
    53. 

  53. } 
    54.