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

Question

1二叉树中存储的数据范围仅限于26个英文字母2程序要提示用户从键盘分别输入二叉树的先序和中序序列，接受输入后，调用相应的函数完成二叉树的创建3成功创建二叉树后，程序自动输出该二叉树的后序遍历次序#include<stdio.h>#include<stdlib.h>#include<string.h>#define size 100typedef 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;elsereturn -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;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 );}}} /* 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 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");
}

调试过的

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) {
//构造二叉链表表示的二叉树T
char 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) {
// 先序遍历二叉树T
if (T) {
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiT *T) {
// 中序遍历二叉树T
if (T) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiT *T) {
// 后序遍历二叉树T
if (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);
}