数据结构实验之求二叉树后序遍历和层次遍历

秒速五厘米 2024-02-18 22:31 49阅读 0赞

#### 数据结构实验之求二叉树后序遍历和层次遍历 ####

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历和层序遍历。

Input

输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。

Output

每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列。

Sample Input

2
    abdegcf
    dbgeafc
    xnliu
    lnixu

Sample Output

dgebfca
    abcdefg
    linux
    xnuli

Hint

Source

ma6174

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        char data;
        struct node *lc, *rc;
    };
    struct node *creat(char a[], char b[], int n)
    {
        int i;
        if(n == 0)
        {
            return NULL;
        }
        struct node *root;
        root = (struct node *)malloc(sizeof(struct node));
        root->data = a[0];
        for(i = 0; i < n; i++)
        {
            if(b[i] == a[0])
            {
                break;
            }
        }
        root->lc = creat(a+1,b,i);
        root->rc = creat(a+i+1,b+1+i,n-1-i);
        printf("%c", root->data);
        return root;
    };
    void cengci(struct node *root)
    {
        int out = 0, in = 0;
        struct node *q[100];
        q[in++] = root;
        while(in > out)
        {
            if(q[out] != 0)
            {
                printf("%c", q[out]->data);
                q[in++] = q[out]->lc;
                q[in++] = q[out]->rc;
            }
            out++;
        }
    }
    int main()
    {
        int t, n;
        struct node *root;
        char a[1001], b[1001];
        scanf("%d", &t);
        while(t--)
        {
            scanf("%s %s", a, b);
            n = strlen(a);
            root = creat(a,b,n);
            printf("\n");
            cengci(root);
            printf("\n");
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2562/pid/2137.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2562/pid/2137.html