-求二元查找樹(shù)的鏡像

　　題目：輸入一顆二元查找樹(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)

　　相關(guān)推薦：

　　2017年計(jì)算機(jī)軟件水平考試時(shí)間公布(全年)

　　各地2017年軟件水平考試準(zhǔn)考證打印/領(lǐng)取時(shí)間匯總

　　考試吧特別策劃：2017年計(jì)算機(jī)軟考報(bào)考指南專題

　　軟考各科目模擬試題及答案※各科目復(fù)習(xí)指導(dǎo)匯總

　　軟考報(bào)考條件※軟考報(bào)名方法※考試大綱※科目

　　歷年軟考真題及答案匯總※軟件水平考試簡(jiǎn)介