#include <iostream>
#include <queue>
using namespace std;

//树节点类
class TNode
{
public:
    TNode *left, *right;
    char value;
    TNode()
    {
        left = right = NULL;
    }

    TNode(char v)
    {
        left = right = NULL;
        value = http://www.mamicode.com/v;>
 需求分析：

    输入一棵二叉树的先序遍历序列和中序遍历序列，输出它的先序遍历、中序遍历、后序遍历和广度优先遍历序列。 
 
 概要设计
 
 先定义树节点类，使用链表储存方式：
class TNode
{
public:
    TNode *left, *right;
    char value;
    TNode()
    {
        left = right = NULL;
    }
 
    TNode(char v)
    {
        left = right = NULL;
        value = v;
    }
 
};
 
 对于二叉树T，可以递归定义它的先序遍历、中序遍历和后序遍历如下：
 PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树)
 InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树)
 PostOrder(T)=PostOrder(T的左子树)+PostOrder(T的右子树)+T的根节点
 其中加号表示字符串连接运算。例如，对下图所示的二叉树，先序遍历为DBACEGF，中序遍历为ABCDEFG，后序遍历为ACBFGED。 
           D
           / \
          B   E
         /  \  / \
        A  C G F
      
重建二叉树:
因为已经给出二叉树的先序遍历和中序遍历，先序遍历的第一个节点是根节点，然后在中序遍历中找到根，根左边的部分为左子树，右边的部分为右子树 ，然后按照这个过程递归建立左右子树即可。
 
广度优先遍历二叉树：
用队列保存当前访问节点，先把根节点入队，当队列非空时，访问队头节点并把该节点的左右孩子入队后弹出队头元素，直到队列为空


程序输入:
第一行为一个整数t（0<t<10），表示测试用例个数。 以下t行，每行输入一个测试用例，包含两个字符序列s1和s2，其中s1为一棵二叉树的先序遍历序列，s2为中序遍历序列。s1和s2之间用一个空格分隔。序列只包含大写字母，并且每个字母最多只会出现一次，程序输出它的先序遍历、中序遍历、后序遍历和广度优先遍历序列。 
 
Sample Input
2 DBACEGF ABCDEFG BCAD CBAD 
Sample Output
PreOrder: DBACEGF
InOrder: ABCDEFG
PostOrder: ACBFGED
BFS: DBEACGF
 
PreOrder: BCAD
InOrder: CBAD
PostOrder: CDAB
BFS: BCAD

测试结果



附录




二叉树重建及二叉树广度优先遍历