PAT甲级1147题（堆遍历）

数据结构题

PAT

发布日期: 2021-02-19

文章字数: 255

阅读时长: 1 分

阅读次数:

1.题目介绍

1147

2.考察点，难度

堆数据结构，Vector容器使用方法，堆判断，层次与后序遍历，难度中

3.解题代码

#include <bits/stdc++.h>
using namespace std;

int M,N,ans=0;
vector<int> v;

void postorder(int index){
    if(index*2>N && index*2+1>N) {
        if(index<=N)  {
            if(!ans){
                cout<<v[index];
                ans++;
            }
            else cout<<" "<<v[index];
        }
    }
    else{
        postorder(index*2);
        postorder(index*2+1);

        if(!ans){
            cout<<v[index];
            ans++;
        }
        else cout<<" "<<v[index];
    }
}


int main(){

    freopen("D:\\PAT\\Clion\\in.txt","r",stdin);

    scanf("%d %d",&M,&N);
    for(int p=0;p<M;p++){
        v.resize(N+1);
        ans=0;
        int s,ismin=0,ismax=0;
        for(int t=1;t<=N;t++){
            scanf("%d",&s);
            v[t]=s;
        }
        for(int i=2;i<=N;i++){
            if(v[i/2]>v[i])ismax++;
            else if(v[i/2]<v[i])ismin++;
        }
        if(ismax && ismin)   cout<<"Not Heap"<<endl;
        else if(ismin)  cout<<"Min Heap"<<endl;
        else if(ismax)  cout<<"Max Heap"<<endl;
        postorder(1);
        cout<<endl;
        v.clear();
    }
    return 0;
}