先序中序建立二叉树

答案:1 悬赏:20 手机版

解决时间 2021-03-28 02:41

提问者网友：且恨且铭记
2021-03-27 12:06

先序中序建立二叉树

最佳答案

五星知识达人网友：患得患失的劫
2021-03-27 12:47

#include
#include
#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");
}

调试过的
有问题留言

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！