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

爱被打了一巴掌 2022-06-01 14:29 60阅读 0赞

数据结构上机测试4.1:二叉树的遍历与应用1  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

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

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

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

ABDCEF  
BDAECF  
Example Output

DBEFCA

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        char data;
        struct node *l, *r;
    };
    char s1[2000], s2[2000];
    struct node *creat(int n, char *s1, char *s2)
    {
        int i;
        if(n == 0)
            return NULL;
        struct node *root;
        root = (struct node*) malloc (sizeof(struct node));
        root -> data = s1[0];
        for(i = 0; i < n; i++)
        {
            if(s2[i] == s1[0])
                break;
        }
        root -> l = creat(i, s1 + 1, s2);
        root -> r = creat(n - 1 - i, s1 + i + 1, s2 + i + 1);
        return root;
    }
    void houxv(struct node *root)
    {
        if(root)
        {
            houxv(root -> l);
            houxv(root -> r);
            printf("%c", root -> data);
        }
    }
    
    int main()
    {
        scanf("%s", s1);
        scanf("%s", s2);
        int n = strlen(s1);
        struct node *root;
        root = creat(n, s1, s2);
        houxv(root);
        return 0;
    }