根据前序和中序排列求后序的递归算法 - ehszt的博客

作者在 2018-06-10 21:14:55 发布以下内容

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