二叉樹已知前序和中序求後序序列（C語言）

• 題目
• 大體思路
• 代碼

題目

已知二叉樹前序為 ABDFGCEH 後序序列為 BFDGACEH ，要求輸出後序周遊為 FGDBHECA

大體思路

又先序得出根，先序的根後為左樹一部分，我們再在中序序列裡找到先序的根，此處之前即為左樹（可以畫圖好好了解下），此處之後為右樹。然後就是不斷遞歸即可。

代碼

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100

typedef struct Node{
char data;
struct Node *Lchild;
struct Node *Rchild;
}BiTNode,*Bitree;

void PreTree(Bitree T)  //後序輸出樹
{   if(T==NULL) return;

     PreTree(T->Lchild);
     PreTree(T->Rchild);
     printf("%c",T->data);

}
char pre[MAX];
char mid[MAX];

int MidFind(int left,int right,char MID)  
{
    for(int i=left;i<=right;i++)
    {
        if(mid[i]==MID) return i;
    }
    return 0;
}

void Create(int left,int right,int *i,BiTNode **T)  //此題建立樹得先将孩子結點賦NULL，因為沒有使用者輸入以确定什麼時候把某個具體的結點賦為NULL
{//這是第一種建立二叉樹的寫法（二級指針法）
//這種感覺是把指針送進函數處理
    *T=(Bitree)malloc(sizeof(BiTNode));
    (*T)->data=pre[*i];
    (*T)->Lchild=NULL; 
    (*T)->Rchild=NULL;
    (*i)++;
    int midnumber =  MidFind(left,right,(*T)->data);
    if(midnumber>left)
    {
        Create(left,midnumber-1,i,(&((*T)->Lchild)));
    }
    if(midnumber<right)
    {
        Create(midnumber+1,right,i,(&((*T)->Rchild)));
    }

}

BiTNode* Create2(int left,int right,int *i)
{//第二中建立方式（注意傳回！！！）  
//這種感覺是把指針讓函數處理（自己不進去）
BiTNode *T;
    T=(Bitree)malloc(sizeof(BiTNode));
    T->data=pre[*i];
    T->Lchild=NULL;
    T->Rchild=NULL;
    (*i)++;
    int midnumber =  MidFind(left,right,T->data);
    if(midnumber>left)
    {
        T->Lchild = Create2(left,midnumber-1,i);
    }
    if(midnumber<right)
    {
        T->Rchild = Create2(midnumber+1,right,i);
    }
    return T;

}
int main()
{
    memset(pre,0,MAX);
     memset(mid,0,MAX);
     gets(pre);
     gets(mid);
     int left,right,len,i=0;
     len=strlen(pre);
     left=0;
     right=len-1;

     BiTNode *T=(Bitree)malloc(sizeof(BiTNode));   //這裡可以不用配置設定空間，因為在函數裡會進行配置設定
     Create(left,right,&i,&T);

     PreTree(T);
     return 0;
}