数据结构/PTA-据后序和中序遍历输出先序遍历/树

标签:scan   amp   lse   color   col   cout   its   using   bre   

据后序和中序遍历输出先序遍历

-1 根据后序和中序遍历输出先序遍历 (25分)

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

输入格式:

第一行给出正整数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<bits/stdc++.h>
using namespace std;
typedef struct BiTNode
{
    struct BiTNode *lchild;
    struct BiTNode *rchild;
    int data;
} BiTNode, *BiTree;
BiTree Plustree(int *in,int *post,int n)
{
    if(n<=0)
        return NULL;
    else
    {
        BiTree T=new BiTNode;
        T->data=post[n-1];
        int i=0;
        for(i=0; i<n; i++)
        {
            if(post[n-1]==in[i])
                break;
        }
        T->lchild = Plustree(in, post, i);
        T->rchild = Plustree(in+i+1,post+i,n-i-1);
        return T;
    }
}
void preorderTraversal( BiTree BT )//前序遍历
{
      if(BT){
        cout << " " << BT->data;
        preorderTraversal(BT->lchild);
        preorderTraversal(BT->rchild);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    int b[32],a[32];
    BiTree T;
    for(int i=0; i<n; i++)
        cin>>a[i];
    for(int i=0; i<n; i++)
        cin>>b[i];
    T=Plustree(b,a,n);

    printf("Preorder:");
    preorderTraversal(T);


}

 

数据结构/PTA-据后序和中序遍历输出先序遍历/树

标签:scan   amp   lse   color   col   cout   its   using   bre   

原文地址:https://www.cnblogs.com/elegantcloud/p/13907262.html

版权声明:完美者 发表于 2020-11-01 10:27:16。
转载请注明:数据结构/PTA-据后序和中序遍历输出先序遍历/树 | 完美导航

暂无评论

暂无评论...