首页 > 代码库 > 数据结构之 二叉树---求二叉树后序遍历和层次遍历（先建树，再遍历）
数据结构之 二叉树---求二叉树后序遍历和层次遍历（先建树，再遍历）
数据结构实验之求二叉树后序遍历和层次遍历
Time Limit: 1000MS Memory limit: 65536K
题目描述
已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历。
输入
输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。
输出
每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列
示例输入
2abdegcfdbgeafcxnliulnixu
示例输出
dgebfcaabcdefglinuxxnuli
第一种方法：根据字符串的递推， 由先序、中序直接计算后序串！ 在建树，进行层次遍历！
代码：
#include <iostream>#include <iomanip>#include <string>#include <string.h>#include <stdio.h>#include <algorithm>#include <queue>#include <vector>using namespace std;typedef struct node{ char a; struct node *ll; struct node *rr;}Binode, *tree;void build(int len, char *s1, char *s2, char *s) //先序中序 推 后序{ if(len<=0) return; int pos; //位置 int i; for(i=0; i<len; i++) { if(s2[i]==s1[0]) { pos=i; break; } } build(pos, s1+1, s2, s ); build(len-pos-1, s1+pos+1, s2+pos+1, s+pos ); s[len-1]=s1[0];} //根据先序中序建树struct node*creat(struct node *root, char *s, char *s1, int n){ if(n<=0) return NULL; root=new node; root->a=s[0]; int p=strchr(s1, s[0] )-s1; root->ll=creat( root->ll, s+1, s1, p ); root->rr=creat( root->rr, s+p+1, s1+p+1, n-p-1 ); return root;}//层次遍历 二叉树void Level_Order(tree root){ queue<tree>q; tree qq; if(root==NULL) return ; Binode *p=root; cout<<(p->a); if(p->ll) q.push( p->ll ); if(p->rr) q.push( p->rr ); while(!q.empty()) { qq=q.front(); q.pop(); cout<<qq->a; if(qq->ll) q.push(qq->ll); if(qq->rr) q.push(qq->rr); } return;}int main()
{ int t; cin>>t; char s1[100], s2[100]; char s3[100]; while(t--) { memset(s3, ‘\0‘, sizeof(s3)); scanf("%s", s1); //中序 scanf("%s", s2); //后序 int len=strlen(s1); build(len, s1, s2, s3); printf("%s\n", s3); //输出后序遍历 //计算层次遍历 tree root, tt; root=creat(tt, s1, s2, len); Level_Order( root); cout<<endl; } return 0;}
第二种方法：先根据先序、中序建树，在进行后序遍历和层次遍历
代码：#include <iostream>#include <iomanip>#include <string>#include <string.h>#include <stdio.h>#include <algorithm>#include <queue>#include <vector>using namespace std;typedef struct node{ char a; struct node *ll; struct node *rr;}Binode, *tree;//根据先序中序建树struct node*creat(struct node *root, char *s, char *s1, int n){ if(n<=0) return NULL; root=new node; root->a=s[0]; int p=strchr(s1, s[0] )-s1; root->ll=creat( root->ll, s+1, s1, p ); root->rr=creat( root->rr, s+p+1, s1+p+1, n-p-1 ); return root;}void postorder(tree p){ if(p) { postorder(p->ll); postorder(p->rr); printf("%c", p->a ); }}//层次遍历 二叉树void Level_Order(tree root){ queue<tree>q; tree qq; if(root==NULL) return ; Binode *p=root; cout<<(p->a); if(p->ll) q.push( p->ll ); if(p->rr) q.push( p->rr ); while(!q.empty()) { qq=q.front(); q.pop(); cout<<qq->a; if(qq->ll) q.push(qq->ll); if(qq->rr) q.push(qq->rr); } return;}int main(){ int t; cin>>t; char s1[100], s2[100]; char s3[100]; while(t--) { memset(s3, ‘\0‘, sizeof(s3)); scanf("%s", s1); //中序 scanf("%s", s2); //后序 int len=strlen(s1); //计算层次遍历 tree root, tt; root=creat(tt, s1, s2, len); postorder(root); cout<<endl; Level_Order( root); cout<<endl; } return 0;}
数据结构之 二叉树---求二叉树后序遍历和层次遍历（先建树，再遍历）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。