從上往下遍歷二元樹

　　題目：輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。

　　例如輸入

　　8

　　/ \

　　6 10

　　/\ /\

　　5 7 9 11

　　輸出8 6 10 5 7 9 11。

　　分析：這曾是微軟的一道面試題。這道題實質上是要求遍歷一棵二元樹，只不過不是我們熟悉的前序、中序或者后序遍歷。

　　我們從樹的根結點開始分析。自然先應該打印根結點8，同時為了下次能夠打印8的兩個子結點，我們應該在遍歷到8時把子結點6和10保存到一個數(shù)據(jù)容器中�，F(xiàn)在數(shù)據(jù)容器中就有兩個元素6 和10了。按照從左往右的要求，我們先取出6訪問。打印6的同時要把6的兩個子結點5和7放入數(shù)據(jù)容器中，此時數(shù)據(jù)容器中有三個元素10、5和7。接下來我們應該從數(shù)據(jù)容器中取出結點10訪問了。注意10比5和7先放入容器，此時又比5和7先取出，就是我們通常說的先入先出。因此不難看出這個數(shù)據(jù)容器的類型應該是個隊列。

　　既然已經(jīng)確定數(shù)據(jù)容器是一個隊列，現(xiàn)在的問題變成怎么實現(xiàn)隊列了。實際上我們無需自己動手實現(xiàn)一個，因為STL已經(jīng)為我們實現(xiàn)了一個很好的deque(兩端都可以進出的隊列)，我們只需要拿過來用就可以了。

　　我們知道樹是圖的一種特殊退化形式。同時如果對圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實際上是一種廣度優(yōu)先遍歷。因此這道題的本質是在二元樹上實現(xiàn)廣度優(yōu)先遍歷。

　　參考代碼：

　　#include

　　#include

　　using namespace std;

　　struct BTreeNode // a node in the binary tree

　　{

　　int m_nValue; // value of node

　　BTreeNode *m_pLeft; // left child of node

　　BTreeNode *m_pRight; // right child of node

　　};

　　///////////////////////////////////////////////////////////////////////

　　// Print a binary tree from top level to bottom level

　　// Input: pTreeRoot - the root of binary tree

　　///////////////////////////////////////////////////////////////////////

　　void PrintFromTopToBottom(BTreeNode *pTreeRoot)

　　{

　　if(!pTreeRoot)

　　return;

　　// get a empty queue

　　deque dequeTreeNode;

　　// insert the root at the tail of queue

　　dequeTreeNode.push_back(pTreeRoot);

　　while(dequeTreeNode.size())

　　{

　　// get a node from the head of queue

　　BTreeNode *pNode = dequeTreeNode.front();

　　dequeTreeNode.pop_front();

　　// print the node

　　cout << pNode->m_nValue << ' ';

　　// print its left child sub-tree if it has

　　if(pNode->m_pLeft)

　　dequeTreeNode.push_back(pNode->m_pLeft);

　　// print its right child sub-tree if it has

　　if(pNode->m_pRight)

　　dequeTreeNode.push_back(pNode->m_pRight);

　　}

　　}

　　相關推薦：

　　2015年軟考信息技術處理員考前知識點總結匯總

　　2015年軟件水平考試《程序員》提高練習題匯總

　　2015軟件水平考試《程序員》知識點總結匯總