先序中序建立二叉树

来源：百度知道 编辑：UC知道 时间：2024/05/29 04:17:01
1二叉树中存储的数据范围仅限于26个英文字母
2程序要提示用户从键盘分别输入二叉树的先序和中序序列，接受输入后，调用相应的函数完成二叉树的创建
3成功创建二叉树后，程序自动输出该二叉树的后序遍历次序

#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);
}
}
}
//先序遍历
v