根据前序和中序排列求后序的递归算法
#include<stdio.h>#include <stdlib.h>
typedef struct BitNode
{
char data;
struct BitNode* lchild;
struct BitNode* rchild;
}BitNode,*Bintree;
Bintree creatbitree(char *a,char *b,int m); //创建二叉树
void preordertraverse(BitNode* t); //前序遍历二叉树
void inorder(BitNode *t);
void postorder(BitNode *t);
int flag=0;
int main()
{
BitNode *bt=NULL;
char a[10]="abdgcefh", b[10]="dgbaechf";
bt=creatbitree(a,b,8);
printf("前序遍历结果:");
preordertraverse(bt);
printf("\n中序遍历结果:");
inorder(bt);
printf("\n后序遍历结果:");
postorder(bt);
}
BitNode * creatbitree(char *a,char *b,int m)
{
int i;
BitNode *s;
if(m==0)return NULL;
s=(BitNode *)malloc(sizeof(BitNode));
s->data=*a;
for(i=0;i<m;i++)
{
if(*a==b[i])break;
}
s->lchild=creatbitree(a+1,b,i);
s->rchild=creatbitree(a+i+1,b+i+1,m-i-1);
// printf("%c",s->data);
return s;
}
void preordertraverse(Bintree bt)
{
if(bt!=NULL)
{
printf("%c",bt->data);
preordertraverse(bt->lchild);
preordertraverse(bt->rchild);
}
}
void inorder(BitNode *bt)
{
if(bt!=NULL)
{
inorder(bt->lchild);
printf("%c",bt->data);
inorder(bt->rchild);
}
}
void postorder(BitNode *bt)
{
if(bt!=NULL)
{
postorder(bt->lchild);
postorder(bt->rchild);
printf("%c",bt->data);
}
}