公眾號:mywangxiao
及時發(fā)布考試資訊
分享考試技巧、復(fù)習(xí)經(jīng)驗
新浪微博 @wangxiaocn關(guān)注微博
聯(lián)系方式 400-18-8000
-從上往下遍歷二元樹
題目:輸入一顆二元樹,從上往下按層打印樹的每個結(jié)點,同一層中按照從左往右的順序打印。
例如輸入
8
/ \
6 10
/\ /\
5 7 9 11
輸出8 6 10 5 7 9 11。
分析:這曾是微軟的一道面試題。這道題實質(zhì)上是要求遍歷一棵二元樹,只不過不是我們熟悉的前序、中序或者后序遍歷。
我們從樹的根結(jié)點開始分析。自然先應(yīng)該打印根結(jié)點8,同時為了下次能夠打印8的兩個子結(jié)點,我們應(yīng)該在遍歷到8時把子結(jié)點6和10保存到一個數(shù)據(jù)容器中。現(xiàn)在數(shù)據(jù)容器中就有兩個元素6 和10了。按照從左往右的要求,我們先取出6訪問。打印6的同時要把6的兩個子結(jié)點5和7放入數(shù)據(jù)容器中,此時數(shù)據(jù)容器中有三個元素10、5和7。接下來我們應(yīng)該從數(shù)據(jù)容器中取出結(jié)點10訪問了。注意10比5和7先放入容器,此時又比5和7先取出,就是我們通常說的先入先出。因此不難看出這個數(shù)據(jù)容器的類型應(yīng)該是個隊列。
既然已經(jīng)確定數(shù)據(jù)容器是一個隊列,現(xiàn)在的問題變成怎么實現(xiàn)隊列了。實際上我們無需自己動手實現(xiàn)一個,因為STL已經(jīng)為我們實現(xiàn)了一個很好的deque(兩端都可以進(jìn)出的隊列),我們只需要拿過來用就可以了。
我們知道樹是圖的一種特殊退化形式。同時如果對圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解,將不難看出這種遍歷方式實際上是一種廣度優(yōu)先遍歷。因此這道題的本質(zhì)是在二元樹上實現(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);
}
}
相關(guān)推薦:
(責(zé)任編輯:)