題目：輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹(shù)中，左子樹(shù)的結(jié)點(diǎn)都大于右子樹(shù)的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹(shù)的鏡像轉(zhuǎn)換。
例如輸入：
8
/ \
6 10
/\ /\
5 7 9 11
輸出：
8
/ \
10 6
/\ /\
11 9 7 5
定義二元查找樹(shù)的結(jié)點(diǎn)為：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
分析：盡管我們可能一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺(jué)，就是交換結(jié)點(diǎn)的左右子樹(shù)。我們?cè)囍诒闅v例子中的二元查找樹(shù)的同時(shí)來(lái)交換每個(gè)結(jié)點(diǎn)的左右子樹(shù)。遍歷時(shí)首先訪問(wèn)頭結(jié)點(diǎn)8，我們交換它的左右子樹(shù)得到：
8
/ \
10 6
/\ /\
9 11 5 7
我們發(fā)現(xiàn)兩個(gè)結(jié)點(diǎn)6和10的左右子樹(shù)仍然是左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值，我們?cè)僭囍粨Q他們的左右子樹(shù)，得到：
8
/ \
10 6
/\ /\
11 9 7 5
剛好就是要求的輸出。
上面的分析印證了我們的直覺(jué)：在遍歷二元查找樹(shù)時(shí)每訪問(wèn)到一個(gè)結(jié)點(diǎn)，交換它的左右子樹(shù)。這種思路用遞歸不難實(shí)現(xiàn)，將遍歷二元查找樹(shù)的代碼稍作修改就可以了。參考代碼如下：
///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) recursively
// the head of BST in initial call
///////////////////////////////////////////////////////////////////////
void MirrorRecursively(BSTreeNode *pNode)
{
if(!pNode)
return;
// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
// mirror left child sub-tree if not null
if(pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);
// mirror right child sub-tree if not null
if(pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}
由于遞歸的本質(zhì)是編譯器生成了一個(gè)函數(shù)調(diào)用的棧，因此用循環(huán)來(lái)完成同樣任務(wù)時(shí)最簡(jiǎn)單的辦法就是用一個(gè)輔助棧來(lái)模擬遞歸。首先我們把樹(shù)的頭結(jié)點(diǎn)放入棧中。在循環(huán)中，只要棧不為空，彈出棧的棧頂結(jié)點(diǎn)，交換它的左右子樹(shù)。如果它有左子樹(shù)，把它的左子樹(shù)壓入棧中;如果它有右子樹(shù)，把它的右子樹(shù)壓入棧中。這樣在下次循環(huán)中就能交換它兒子結(jié)點(diǎn)的左右子樹(shù)了。參考代碼如下：
///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) Iteratively
// Input: pTreeHead: the head of BST
///////////////////////////////////////////////////////////////////////
void MirrorIteratively(BSTreeNode *pTreeHead)
{
if(!pTreeHead)
return;
std::stackstackTreeNode;
stackTreeNode.push(pTreeHead);
while(stackTreeNode.size())
{
BSTreeNode *pNode = stackTreeNode.top();
stackTreeNode.pop();
// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
// push left child sub-tree into stack if not null
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);
// push right child sub-tree into stack if not null
if(pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}
從上往下遍歷二元樹(shù)
題目：輸入一顆二元樹(shù)，從上往下按層打印樹(shù)的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。
例如輸入
8
/ \
6 10
/\ /\
5 7 9 11
輸出8 6 10 5 7 9 11。
分析：這曾是微軟的一道面試題。這道題實(shí)質(zhì)上是要求遍歷一棵二元樹(shù)，只不過(guò)不是我們熟悉的前序、中序或者后序遍歷。
我們從樹(shù)的根結(jié)點(diǎn)開(kāi)始分析。自然先應(yīng)該打印根結(jié)點(diǎn)8，同時(shí)為了下次能夠打印8的兩個(gè)子結(jié)點(diǎn)，我們應(yīng)該在遍歷到8時(shí)把子結(jié)點(diǎn)6和10保存到一個(gè)數(shù)據(jù)容器中�，F(xiàn)在數(shù)據(jù)容器中就有兩個(gè)元素6 和10了。按照從左往右的要求，我們先取出6訪問(wèn)。打印6的同時(shí)要把6的兩個(gè)子結(jié)點(diǎn)5和7放入數(shù)據(jù)容器中，此時(shí)數(shù)據(jù)容器中有三個(gè)元素10、5和7。接下來(lái)我們應(yīng)該從數(shù)據(jù)容器中取出結(jié)點(diǎn)10訪問(wèn)了。注意10比5和7先放入容器，此時(shí)又比5和7先取出，就是我們通常說(shuō)的先入先出。因此不難看出這個(gè)數(shù)據(jù)容器的類型應(yīng)該是個(gè)隊(duì)列。
既然已經(jīng)確定數(shù)據(jù)容器是一個(gè)隊(duì)列，現(xiàn)在的問(wèn)題變成怎么實(shí)現(xiàn)隊(duì)列了。實(shí)際上我們無(wú)需自己動(dòng)手實(shí)現(xiàn)一個(gè)，因?yàn)镾TL已經(jīng)為我們實(shí)現(xiàn)了一個(gè)很好的deque(兩端都可以進(jìn)出的隊(duì)列)，我們只需要拿過(guò)來(lái)用就可以了。
我們知道樹(shù)是圖的一種特殊退化形式。同時(shí)如果對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實(shí)際上是一種廣度優(yōu)先遍歷。因此這道題的本質(zhì)是在二元樹(shù)上實(shí)現(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);
}
}
