題目

已知二叉樹前序為 ABDFGCEH 后序序列為 BFDGACEH ，要求輸出后序遍歷為 FGDBHECA

大體思路

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

代碼

#include

#include

#include

#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

{

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

{

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

{

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;

}

責任編輯：haq