-求二元查找樹的鏡像

題目：輸入一顆二元查找樹，將該樹轉(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)的左右子樹。我們試著在遍歷例子中的二元查找樹的同時(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)的值，我們再試著交換他們的左右子樹，得到：

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)

相關(guān)推薦：

計(jì)算機(jī)軟件水平考試輔導(dǎo)資料

計(jì)算機(jī)軟件水平考試精品輔導(dǎo)班

（責(zé)任編輯：）