1147 Heaps (30 分)

1147 Heaps (30 分)

题目大意

给定一组由完全二叉树层次遍历得到的序列，判断它是否是一个大根堆、小根堆、或非根堆。

基本思路

对于每一组数据，从它的最后一个非叶子结点开始逆序遍历，比较它与左右孩子结点的大小关系，先假设它是大根堆/小根堆，如果违反了大根堆或者小根堆的定义，则进行否定(flag1和flag2的值)，根据flag1或者flag2的值输出属于什么根堆。然后输出这一组序列后序遍历的结果。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1010;
int k,n;
int cnt;
int data[maxn];
int flag1,flag2;//是否是大、小根堆
void post_dfs(int i,int n){
    if(i>n) return;
    post_dfs(2*i,n);
    post_dfs(2*i+1,n);
    if(cnt<n){
        cout<<data[i]<<" ";
        cnt++;
    }else if(cnt==n){
        cout<<data[i]<<endl;
    }
}
int main(){
    cin>>k>>n;
    while(k--){
        cnt=1;
        flag1=1;
        flag2=1;
        for(int i=1;i<=n;i++) cin>>data[i];
        int half=n/2;
        //判断是否是大根堆
        for(int i=half;i>=1;i--){
            int j=2*i;
            if(j+1<=n&&data[j+1]>data[j]) j=j+1;
            if(data[i]<data[j]){
                flag1=0;
                break;
            }
        }
        if(flag1){
            cout<<"Max Heap"<<endl;
            post_dfs(1,n);//后序遍历完全二叉树
            continue;
        }
        //判断是否是小根堆
        for(int i=half;i>=1;i--){
            int j=2*i;
            if(j+1<=n&&data[j+1]<data[j]) j=j+1;
            if(data[i]>data[j]){
                flag2=0;
                break;
            }
        }
        if(flag2){
            cout<<"Min Heap"<<endl;
            post_dfs(1,n);//后序遍历完全二叉树
            continue;
        }
        //它是非根堆
        cout<<"Not Heap"<<endl;
        post_dfs(1,n);//后序遍历完全二叉树
        continue;
    }
}

---

看了柳神的代码之后，发现她的方法更加简洁,，链接如下：

https://blog.csdn.net/liuchuo/article/details/79810648

基本思路

从后往前检查所有的结点（除了根结点）和它的父结点的关系，判断是否破坏最大堆或者最小堆的性质，如果有不满足的情况将flag1和flag2置为0，以此排除最大堆或者最小堆。
然后后序遍历，对于index结点分别遍历孩子index2和右孩子index2+1，遍历完左右子树后输出根结点。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1010;
int k,n;
int data[maxn];
void post_dfs(int i){
    if(i>n) return;
    post_dfs(2*i);
    post_dfs(2*i+1);
    printf("%d%s",data[i],i==1?"\n":" ");//后序遍历最后一个输出的一定是根结点，节点编号是1
}
int main(){
    cin>>k>>n;
    while(k--){
        int flag1=1,flag2=1;//是否是大、小根堆
        for(int i=1;i<=n;i++) cin>>data[i];
        //判断是否是大、小根堆
        for (int i = 2; i <= n; i++) {
            if (data[i] > data[i / 2]) flag1 = 0;
            if (data[i] < data[i / 2]) flag2 = 0;
        }
        //根据flag1和flag2的值输出属于什么根堆
        if(flag1) cout<<"Max Heap"<<endl;
        else if(flag2) cout<<"Min Heap"<<endl;   
        else cout<<"Not Heap"<<endl;
        //后序遍历完全二叉树
        post_dfs(1);
    }
}