数据结构（树的遍历）

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

分析：无论是给定中序遍历、后序遍历，还是中序遍历、前序遍历，都要首先确定根结点，而确定一定不是通过中序遍历，因为它是左根右，无法直接确定哪一个是所有树的根结点。然后递归调用即可。

#include <iostream> #include <queue> #include <cstdlib> using namespace std; typedef struct Node{ int data; struct Node *left,*right; }Node,*Tree; Tree create(int n,int *aft,int *mid){ if(n==0) return NULL; Tree tree = (Node *)malloc(sizeof(Node)); tree->data = aft[n-1]; tree->left = tree->right = NULL; int i; for(i = 0;i<n;i++){ if(mid[i]==aft[n-1]) break; } tree->left = create(i,aft,mid);//左子树 tree->right = create(n-1-i,aft+i,mid+i+1);//右子树  return tree; } void order(int n,Tree tree){ if(!tree) return; queue<Tree> qe; qe.push(tree); int len = 0; while(!qe.empty()){ Tree t = qe.front(); len++; if(len<n) cout << t->data << " "; else cout << t->data; if(t->left) qe.push(t->left); if(t->right) qe.push(t->right); qe.pop(); } } int main(){ ios::sync_with_stdio(false); int n; cin >> n; int aft[n],mid[n]; int num; for(int i = 0;i<n;i++){ cin >> aft[i]; } for(int i = 0;i<n;i++){ cin >> mid[i]; } Tree tree = create(n,aft,mid); order(n,tree); return 0; } 

本文地址：https://blog.csdn.net/weixin_45845039/article/details/107763284