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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

Input

 输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。

Output

每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列。

Sample Input

2abdegcfdbgeafcxnliulnixu

Sample Output

dgebfcaabcdefglinuxxnuli 提示：本题用到了还原二叉树的知识点，即通过前序+中序来还原二叉树，从而输出它的后序遍历和层序遍历。 代码实现如下（g++）：

#include 
      
       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!='\0'; p++)    {        if(*p==a[0])//一步步找b数组中a[0]的位置，找到位置记下来            break;    }    int t=p-b;//左子树长度为p-b    root->left=create(t,a+1,b);//三个变量分别为左子树长度，指向a的下一位，指向b    root->right=create(n-t-1,a+t+1,p+1);//三个变量分别为右子树长度，指向a+左子树长度+根节点长度，指向p的下一位    return root;}void housort(node *root)//后序遍历{    if(root)    {    housort(root->left);//遍历左儿子    housort(root->right);//遍历右儿子    cout<
       
        data;//遍历根节点，输出根节点    }}void cengci(node *root)//层序遍历，需要用到队列{    queue
        
         t;    t.push(root);    while(!t.empty())    {        root=t.front();        t.pop();        if(root)        {            cout<
         
          data;            t.push(root->left);            t.push(root->right);//将左右节点依次进队，先进先出，很好理解        }    }}int main(){    char a[55],b[55];    int n;    while(~scanf("%d",&n))    {        node *root;        scanf("%s",a);        scanf("%s",b);        n=strlen(a);        root=create(n,a,b);        housort(root);        printf("\n");        cengci(root);        printf("\n");    }    return 0;}/***************************************************Result: AcceptedTake time: 0msTake Memory: 200KB****************************************************/