輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，重建出這棵二叉樹，假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如，輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出這棵滿足前序遍歷和中序遍歷的二叉樹并輸出它的頭結(jié)點。

成都創(chuàng)新互聯(lián)公司是一家專業(yè)提供元江縣企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計、H5技術(shù)、小程序制作等業(yè)務(wù)。10年已為元江縣眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)絡(luò)公司優(yōu)惠進(jìn)行中。

  對一棵二叉樹前序遍歷的順序是“根結(jié)點->左結(jié)點->右結(jié)點”，而中序遍歷的順序是“左結(jié)點->根節(jié)點->右結(jié)點”，因此，一般的思路都是醬紫的：

1. 前序遍歷列表中，第一個數(shù)據(jù)肯定是根節(jié)點，而中序遍歷列表中，第一個數(shù)據(jù)肯定是樹的最左結(jié)點，這樣就可以得知，在前序遍歷中，從根結(jié)點到最左結(jié)點一定是樹的最左分支，也就是“1->2->4”；

2. 接下來，在中序遍歷中，訪問完最左結(jié)點4之后因為其左結(jié)點為NULL要訪問的就是4的右分支的最左結(jié)點了，為7，而在前序遍歷中訪問到最左結(jié)點之后就要訪問右結(jié)點，發(fā)現(xiàn)也為7，說明7就是最左結(jié)點4的右分支上的最左結(jié)點，也就是只有7一個右結(jié)點；

3. 然后，在中序遍歷中訪問完最左結(jié)點也就是以4為根節(jié)點子樹之后，就要回到4結(jié)點的父節(jié)點了，也就是2，再往下訪問是根節(jié)點1，也就是2并沒有右結(jié)點；

4. 至此會發(fā)現(xiàn)1為根節(jié)點的左子樹已經(jīng)全部訪問完了；

  上面沒有再繼續(xù)往下分析，是因為會發(fā)現(xiàn)，上面說的一堆雖然能把樹給重建出來，但是很繁瑣，邏輯上有關(guān)聯(lián)卻難以疏通個條理出來，因此要想轉(zhuǎn)換為代碼來實現(xiàn)想必又是要大費周折；

  為什么分析到第四點就停下了，是因為第四點的式轉(zhuǎn)換新思路的一個起點：

1. 首先前面第一點中加粗的字體肯定是沒有問題的，前序遍歷中第一個數(shù)據(jù)一定是樹的根結(jié)點；

2. 再結(jié)合第四點，在中序遍歷中找到這個根結(jié)點，會發(fā)現(xiàn)以1為根結(jié)點前面的數(shù)據(jù)都是1的左子樹，有三個結(jié)點，那么在前序遍歷中1后面的三個結(jié)點都是屬于左子樹的；因此，在1后面的數(shù)據(jù)肯定也都是在1的右子樹上，有四個結(jié)點；

3. 接下來看在前序遍歷中跟在1后面的數(shù)據(jù)2是在1的左邊還是右邊，在左邊就是1的左結(jié)點，在右邊就是1的右結(jié)點；

4. 然后按照前序遍歷列表中的順序?qū)?看為新的根結(jié)點，那么在它左邊的數(shù)據(jù)就是它左子樹上的，右邊的數(shù)據(jù)就是右子樹上的，當(dāng)然是截止到前一個根結(jié)點1為止；然后就再次循環(huán)從上一步開始；

可畫圖如下：

  是不是會發(fā)現(xiàn)第二次的分析比第一次要簡單明了多了？而且邏輯上有重復(fù)性，這樣的分析用代碼實現(xiàn)起來會比較容易，可以用遞歸來實現(xiàn)：

#include <iostream>
#include <assert.h>
using namespace std;

typedef int data_type;

//首先定義一個樹結(jié)點的結(jié)構(gòu)體并實現(xiàn)構(gòu)造函數(shù)
struct BinaryTreeNode
{
    data_type _data;
    BinaryTreeNode* _Lnode;
    BinaryTreeNode* _Rnode;

    BinaryTreeNode(data_type data)
        :_data(data)
        ,_Lnode(NULL)
        ,_Rnode(NULL)
    {}  
};

//重建二叉樹，參數(shù)為兩個遍歷列表，樹結(jié)點的個數(shù)，還有遞歸所需要知道子樹的范圍
BinaryTreeNode* RebuildBinaryTree(const data_type* prevlist, const data_type *inlist, const size_t num, size_t head, size_t tail)
{
    assert(prevlist && inlist && num);  //判斷參數(shù)有效性
    //前序遍歷列表中第一個結(jié)點一定是樹的根結(jié)點
    BinaryTreeNode *root = new BinaryTreeNode(*prevlist);

    size_t root_index;
    //在中序遍歷列表中找出根結(jié)點
    for(root_index = 0; root_index < num; ++root_index)
    {   
        if(inlist[root_index] == *prevlist)
            break;
    }   
    if(inlist[root_index] != *prevlist)  //檢查給出的序列是否為有效的遍歷序列
    {   
        cout<<"Invalid parameter..."<<endl;
        exit(0);
    }   

    //當(dāng)結(jié)點個數(shù)大于0的時候才表示會有子結(jié)點，否則為已經(jīng)初始化過的NULL
    //傳遞首尾范圍的時候，是不包括根結(jié)點的，因此要注意
    size_t left_node_num = root_index - head;//根結(jié)點左邊的結(jié)點個數(shù)
    if(left_node_num > 0)
        root->_Lnode = RebuildBinaryTree(prevlist+1, inlist, num, head, root_index-1);

    size_t right_node_num = tail - root_index;//根結(jié)點右邊的結(jié)點個數(shù)
    if(right_node_num > 0)
        root->_Rnode = RebuildBinaryTree(prevlist+left_node_num+1, inlist, num, root_index+1, tail);

    return root;
}

//前序遍歷檢查二叉樹是否正確重建
void PreOrder(BinaryTreeNode *root)
{
    if(root != NULL)
    {
        cout<<root->_data<<"->";
        PreOrder(root->_Lnode);
        PreOrder(root->_Rnode);
    }
}

int main()
{
    data_type PrevOrderList[] = {1, 2, 4, 7, 3, 5, 6, 8};
    data_type InOrderList[] = {4, 7, 2, 1, 5, 3, 8, 6};

    size_t node_num = sizeof(PrevOrderList)/sizeof(PrevOrderList[0]);
    //這里的首部和尾部的表示范圍都是在中序遍歷中
    size_t head = 0;
    size_t tail = node_num-1;
    BinaryTreeNode* root = RebuildBinaryTree(PrevOrderList, InOrderList, node_num, head, tail);

    cout<<"the root data: "<<root->_data<<endl;
    PreOrder(root);
    cout<<"NULL"<<endl;
    return 0;
}

運行程序：

因為只是檢查書是否重建好，用遞歸寫樹的先序遍歷，輸出發(fā)現(xiàn)和給定的先序遍歷序列一樣，則樹重建完成。

《完》

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享題目：用一棵二叉樹的前序遍歷結(jié)果和中序遍歷結(jié)果還原這棵二叉樹——6-創(chuàng)新互聯(lián)
標(biāo)題URL：http://www.rwnh.cn/article40/doepeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計、響應(yīng)式網(wǎng)站、網(wǎng)站排名、企業(yè)網(wǎng)站制作、網(wǎng)站設(shè)計、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)