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

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

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

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

输入

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

输出

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

示例输入

2 abdegcf dbgeafc xnliu lnixu

示例输出

dgebfca abcdefg linux xnuli

前序遍历的第一个就是二叉树的根，从中序遍历中找到它，左边的就属于它的左子树，右边的就属于它的右子树。再分别从它的左右子树为继续这样分解，同时建立二叉树，直到最后。然后在层次遍历。

#include <iostream>

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <queue> using namespace std; typedef struct TNode {     char data;     TNode *Lchild;     TNode *Rchild; } TNode; TNode* restore(char* pre,char* in,  int length) {     if(length == 0)     {         return NULL ;     }     TNode* node=new TNode;     node->data=*pre;     int r=0;     for(  ; r< length; r++)     {         if(in[r] == *pre)             break;     }

    node->Lchild = restore(pre+1,in,r); //参数 in和pre+1是确定起点，r确定字符串的大小。

    node->Rchild= restore(pre+r+1,in+r+1,length-(r+1));//     cout<<node->data;     return node; } void Cengci (TNode *&T) {     TNode* temp;     queue<TNode*>q;     if(T) q.push(T);     while(!q.empty()){         temp=q.front();         q.pop();         if(temp)         {             cout<<temp->data;         }         if(temp->Lchild) q.push(temp->Lchild);          if(temp->Rchild) q.push(temp->Rchild);         } } int main() {     int t, l ;     char i[52],p[52];     cin>>t;     while(t--)     {         cin>>p;         cin>>i;         l=strlen(i);         TNode *Ti;         Ti=restore(p,i,l);         cout<<endl;         Cengci(Ti);         cout<<endl;     } }