【PTA数据结构 | C语言版】是不是堆

本专栏持续输出数据结构题目集，欢迎订阅。

题目

给定一个完全二叉树的层序遍历序列，请判断该二叉树是否是二叉堆。

输入格式：
每组测试第 1 行包含 2 个正整数：m (≤100) 是二叉树的个数；n（1<n≤1000）是每个二叉树中结点的个数。随后 m 行，每行给出 n 个不重复的整数键值（均在 32 位整型 int 范围内），是一个完全二叉树的层序遍历序列。

输出格式：
对每个输入中给定的二叉树，如果其对应了一个最大堆，则在一行中输出 Max Heap；如果对应最小堆，则输出 Min Heap；否则输出 Not Heap。随后在下一行输出这棵树的后序遍历序列。一行中的数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

输出样例：
Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10

代码

#include <stdio.h>
#include <stdlib.h>#define MAXN 1001int tree[MAXN];
int n;// 判断是否为最大堆
int isMaxHeap() {for (int i = 1; i <= n/2; i++) {int left = 2 * i;int right = 2 * i + 1;if (left <= n && tree[i] < tree[left]) return 0;if (right <= n && tree[i] < tree[right]) return 0;}return 1;
}// 判断是否为最小堆
int isMinHeap() {for (int i = 1; i <= n/2; i++) {int left = 2 * i;int right = 2 * i + 1;if (left <= n && tree[i] > tree[left]) return 0;if (right <= n && tree[i] > tree[right]) return 0;}return 1;
}// 后序遍历二叉树
void postOrder(int root, int *index, int *result) {if (root > n) return;postOrder(2 * root, index, result);       // 遍历左子树postOrder(2 * root + 1, index, result);   // 遍历右子树result[(*index)++] = tree[root];          // 访问根节点
}int main() {int m;scanf("%d %d", &m, &n);for (int i = 0; i < m; i++) {// 读取层序遍历序列for (int j = 1; j <= n; j++) {scanf("%d", &tree[j]);}// 判断堆的类型if (isMaxHeap()) {printf("Max Heap\n");} else if (isMinHeap()) {printf("Min Heap\n");} else {printf("Not Heap\n");}// 后序遍历int result[MAXN];int index = 0;postOrder(1, &index, result);// 输出后序遍历结果for (int k = 0; k < n; k++) {if (k > 0) printf(" ");printf("%d", result[k]);}printf("\n");}return 0;
}