二叉樹層序遍歷

1、二叉樹層序遍歷微軟面試題，難度系數(shù)低，題目描述如下：輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右 的順序打印。例如輸入86 105 7 9 11輸出 8 6 10 5 7 9 11.邏輯分析：1、顯然就是二叉樹的層序遍歷，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的時候，多數(shù)人都對 先序，中序，后序遍歷感到熟悉，這三種都屬于深度搜索，而層序遍歷則是廣度 搜索。盡管如此，微軟以此為面試題目，還是相當(dāng)便宜面試者。2、對于層序遍歷，類似先序遍歷的想法，我們知道，先序遍歷的循環(huán)實現(xiàn) 需要借助輔助棧來實現(xiàn)，棧是一種LIF0的數(shù)據(jù)結(jié)構(gòu)，即后進先出，last in first out,那么,對于層序遍歷來說，

2、過程剛好相反，即FIFO, first in first out, 我們每次將根節(jié)點入隊列，當(dāng)隊列非空，則將front賦給臨時指針temp,繼而輸 出根節(jié)點的衛(wèi)星域，接下來判斷根節(jié)點左右孩子是否為空，非空則入隊列，上述 工作以后，再度從隊列中取元素，隊列空，則循環(huán)結(jié)束。void printByLevel (BSTreeNode* root)queueBSTREENODE* Q;BSTreeNode* p = root;if （p 二二 NULL）return ;Q. push (p)；while ( ! Q. empty ()p = Q front ()；Q. pop ();cout p-m_

3、nValue endl;if (p-m_pLeft)Q.push (p-m_pLeft)；if (p-m_pRight)Q.push (p-m_pRight)；3、因為之前做的是BSTree的鏡像翻轉(zhuǎn)例子，這里為了方便，不再改寫為 BTree,畢竟二叉排序樹也是二叉樹的一種。完整代碼如下：include IOSTREAMinclude using namespace std;typedef struct BSTreeNode/a node in the BSTintm_nValue;/Vaiue of nodestruct BSTreeNode *m_pLeft;/left child of

4、node/right child of nodestruct BSTreeNode *m_pRight;/right child of node;BSTreeNode;void printByLevel (BSTreeNode* root)queueBSTREENODE* Q;BSTreeNode* p 二 root;if (p 二二 NULL)return ;Q push (p)；while ( ! Q. empty ()p = Q front ()；Q. pop ()；cout p-m_nValue endl;if (p-m_pLeft)Qpush (p-m_pLeft)；if (p-m_

5、pRight)Qpush (p-m_pRight)；int main ()BSTreeNode node 7;node0m_nValue 二 8;nodeL0m_pLeft 二 &nodel;node L0m_pRight 二 &node2;node L1m_nValue 二 6;node L1m_pLeft 二 &node3;node L1m_pRight 二 &node4;node2m_nValue 二 10;node2m_pLeft 二 &node5;node2m_pRight 二 &node6;node3m_nValue 二 5;node3m_pLeft 二 NULL;node3m_pRight 二 NULL;node4 m_nValue 二 7;node4m_pLeft 二 NULL;node4. m_pRight 二 NULL;node5m_nValue 二 9;node5m_pLeft 二 NULL;node5m_pRight 二 NULL;node6m_nValue 二 11:node6m_pLeft