数据结构实验之求二叉树后序遍历和层次遍历
Time Limit: 1000 ms Memory Limit: 65536 KiB
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; }
