點(diǎn)擊進(jìn)入>>>>>

    求二元查找樹的鏡像

    題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。

    例如輸入：

    8

    /\

    610

    /\/\

    57911

    輸出：

    8

    /\

    106

    /\/\

    11975

    定義二元查找樹的結(jié)點(diǎn)為：

    structBSTreeNode//anodeinthebinarysearchtree(BST)

    {

    intm_nValue;//valueofnode

    BSTreeNode*m_pLeft;//leftchildofnode

    BSTreeNode*m_pRight;//rightchildofnode

    };

    分析：盡管我們可能一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺，就是交換結(jié)點(diǎn)的左右子樹。我們?cè)囍诒闅v例子中的二元查找樹的同時(shí)來交換每個(gè)結(jié)點(diǎn)的左右子樹。遍歷時(shí)首先訪問頭結(jié)點(diǎn)8，我們交換它的左右子樹得到：

    8

    /\

    106

    /\/\

    91157

    我們發(fā)現(xiàn)兩個(gè)結(jié)點(diǎn)6和10的左右子樹仍然是左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值，我們?cè)僭囍粨Q他們的左右子樹，得到：

    8

    /\

    106

    /\/\

    11975

    剛好就是要求的輸出。

    上面的分析印證了我們的直覺：在遍歷二元查找樹時(shí)每訪問到一個(gè)結(jié)點(diǎn)，交換它的左右子樹。這種思路用遞歸不難實(shí)現(xiàn)，將遍歷二元查找樹的代碼稍作修改就可以了。參考代碼如下：

    ///////////////////////////////////////////////////////////////////////

    //MirroraBST(swaptheleftrightchildofeachnode)recursively

    //theheadofBSTininitialcall

    ///////////////////////////////////////////////////////////////////////

    voidMirrorRecursively(BSTreeNode*pNode)

    {

    if(!pNode)

    return;

    //swaptherightandleftchildsub-tree

    BSTreeNode*pTemp=pNode->m_pLeft;

    pNode->m_pLeft=pNode->m_pRight;

    pNode->m_pRight=pTemp;

    //mirrorleftchildsub-treeifnotnull

    if(pNode->m_pLeft)

    MirrorRecursively(pNode->m_pLeft);

    //mirrorrightchildsub-treeifnotnull

    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)的左右子樹了。參考代碼如下：

    ///////////////////////////////////////////////////////////////////////

    //MirroraBST(swaptheleftrightchildofeachnode)Iteratively

    //Input:pTreeHead:theheadofBST

    ///////////////////////////////////////////////////////////////////////

    voidMirrorIteratively(BSTreeNode*pTreeHead)

    {

    if(!pTreeHead)

    return;

    std::stackstackTreeNode;

    stackTreeNode.push(pTreeHead);

    while(stackTreeNode.size())

    {

    BSTreeNode*pNode=stackTreeNode.top();

    stackTreeNode.pop();

    //swaptherightandleftchildsub-tree

    BSTreeNode*pTemp=pNode->m_pLeft;

    pNode->m_pLeft=pNode->m_pRight;

    pNode->m_pRight=pTemp;

    //pushleftchildsub-treeintostackifnotnull

    if(pNode->m_pLeft)

    stackTreeNode.push(pNode->m_pLeft);

    //pushrightchildsub-treeintostackifnotnull

    if(pNode->m_pRight)

    stackTreeNode.push(pNode->m_pRight);

    }

    }

    從上往下遍歷二元樹

    題目：輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。

    例如輸入

    8

    /\

    610

    /\/\

    57911

    輸出861057911。

    分析：這曾是微軟的一道面試題。這道題實(shí)質(zhì)上是要求遍歷一棵二元樹，只不過不是我們熟悉的前序、中序或者后序遍歷。

    我們從樹的根結(jié)點(diǎn)開始分析。自然先應(yīng)該打印根結(jié)點(diǎn)8，同時(shí)為了下次能夠打印8的兩個(gè)子結(jié)點(diǎn)，我們應(yīng)該在遍歷到8時(shí)把子結(jié)點(diǎn)6和10保存到一個(gè)數(shù)據(jù)容器中。現(xiàn)在數(shù)據(jù)容器中就有兩個(gè)元素6和10了。按照從左往右的要求，我們先取出6訪問。打印6的同時(shí)要把6的兩個(gè)子結(jié)點(diǎn)5和7放入數(shù)據(jù)容器中，此時(shí)數(shù)據(jù)容器中有三個(gè)元素10、5和7。接下來我們應(yīng)該從數(shù)據(jù)容器中取出結(jié)點(diǎn)10訪問了。注意10比5和7先放入容器，此時(shí)又比5和7先取出，就是我們通常說的先入先出。因此不難看出這個(gè)數(shù)據(jù)容器的類型應(yīng)該是個(gè)隊(duì)列。

    既然已經(jīng)確定數(shù)據(jù)容器是一個(gè)隊(duì)列，現(xiàn)在的問題變成怎么實(shí)現(xiàn)隊(duì)列了。實(shí)際上我們無需自己動(dòng)手實(shí)現(xiàn)一個(gè)，因?yàn)镾TL已經(jīng)為我們實(shí)現(xiàn)了一個(gè)很好的deque(兩端都可以進(jìn)出的隊(duì)列)，我們只需要拿過來用就可以了。

    我們知道樹是圖的一種特殊退化形式。同時(shí)如果對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實(shí)際上是一種廣度優(yōu)先遍歷。因此這道題的本質(zhì)是在二元樹上實(shí)現(xiàn)廣度優(yōu)先遍歷。

    參考代碼：

    #include

    #include

    usingnamespacestd;

    structBTreeNode//anodeinthebinarytree

    {

    intm_nValue;//valueofnode

    BTreeNode*m_pLeft;//leftchildofnode

    BTreeNode*m_pRight;//rightchildofnode

    };

    ///////////////////////////////////////////////////////////////////////

    //Printabinarytreefromtopleveltobottomlevel

    //Input:pTreeRoot-therootofbinarytree

    ///////////////////////////////////////////////////////////////////////

    voidPrintFromTopToBottom(BTreeNode*pTreeRoot)

    {

    if(!pTreeRoot)

    return;

    //getaemptyqueue

    dequedequeTreeNode;

    //inserttherootatthetailofqueue

    dequeTreeNode.push_back(pTreeRoot);

    while(dequeTreeNode.size())

    {

    //getanodefromtheheadofqueue

    BTreeNode*pNode=dequeTreeNode.front();

    dequeTreeNode.pop_front();

    //printthenode

    cout<<pNode->m_nValue<<'';

    //printitsleftchildsub-treeifithas

    if(pNode->m_pLeft)

    dequeTreeNode.push_back(pNode->m_pLeft);

    //printitsrightchildsub-treeifithas

    if(pNode->m_pRight)

    dequeTreeNode.push_back(pNode->m_pRight);

    }

    }

    相關(guān)推薦:

  2015年上半年軟考成績查詢攻略

  2015年下半年軟考報(bào)名時(shí)間

  2015年上半年軟考報(bào)名入口

    2015年上半年軟考成績多少分?jǐn)?shù)及格？

    2015年5月軟考證書什么時(shí)候領(lǐng)?。?/a>