【题目】

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

打印结果：8。6，10，5，7，9，11。

---

【分析】

二叉树遍历方式：前序。中序。后序，另一种广度优先遍历。在对图遍历时涉及到，而二叉树能够看作退化的图，从样例中能够看出，打印顺序是按层决定的，观察发现，打印完根节点之后，然后打印其左右节点。再继续打印左节点的左右孩子和右结点的左右孩子。由此能够发现，假设将其结点的左右孩子放在一个容器内，打印父节点后。再取其孩子依次打印，举上述样例进行说明：

1.打印8后。将6，10放在容器内。

2.打印6，将5，7放在容器内；

3.打印10。将9，11放入容器内；

4.打印5，5为叶子结点，没有左右孩子，故打印容器内下一个元素7，这样依次打印出9，11。

由上述可观察到。先进容器的先打印。先入先出的模式。而数据结构中队列就是这样的模式，所以这个容器採用队列模式，可是和普通队列略有不同，要注意到队列的元素存储的是一个二叉树结点。存在左右孩子成员，所以这里最好用数组队列，当然。链表队列也是能够，可是指针方面相对复杂一点。

由此，总结思路例如以下所看到的：

1、根节点进入队列。

2、打印根节点。左右孩子进入队列；

3、循环第二步，直至队列中没有元素进入了。

---

【測试代码】

//从上往下打印二叉树（层序遍历，广度优先遍历）#include
      
       #include
       
        using namespace std;struct BinaryTreeNode{    int m_nValue;    BinaryTreeNode* m_pLef;    BinaryTreeNode* m_pRight;};BinaryTreeNode* createBinaryTreeNode(int value){    BinaryTreeNode* pNode = new BinaryTreeNode();    pNode->m_nValue = value;    pNode->m_pLef = NULL;    pNode->m_pRight = NULL;    return pNode;}void connectBinaryTreeNode(BinaryTreeNode* pParent, BinaryTreeNode* pLeftChild,                           BinaryTreeNode* pRightChild){    if(!pParent || !pLeftChild || !pRightChild)        return;    pParent->m_pLef = pLeftChild;    pParent->m_pRight = pRightChild;}void printTreeFromTopToBottom(BinaryTreeNode* pRoot){    if(pRoot == NULL)        return;    queue
        
          btnQueue;    btnQueue.push(pRoot);    while(!btnQueue.empty())    {        BinaryTreeNode* pTemp = btnQueue.front();        btnQueue.pop();        printf("%d ",pTemp->m_nValue);        if(pTemp->m_pLef)            btnQueue.push(pTemp->m_pLef);        if(pTemp->m_pRight)            btnQueue.push(pTemp->m_pRight);    }}void test(){    BinaryTreeNode* pNode1 = createBinaryTreeNode(8);    BinaryTreeNode* pNode2 = createBinaryTreeNode(6);    BinaryTreeNode* pNode3 = createBinaryTreeNode(10);    BinaryTreeNode* pNode4 = createBinaryTreeNode(5);    BinaryTreeNode* pNode5 = createBinaryTreeNode(7);    BinaryTreeNode* pNode6 = createBinaryTreeNode(9);    BinaryTreeNode* pNode7 = createBinaryTreeNode(11);    connectBinaryTreeNode(pNode1,pNode2,pNode3);    connectBinaryTreeNode(pNode2,pNode4,pNode5);    connectBinaryTreeNode(pNode3,pNode6,pNode7);    printTreeFromTopToBottom(pNode1);}int main(){    test();    return 0;}
        
       
      

---

【输出】

---

【程序说明】

1.对于本题来说，假设纯用c来实现，将会耗费非常大工作量，而考虑到现有编译器c和c++皆是兼容的，所以，最好还是利用c++封装库的优势，在c++库中存在队列。在这里仅仅需加上

#include<queue>

但这里须要注意，想要用c++库一定要加

using namespace std;

详细參照c++相关基础解说。不再赘述。

2.queue库中相关应用解释：

queue
      
        btnQueue;
      

初始化队列，元素类型为BinaryTreeNode*。队列名btnQueue

btnQueue.push(pRoot)

将根节点压入队列

btnQueue.pop()

出队列

btnQueue.empty()

队列是否为空，能够理解为空为1。非空为0

btnQueue.front()

队列的头

---

【參考文档】