请问在先序中序建立二叉树，该怎么实现？

Question

1二叉树中存储的数据范围仅限于26个英文字母
2程序要提示用户从键盘分别输入二叉树的先序和中序序列，接受输入后，调用相应的函数完成二叉树的创建
3成功创建二叉树后，程序自动输出该二叉树的后序遍历次序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define size 100
typedef struct JD
{
char data;
struct JD *lchild,*rchild;
}BiTree;
int Search(char ino[],char ch)
{
int i=0;
//puts(ino)
while(ino[i]!=ch&&ino[i])
i++;
if(ino[i]==ch)
return i;
else
return -1;
}
void CrtBT(BiTree *T, char pre[], char ino[], int ps, int is, int n ) /*已知pre[ps..ps+n-1]为二叉树的先序序列,ino[is..is+n-1]为二叉树的中序序列,本算法由此两个序列构造二叉链表*/
{
int k;
if (n==0) T=NULL;
else
{
k=Search(ino, pre[ps]);/*在中序序列中查询*/
if (k== -1) {T=NULL;puts("错误！！！\n");}
else
{
T= (BiTree*)malloc(sizeof(BiTree));
if (T==NULL) exit(1);
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 );
}
}
} /* end CrtBT */
void postorder(BiTree *t)//递归先序遍历
{
if(t!=NULL)
{ printf("%c\t",t->data);
postorder(t->lchild);
postorder(t->rchild);

}
}
void main()
{
char pre[size],ino[size];
int ps,is,n;
BiTree *T=NULL;
puts("enter:");
scanf("%s",pre);
scanf("%s",ino);
CrtBT(T,pre,ino,0,0,strlen(pre));
postorder(T);
getchar();
}

修改
或者新程序都可以

Answer 1

#include<stdio.h>#include<stdlib.h>#define size 100typedef 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;elsereturn -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;elseCrtBT(T->lchild,pre,ino,ps+1,is,k-is);if(k==is+n-1)T->rchild=NULL;elseCrtBT(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);}elsereturn 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");}调试过的

Answer 2

参考一下吧！程序1#include<stdio.h>#include<stdlib.h>typedef struct BiT{char data;struct BiT *lchild;struct BiT *rchild;}BiT;BiT* CreateBiTree(BiT *T) {//构造二叉链表表示的二叉树Tchar ch;scanf("%c",&ch);if (ch=='#') T = NULL;else {T = (BiT *)malloc(sizeof(BiT));T->data = ch;T->lchild=CreateBiTree(T->lchild);T->rchild=CreateBiTree(T->rchild);}return T;}void PreOrderTraverse(BiT *T) {// 先序遍历二叉树Tif (T) {printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}void InOrderTraverse(BiT *T) {// 中序遍历二叉树Tif (T) {InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}}void PostOrderTraverse(BiT *T) {// 后序遍历二叉树Tif (T) {PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}}void main() {printf("先序建树:");BiT *T=CreateBiTree(T);printf("\n先序遍历:");PreOrderTraverse(T);printf("\n中序遍历:");InOrderTraverse(T);printf("\n后序遍历:");PostOrderTraverse(T);getchar();getchar();}来源http://zhidao.baidu.com/question/29259767.html?si=9程序2#define EL 10#define TEL 2*EL+1#define LEN sizeof(struct node)#include "stdio.h"#include "stdlib.h"char pre[TEL]="ABCDEFGHIJ";char pin[TEL]="CBEDAGHFJI";typedef struct node{ char data;struct node * lch,*rch;}BTNode,*BTree;BTNode root;BTree rt=&root;int pos(char c,char s[],int st){char *p;p=s+st;while(*p!=c && *p!='\0') p++;return p-s;}void create(BTree *t,int i1,int i2,int len){int r,llen,rlen;if(len<=0) *t=NULL;else{*t=(BTree)malloc(LEN);(*t)->data=pre[i1];r=pos(pre[i1],pin,i2);llen=r-i2;rlen=len-(llen+1);create(&(*t)->lch,i1+1,i2,llen);create(&(*t)->rch,i1+llen+1,r+1,rlen);}}void travel(BTree t){if(t){travel(t->lch);travel(t->rch);putchar(t->data);}}int main(){create(&rt,0,0,EL);if(rt) travel(rt);}