数据结构上机测试4.1:二叉树的遍历与应用1

r囧r小猫 2022-08-18 02:23 55阅读 0赞

## 数据结构上机测试4.1:二叉树的遍历与应用1 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

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

## 输入 ##

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

## 输出 ##

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

## 示例输入 ##

ABDCEF
    BDAECF

## 示例输出 ##

DBEFCA

#include<stdio.h>  
    #include<stdlib.h>  
    #include<string.h>  
    struct node  
    {  
    int data;  
    struct node *lchild,*rchild;  
    };  
    struct node *creat(int n,char *a,char *b)  
    {  
    struct node *root;  
    char *p;  
    if(n==0)  
    return NULL;  
    root=(struct node *)malloc(sizeof(struct node));  
    root->data=a[0];  
    for(p=b;p!='\0';p++)  
    if(*p==a[0])  
    break;  
    int t;  
    t=p-b;  
    root->lchild=creat(t,a+1,b);  
    root->rchild=creat(n-t-1,a+t+1,p+1);  
    return root;  
    }  
    void houxu(struct node *root)  
    {  
    if(root)  
    {  
    houxu(root->lchild);  
    houxu(root->rchild);  
    printf("%c",root->data);  
    }  
    }  
    int main()  
    {  
    int i,j,n,m,k,t;  
    struct node *root;  
    root=(struct node *)malloc(sizeof(struct node));  
    char a[100],b[100];  
    scanf("%s %s",a,b);  
    m=strlen(a);  
    root=creat(m,a,b);  
    houxu(root);  
    printf("\n");  
    }