1.首先建立一棵二叉树
这里根据二叉树的先序和中序的序列建立一颗树
{
int k;
if (n==0)
T=NULL;
else
{
k=search(ino,pre[ps]);
if (k==-1)
printf("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);
}
}
}
2.用先序,中序,后序遍历树
源代码如下:
#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)
printf("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!=NULL)
{
printf("%c",t->data);
preOrder(t->lchild);
preOrder(t->rchild);
}
}
//中序递归遍历
void inOrder(BitTree t)
{
if (t!=NULL)
{
inOrder(t->lchild);
printf("%c",t->data);
inOrder(t->rchild);
}
}
//后序递归遍历
void postOrder(BitTree t)
{
if (t!=NULL)
{
postOrder(t->lchild);
postOrder(t->rchild);
printf("%c",t->data);
}
}
int main()
{
//1.建立二叉树
char pre[size],ino[size];
puts("输入先序序列：");
gets(pre);
puts("输入中序序列：");
gets(ino);
BitTree T=NULL;
CrtBT(T,pre,ino,0,0,7);
printf("完成二叉树\n");
printf("\n");
//2.先序递归遍历
printf("先序递归遍历为\n");
preOrder(T);
printf("\n");
//3.中序递归遍历
printf("中序递归遍历为\n");
inOrder(T);
printf("\n");
//4.后序递归遍历
printf("后序递归遍历为\n");
postOrder(T);
system("pause");
}
