2-8

　　給定一棵二叉樹的前序序列pre［low.1.hign1］和中序序列in［low2..hign2］，試以二叉鏈

　　#include《stdio.h》

　　#include《stdlib.h》

　　#define size 100

　　typedef struct node//定義結點

　　{

　　char data;

　　struct node *lchild，*rchild;

　　} JD，*BitTree;

　　int search（char ino［］，char pre）//在中序序列中查找先序中該元素所在位置

　　{

　　int i=0;

　　while（ino［i］！=pre&&ino［i］）

　　i++;

　　if（ino［i］==pre）

　　return i;

　　else

　　return -1;

　　}

　　void CrtBT（BitTree &T，char pre［］，char ino［］，int ps，int is，int n）/*遞歸算法構造函數，建立二叉鏈表*/

　　{

　　int k;

　　if（n==0）

　　T=NULL;

　　else

　　{

　　k=search（ino，pre［ps］）;

　　if（k==-1）

　　puts（“error！”）;

　　else

　　{

　　T=（JD*）malloc（sizeof（JD））;

　　T-》data=pre［ps］;

　　if（k==is）

　　T-》lchild=NULL;

　　else

　　CrtBT（T-》lchild，pre，ino，ps+1，is，k-is）;

　　if（k==is+n-1）

　　T-》rchild=NULL;

　　else

　　CrtBT（T-》rchild，pre，ino，ps+1+（k-is），k+1，n-（k-is）-1）;

　　}

　　}

　　}

　　//先序遍歷

　　void PreOrder（BitTree T）

　　{

　　if（T）

　　{

　　printf（“%c”，T-》data）;

　　PreOrder（T-》lchild）;

　　PreOrder（T-》rchild）;

　　}

　　}

　　//中序遍歷

　　void InOrder（BitTree T）

　　{

　　if（T）

　　{

　　InOrder（T-》lchild）;

　　printf（“%c”，T-》data）;

　　InOrder（T-》rchild）;

　　}

　　}

　　//后序遍歷（左-》右-》根），

　　int PostOrder（BitTree T）

　　{

　　if（T）

　　{

　　PostOrder（T-》lchild）;

　　PostOrder（T-》rchild）;

　　printf（“%c”，T-》data）;

　　}

　　else

　　return 1;

　　}

　　void main（）

　　{

　　char pre［size］，ino［size］;

　　puts（“輸入先序序列：”）;

　　gets（pre）;

　　puts（“輸入中序序列：”）;

　　gets（ino）;

　　BitTree T=NULL;

　　CrtBT（T，pre，ino，0，0，7）;

　　printf（“先序遍歷的二叉樹：”）;

　　PreOrder（T）;

　　printf（“\n”）;

　　printf（“中序遍歷的二叉樹：”）;

　　InOrder（T）;

　　printf（“\n”）;

　　printf（“后序遍歷的二叉樹：”）;

　　PostOrder（T）;

　　printf（“\n”）;

　　}