关于算法-数据结构:PAT甲级1147-Heaps

题目粗心：

现有M个查问，每一个查问给定一个长度为N的齐全二叉树层序序列，判断该二叉树是大根堆，小根堆和非堆，而后输入该齐全二叉树的后序遍历序列。

算法思路：

对于齐全二叉树能够应用一个数组来保留其层序序列，而后应用函数isMaxHeap和isMinHeap别离判断该齐全二叉树是否是大根堆还是小根堆，如果都不是则输入Not Heap，而后再应用postTraverse对该齐全二叉树进行后序遍历，拜访节点的时候输入节点即可。

isMaxHeap

// 判断是否是大根堆bool isMaxHeap(){    for (int i = 1; i <= N; ++i) {        if((2*i<=N&&heap[2*i]>heap[i])||(2*i+1<=N&&heap[2*i+1]>heap[i])){            return false;        }    }    return true;}

isMinHeap

// 判断是否是小根堆bool isMinHeap(){    for (int i = 1; i <= N; ++i) {        if((2*i<=N&&heap[2*i]<heap[i])||(2*i+1<=N&&heap[2*i+1]<heap[i])){            return false;        }    }    return true;}

提交后果：

AC代码：

#include<cstdio>using namespace std;int heap[1005];int M,N;// 判断是否是大根堆bool isMaxHeap(){    for (int i = 1; i <= N; ++i) {        if((2*i<=N&&heap[2*i]>heap[i])||(2*i+1<=N&&heap[2*i+1]>heap[i])){            return false;        }    }    return true;}// 判断是否是小根堆bool isMinHeap(){    for (int i = 1; i <= N; ++i) {        if((2*i<=N&&heap[2*i]<heap[i])||(2*i+1<=N&&heap[2*i+1]<heap[i])){            return false;        }    }    return true;}int num;// 管制空格输入void postTraverse(int root){    if(root>N) return;    postTraverse(2*root);    postTraverse(2*root+1);    printf("%d",heap[root]);    if(num<N-1) printf(" ");    ++num;}int main(){    scanf("%d %d",&M,&N);    for (int i = 0; i < M; ++i) {        // M次查问        num = 0;// 每次都得赋值为0        for (int j = 1; j <= N; ++j) {            scanf("%d",&heap[j]);        }        if(isMinHeap()){            printf("Min Heap\n");        } else if(isMaxHeap()){            printf("Max Heap\n");        } else {            printf("Not Heap\n");        }        postTraverse(1);        printf("\n");// 记得换行    }    return 0;}