c++樹，知道前序和中序求後序遍歷，二叉樹後序遍歷

c++樹，知道前序和中序求後序遍歷，二叉樹後序遍歷

經常有面試題就是知道一棵樹的前序遍歷和中序遍歷讓你寫出後序遍歷，這個慢慢畫是能畫出來的，但是要很快的弄出來還是要懂原理。

首先說一下三種遍歷：所謂的前序後序和中序都是遍歷時遍歷根節點的順序。子樹的話依照從做左到右的順序，比如前序就是：中-》左-》右，中序就是：左-》中-》右。

現在前序是：ABDGCEFH

中序是：DGBAECHF

想要求後序就要把樹重建出來，我們理一下思路。

1.由前序遍歷的性質可以知道A必然是樹的根節點

2.中序遍歷中A之前的就肯定是A的左子樹，A後面的就是A的右子樹。

好的，我們現在可以把中序分一下，變成：DGB  | A | ECHF

同樣左子樹和右子樹在前序上也是連續的，所以我們可以分成 A | BDG | CEFH

你一定已經想到遞歸了，對，如果只看左子樹的話又當成一個新的樹，題目變成已知前序為：BDG，中序為：DGB，求原來的樹。右子樹同理。

上代碼，自己瞎寫的。。。。多多包涵

#include <iostream>
#include <string>

using namespace std;
struct Node
{
    char val ;
    Node *rc , *lc ;
} ;
Node* rebuild(string pre,string mid)
{
    int i , len ;
    Node *head = new Node() ;
    head->val = pre[0] ;
    //cout << pre<< "  " << mid << endl ;
    len = mid.length() ;
    for(i=0;i<len;i++)
    {
        if(pre[0]==mid[i])
        {
            if(i!=0)
            {
                head->lc = rebuild(pre.substr(1,i),mid.substr(0,i));//左子樹
            }
            else{
                head->lc = NULL ;
            }
            if(i!=len-1)
            {
                head->rc = rebuild(pre.substr(i+1,len-1-i),mid.substr(i+1,len-1-i));//右子樹
            }
            else{
                head->rc = NULL ;
            }
        }
    }
    return head ;
}
void after(Node *head)
{
    if(head==NULL)
    {
        return ;
    }
    else{
        if(head->lc!=NULL)
            after(head->lc) ;
        if(head->rc!=NULL)
            after(head->rc) ;
        cout << head->val << endl ;
    }
}
int main()
{
    string pre , mid ;
    Node *head = NULL ;
    while(cin>>pre>>mid)
    {
        Node * head ;
        head = rebuild(pre,mid) ;
        after(head) ;
    }
    return 0;
}

注意substr這個函數的參數的意思是substr（start，length),遞歸左子樹的時候，左子樹子串前序和中序的length等於i，並不是到i那個位置結束。