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

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

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

提示：本题用到了还原二叉树的知识点，即通过前序+中序来还原二叉树，从而输出它的后序遍历和层序遍历。

代码实现如下（g++）：

#include <bits/stdc++.h>

using namespace std;

typedef struct node
{
    char data;
    struct node *left;
    struct node *right;
} node;//typedef定义struct node结构体

node *create(int n,char *a,char *b)
{
    node *root;
    char *p;//定义一个指针，用来查找b数组
    if(n==0)
        return NULL;//如果n==0，即长度为空，不存在
    root=(node *)malloc(sizeof(node));//申请空间
    root->data=a[0];//注意a数组是前序遍历，所以它的第一个元素必定是该树的根节点
    for(p=b; p!='