[数据结构与算法]B - 数据结构上机测试4.1:二叉树的遍历与应用1

Description

输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。

Input

第一行输入二叉树的先序遍历序列；
第二行输入二叉树的中序遍历序列。

Output

输出该二叉树的后序遍历序列。

Sample

Input

ABDCEF
BDAECF

Output

DBEFCA

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{
    char c;//数值域
    struct node *lt, *rt;//指针域
};

//#define N 1010
char pre[50];//前中序遍历字符串
char in[50];//中序： 已知根结点，根结点左边的值都在根结点的左子树上
//根结点右边的值都在根结点的右子树上

int len;

struct node *create(int len, char pre[], char in[]){//建树
    struct node *root;
    int i;

    if(!len){//判断树是否为空
        root = NULL;
        return root;
    }
    root = (struct node *)malloc(sizeof(struct node));
    root -> c = pre[0];//找根结点
    for(i = 0; i < len; i++){//找中序遍历中根结点所在位置
        if(pre[0] == in[i]){
            break;
        }
    }
    root -> lt = create(i, pre + 1, in);//建立左子树
    root -> rt = create(len - 1 - i, pre + 1 + i, in + 1 + i);//建立右子数
    return root;
}

void postorder(struct node *root){//后序遍历：左->右->根
    if(root){
        postorder(root -> lt);
        postorder(root -> rt);
        printf("%c", root -> c);
    }
}
int main(){
    scanf("%s", pre);
    scanf("%s", in);
    struct node *root;
    //int len;
    len = strlen(pre);
    root = create(len, pre, in);
    postorder(root);
    return 0;
}