求二叉树的层次遍历
Time Limit: 1000 ms Memory Limit: 65536 KiB
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; }
