劍指Offer第23題（從上往下列印二叉樹）

（本部落格旨在個人總結回顧）

題目描述：

       從上往下列印二叉樹的每個結點，同一層的結點按照從左到右的順序列印。例如輸入圖4.5中的二叉樹，則依次列印8、6、10、5、7、9、11。

        二叉樹結點的定義如下：

struct BinaryTreeNode
{
    int             m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
           

解題思路：

        利用隊列先進先出特點解決此題。

完整代碼： 

#include "stdafx.h"
#include <iostream>
#include <deque>
using namespace std;

struct BinaryTreeNode
{
    int             m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};


/*
 * @name   PrintTopToButtom
 * @brief  從上往下輸出二叉樹
 * @param  [in] BinaryTreeNode * pRoot
 * @return void
 */
void PrintTopToButtom(BinaryTreeNode* pRoot)
{
    if (pRoot == NULL)
    {
        return;
    }
    BinaryTreeNode* pTmpNode = NULL;
    deque<BinaryTreeNode*> dequeTmp;
    dequeTmp.push_back(pRoot);
    while (dequeTmp.size() != 0)
    {
        pTmpNode = dequeTmp.front();
        dequeTmp.pop_front();
        cout << pTmpNode->m_nValue << " ";
        if (NULL != pTmpNode->m_pLeft)
        {
            dequeTmp.push_back(pTmpNode->m_pLeft);
        }
        if (NULL != pTmpNode->m_pRight)
        {
            dequeTmp.push_back(pTmpNode->m_pRight);
        }
    }
    cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    //建立二叉樹
    //
    //          8
    //       /     \ 
    //      6      10
    //     / \     / \
    //    5   7   9   11
    //
    BinaryTreeNode* pRoot = new BinaryTreeNode();
    pRoot->m_nValue = 8;

    BinaryTreeNode* pTmpNode = new BinaryTreeNode();
    pTmpNode->m_nValue = 6;
    pRoot->m_pLeft = pTmpNode;

    pTmpNode = new BinaryTreeNode();
    pTmpNode->m_nValue = 5;
    pRoot->m_pLeft->m_pLeft = pTmpNode;

    pTmpNode = new BinaryTreeNode();
    pTmpNode->m_nValue = 7;
    pRoot->m_pLeft->m_pRight = pTmpNode;

    pTmpNode = new BinaryTreeNode();
    pTmpNode->m_nValue = 10;
    pRoot->m_pRight = pTmpNode;

    pTmpNode = new BinaryTreeNode();
    pTmpNode->m_nValue = 9;
    pRoot->m_pRight->m_pLeft = pTmpNode;

    pTmpNode = new BinaryTreeNode();
    pTmpNode->m_nValue = 11;
    pRoot->m_pRight->m_pRight = pTmpNode;

    PrintTopToButtom(pRoot);

    system("pause");
    return 0;
}
           

運作結果：