已知中序序列和后序序列，写一个建立该二叉树的算法
#include <stdio.h> #include <stdlib.h> #define maxsize 20 #define OK 1 #define ERROR 0 typedef int Status; typedef struct Node { char data; struct Node *lchild,*rchild; }Node,*BiTree; typedef struct { BiTree H[maxsize]; int len; }Arr; int CreateBiTree(BiTree *T); Status Visit(BiTree T,Arr *H); Status PreOrderTraverse(BiTree T,Arr *H); Status MidOrderTraverse(BiTree T,Arr *H); Status BacOrderTraverse(BiTree T,Arr *H); void CreateBiTreefromarray(BiTree *T,Arr Mid,int Mfirst,int Mlast,Arr Bac,int Bfirst,int Blast); int main() { Arr Pre,Mid,Bac,Pre2,Mid2,Bac2; Pre.len=Mid.len=Bac.len=Pre2.len=Mid2.len=Bac2.len=0; BiTree T,T2; T=(BiTree)malloc(sizeof(Node)); T2=(BiTree)malloc(sizeof(Node)); CreateBiTree(&T); PreOrderTraverse(T,&Pre); MidOrderTraverse(T,&Mid); BacOrderTraverse(T,&Bac); int i; printf("\n前序序列："); for(i=0;i<Pre.len;i++) printf("%c ",Pre.H[i]->data); printf("\n"); printf("中序序列："); for(i=0;i<Mid.len;i++) printf("%c ",Mid.H[i]->data); printf("\n"); printf("后序序列："); for(i=0;i<Bac.len;i++) printf("%c ",Bac.H[i]->data); printf("\n"); CreateBiTreefromarray(&T2,Mid,0,Mid.len-1,Bac,0,Bac.len-1); PreOrderTraverse(T2,&Pre2); MidOrderTraverse(T2,&Mid2); BacOrderTraverse(T2,&Bac2); printf("\n前序序列："); for(i=0;i<Pre2.len;i++) printf("%c ",Pre2.H[i]->data); printf("\n"); printf("中序序列："); for(i=0;i<Mid2.len;i++) printf("%c ",Mid2.H[i]->data); printf("\n"); printf("后序序列："); for(i=0;i<Bac2.len;i++) printf("%c ",Bac2.H[i]->data); printf("\n"); return 0; } int CreateBiTree(BiTree *T) { fflush(stdin); printf("please input the node data:"); char ch; scanf("%c",&ch); *T=(BiTree)malloc(sizeof(Node)); (*T)->data=ch; char c; fflush(stdin); printf("Dose %c has leftchild(y--yes,n--no):",ch); scanf("%c",&c); if(c=='y') CreateBiTree(&(*T)->lchild); else (*T)->lchild=NULL; fflush(stdin); printf("Dose %c has rightchild(y--yes,n--no):",ch); scanf("%c",&c); if(c=='y') CreateBiTree(&(*T)->rchild); else (*T)->rchild=NULL; return 0; } Status Visit(BiTree T,Arr *H) { H->H[H->len]=T; H->len++; return OK; } //前序遍历并将遍历结果存于数组中 Status PreOrderTraverse(BiTree T,Arr *H) { if(T) { if(Visit(T,H)) if(PreOrderTraverse(T->lchild,H)) if(PreOrderTraverse(T->rchild,H)) return OK; return ERROR; } else return OK; } //中序遍历并将遍历结果存于数组中 Status MidOrderTraverse(BiTree T,Arr *H) { if(T) { if(MidOrderTraverse(T->lchild,H)) if(Visit(T,H)) if(MidOrderTraverse(T->rchild,H)) return OK; return ERROR; } else return OK; } //后序遍历并将遍历结果存于数组中 Status BacOrderTraverse(BiTree T,Arr *H) { if(T) { if(BacOrderTraverse(T->lchild,H)) if(BacOrderTraverse(T->rchild,H)) if(Visit(T,H)) return OK; return ERROR; } else return OK; } //从中序序列和后序序列数组中创建二叉树 void CreateBiTreefromarray(BiTree *T,Arr Mid,int Mfirst,int Mlast,Arr Bac,int Bfirst,int Blast) { *T=(BiTree)malloc(sizeof(Node)); (*T)->data=Bac.H[Blast]->data; int i,j; for(i=Mfirst;i<=Mlast;i++) if(Bac.H[Blast]->data==Mid.H[i]->data) j=i; if(j>Mfirst) CreateBiTreefromarray(&(*T)->lchild,Mid,Mfirst,j-1,Bac,Bfirst,Bfirst+j-Mfirst-1); else (*T)->lchild=NULL; if(j<Mlast) CreateBiTreefromarray(&(*T)->rchild,Mid,j+1,Mlast,Bac,Bfirst+j-Mfirst,Blast-1); else (*T)->rchild=NULL; }