资 源 简 介
2-8
给定一棵二叉树的前序序列pre［low.1.hign1］和中序序列in［low2..hign2］，试以二叉链
#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（“
”）;
printf（“中序遍历的二叉树：”）;
InOrder（T）;
printf（“
”）;
printf（“后序遍历的二叉树：”）;
PostOrder（T）;
printf（“
”）;
}
