求二叉树的层次遍历

分手后的思念是犯贱 2022-07-12 07:15 70阅读 0赞

求二叉树的层次遍历  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

已知一颗二叉树的前序遍历和中序遍历，求二叉树的层次遍历。  
Input

输入数据有多组，输入T，代表有T组测试数据。每组数据有两个长度小于50的字符串，第一个字符串为前序遍历，第二个为中序遍历。  
Output

每组输出这颗二叉树的层次遍历。  
Example Input

2  
abc  
bac  
abdec  
dbeac  
Example Output

abc  
abcde  
Hint

Author

fmh

**这个题是根据前序和中序重建二叉树，然后在求层序遍历。**

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    char a[55];
    char b[55];
    struct node
    {
        int data;
        struct node *l, *r;
    };
    struct node *creat(int n, char *a, char *b)//重建二叉树
    {
        int i;
        struct node *root;
        if(n == 0) return NULL;
        root = (struct node *) malloc(sizeof(struct node));
        root -> data = a[0];
        for(i = 0; i < n; i++)
        {
            if(b[i] == a[0])
                break;
        }
        root -> l = creat(i, a+1, b);
        root -> r = creat(n-1-i, a+i+1, b+i+1);
        return root;//重建完成
    };
    void cengxu(struct node *root)//求层序遍历
    {
        int in = 0, out = 0;
        struct node *p[100];//用于储存每一层的数据
        p[in++] = root;
        while(in > out)
        {
            if(p[out])
            {
                printf("%c", p[out] -> data);
                p[in++] = p[out] -> l;
                p[in++] = p[out] -> r;
            }
            out++;
        }
    }
    int main()
    {
        int t, n;
        scanf("%d", &t);
        while(t--)
        {
            scanf("%s%s",a , b);
            n = strlen(a);
            struct node *root;
            root = creat(n, a, b);
            cengxu(root);
            printf("\n");
        }
        return 0;
    }