7-2 根据后序和中序遍历输出先序遍历

分数 25

全屏浏览题目

切换布局

作者 DS课程组

单位 浙江大学

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

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

输出样例:

Preorder: 4 1 3 2 6 5 7

代码：

#include <iostream>
using namespace std;
int n =0;
int hou[30];
int zhong[30];
void out_qian(int n,int *hou,int *zhong)
{
    if(n<=0)
        return;
    cout<<" "<<hou[n-1];
    int i;
    for(i=0;i<n;i++)
    {
        if(hou[n-1]==zhong[i])
            break;
    }
    out_qian(i,hou,zhong);//递归左子树
    out_qian(n-1-i,hou+i,zhong+i+1);//递归右子树
    return;
}
int main()
{

    cin>>n;
    for(int i = 0;i < n;i++)
        cin>>hou[i];
    for(int i = 0;i < n;i++)
        cin>>zhong[i];
    cout << "Preorder:";
    out_qian(n,hou,zhong);
    return 0;
}