PAT甲级1147Heaps

Posted on | | Visitors:
Words count in article: 585 字 | Reading time ≈ 3 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805342821531648

题解

题目要求

给定一个完全二叉树，请判断它是不是堆（大顶堆指父结点的值大于等于子结点的值，小顶堆指父结点的值小于等于子结点的值）

  • 输入
    • M：需要测试的树的数量，不超过100
    • N：每颗树中值的数量，大于1，不超过1000
    • M颗树：每颗树包含N个互异的值（int范围内），按照层次遍历的顺序给出
  • 输出
    • 对于每颗树，输出它是最大堆还是最小堆，或者它不是个堆，然后后序遍历输出这个树，值之间用空格间隔

思路

  • 完全二叉树性质
    • 如果某结点的序号为i，如果它的左右子结点存在，那左子结点序号为2i，右子结点序号为2i+1。
    • 相应地，如果某子结点的序号为i，那其父结点的序号为i/2，其中i为int类型、只取i/2所得结果的整数部分。
  1. 因为是完全二叉树，所以不用建树，将所有结点按层次遍历的顺序存入数组即可
  2. 遍历除了根结点以外的结点，判断是否违反大顶堆或小顶堆的特点，然后输出是否是堆
  3. 递归实现后序遍历

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Problem: PAT Advanced 1147
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805342821531648
// Tags: Tree DFS Heap

#include <iostream>
using namespace std;

int nodes[1005]; // 存储n个结点
int m, n;

void postOrderTrace(int i){
    if (i > n) return ; // 避免越界
    postOrderTrace(2 * i);
    postOrderTrace(2 * i + 1);
    if (i == 1) printf("%d\n", nodes[i]);
    else printf("%d ", nodes[i]);
}

int main()
{
    scanf("%d %d", &m, &n);

    while (m--){
        for (int i = 1; i <= n; i++) // 读取树
            scanf("%d", nodes+i);

        bool isMaxHeap = true, isMinHeap = true; // 遍历判断是否是大小顶堆
        for (int i = 2; i <= n; i++)
            if (nodes[i] > nodes[i/2]) isMaxHeap = false;
            else if(nodes[i] < nodes[i/2]) isMinHeap = false;
        if (isMaxHeap) printf("Max Heap\n");
        else if(isMinHeap) printf("Min Heap\n");
        else printf("Not Heap\n");

        postOrderTrace(1); // 后序遍历完全二叉树
    }
    return 0;
}

参考链接

https://www.cnblogs.com/chouxianyu/p/13293152.html

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!