查看匯總:2015軟件水平考試程序員精選題匯總
求二元查找樹的鏡像
題目:輸入一顆二元查找樹,將該樹轉(zhuǎn)換為它的鏡像,即在轉(zhuǎn)換后的二元查找樹中,左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入:
8
/ \
6 10
/\ /\
5 7 9 11
輸出:
8
/ \
10 6
/\ /\
11 9 7 5
定義二元查找樹的結(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
};
分析:盡管我們可能一下子不能理解鏡像是什么意思,但上面的例子給我們的直觀感覺,就是交換結(jié)點(diǎn)的左右子樹。我們?cè)囍诒闅v例子中的二元查找樹的同時(shí)來交換每個(gè)結(jié)點(diǎn)的左右子樹。遍歷時(shí)首先訪問頭結(jié)點(diǎn)8,我們交換它的左右子樹得到:
8
/ \
10 6
/\ /\
9 11 5 7
我們發(fā)現(xiàn)兩個(gè)結(jié)點(diǎn)6和10的左右子樹仍然是左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值,我們?cè)僭囍粨Q他們的左右子樹,得到:
8
/ \
10 6
/\ /\
11 9 7 5
剛好就是要求的輸出。
上面的分析印證了我們的直覺:在遍歷二元查找樹時(shí)每訪問到一個(gè)結(jié)點(diǎn),交換它的左右子樹。這種思路用遞歸不難實(shí)現(xiàn),將遍歷二元查找樹的代碼稍作修改就可以了。參考代碼如下:
///////////////////////////////////////////////////////////////////////
// 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)來完成同樣任務(wù)時(shí)最簡單的辦法就是用一個(gè)輔助棧來模擬遞歸。首先我們把樹的頭結(jié)點(diǎn)放入棧中。在循環(huán)中,只要棧不為空,彈出棧的棧頂結(jié)點(diǎn),交換它的左右子樹。如果它有左子樹,把它的左子樹壓入棧中;如果它有右子樹,把它的右子樹壓入棧中。這樣在下次循環(huán)中就能交換它兒子結(jié)點(diǎn)的左右子樹了。參考代碼如下:
///////////////////////////////////////////////////////////////////////
// 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);
}
}
相關(guān)推薦:
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |