我就直接举例子了:
像这样先序为:abcde
中序为:dbcae
这样的是无法求出二叉树的后序的
我发现程序是卡在了递归的死循环当中,上程序:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OVERFLOW 0
typedef struct Node
{
char data;
struct Node *lchild,*rchild;
//Node(){data = 0;lchild = rchild = NULL;}
}Node,*BiTree;
char PreString[30],InString[30];//先序和中序遍历字符串
BiTree Build(char *PreString,char *InString,int s1,int e1,int s2,int e2)
{
BiTree T = new Node();
T -> data = PreString[s1];
int rootIdx;//根结点所在序号
for(int i = s2;i <= e2;i++)
{
if(PreString[s1] == InString[i])
{
rootIdx = i;
break;
}
}
int llen = rootIdx - s2;
int rlen = e2 - rootIdx;
if(llen != 0)
{
T -> lchild = new Node();
T -> lchild = Build(PreString,InString,s1 + 1,s1 + llen,s2,s2 + llen - 1);
}
else
T -> lchild = NULL;
if(rlen != 0)
{
T -> rchild = new Node();
T -> rchild = Build(PreString,InString,e1 - rlen + 1,e1,e2 - rlen + 1,e2);
}
else
{
T -> rchild = NULL;
}
return T;
}
void PostOrder(BiTree T)//后序遍历
{
if(T != NULL)
{
PostOrder(T -> lchild);
PostOrder(T -> rchild);
printf("%c",T -> data);
}
}
int main()
{
printf("请输入先序遍历字符串:");
scanf("%s",PreString);
printf("请输入中序遍历字符串:");
scanf("%s",InString);
BiTree T = NULL;
T = Build(PreString,InString,0,strlen(PreString)-1,0,strlen(InString)-1);
printf("此二叉树的后序遍历为:");
PostOrder(T);
printf("\n");
return 0;
}
就是在BiTree Build当中跳不出去,求助各位大佬指点一下思路。。。