求二叉树的层次遍历

左手的ㄟ右手 2024-02-18 22:31 25阅读 0赞

#### 求二叉树的层次遍历 ####

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

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

Input

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

Output

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

Sample Input

2
    abc
    bac
    abdec
    dbeac

Sample Output

abc
    abcde

Hint

Source

fmh

#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);
        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);
            cengci(root);
            printf("\n");
        }
        return 0;
    }

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