C++中序遍历和后序遍历推出层序遍历

一、题目要求

1、编程实现

给定一个二叉树的中序遍历和后序遍历顺序，求出二叉树对应的层序遍历顺序。

注：二叉树的节点个数小于等于50

2、输入输出

输入描述：第一行输入节点个数n（1<=n<=50）

第二行输入n个节点的中序遍历

第三行输入n个节点的后序遍历

输出描述：只有一行，层序遍历的节点顺序

输入样例：

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

输出样例：

4 2 3 1 5 6 7

二、算法分析

1. 从给定题目的初步分析可以看出，这是一道二叉树相关题目
2. 题目是给定中序遍历顺序和后序遍历顺序，要求层序遍历顺序
3. 所以可以首先通过中序遍历和后序遍历构建出这棵二叉树
4. 先定义一个二叉树的节点的结构体，每个节点包括值和左右子树
5. 关键在于如何构建这棵二叉树，可以从后序遍历入手，后序遍历是左子树→右子树→根；而中序遍历是左子树→根→右子树
6. 所以可以根据后序遍历数组的最后一个元素（即根节点）创建一个新节点，并在中序遍历数组中找到对应的根节点位置。然后计算左子树节点个数，接着就可以根据中序遍历数组的范围和后序遍历数组的范围递归构建左右子树，最后得到这棵二叉树
7. 有了二叉树之后就可以通过使用广度优先搜索（BFS）的方式实现层序遍历，实现方式可以结合使用队列（queue）的形式进行，先输出根节点，然后是左子树，最后是右子树；得到整个层序遍历的节点顺序

三、程序编写

//根据中序遍历和后序遍历得出层序遍历
#include<bits/stdc++.h>
using namespace std;
const int N = 50;
int n,in[N],post[N];
struct node{
  int data;
  node* lchild;
  node* rchild;
};
//根据中序遍历和后序遍历创建二叉树
node* createT(int,int,int,int);
void Bfs(node*);


int main()
{
  cin >> n;
  for(int i=0;i<n;i++) cin >> in[i];
  for(int i=0;i<n;i++) cin >> post[i];
  node* root = createT(0,n-1,0,n-1);
  Bfs(root);
  return 0;
}


node* createT(int inl,int inr,int postl,int postr)
{
  if(postl > postr) return NULL;
  node* root = new node;
  root->data = post[postr];
  int i;
  for(i=inl;i<=inr;i++)
    if(in[i] == post[postr])
      break;
  int nums = i - inl;  //左节点个数
  root->lchild = createT(inl,i-1,postl,postl+nums-1);
  root->rchild = createT(i+1,inr,postl+nums,postr-1);
  return root;
}


void Bfs(node* root)
{
  queue<node*> q;
  q.push(root);
  while(!q.empty())
  {
    node* temp = q.front();
    q.pop();
    cout << temp->data << " ";
    if(temp->lchild) q.push(temp->lchild);
    if(temp->rchild) q.push(temp->rchild);
  }
}

四、运行结果

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

五、考点分析

难度级别：中等，这题相对而言难在构建二叉树并进行层序搜索，具体主要考查如下：

1. 分析题目，找到解题思路
2. 充分掌握变量和数组的定义和使用
3. 掌握结构体的定义和使用
4. 了解指针的原理以及指针的使用方法
5. 了解二叉树相关知识，中序遍历和后序遍历过程
6. 学会如何使用中序遍历和后序遍历构建整个二叉树
7. 学会使用队列的方式实现广度优先搜索算法
8. 学会输入流对象cin的使用，从键盘读入相应的数据
9. 学会for循环的使用，在确定循环次数的时候推荐使用学会
10. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
11. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
12. 充分掌握数组、结构体定义和使用、分支语句、循环语句和广度优先搜索算法的应用