PAT|1147 Heaps(最大堆、最小堆、二叉树的遍历）

题目大意

在计算机科学中，堆是一种特殊的基于树的数据结构，它满足堆属性：如果 P 是 C 的父节点，则 P 的键（值）要么大于或等于（在最大堆中） ) 或小于或等于（在最小堆中）C 的键。堆的常见实现是二叉堆，其中树是完全二叉树。 （引自维基百科 https://en.wikipedia.org/wiki/Heap_(data_structure)） 你的工作是判断一个给定的完整二叉树是否是一个堆。

解题分析

• 首先需要明白最大、最小堆的定义
• 根据完全二叉树可以由下标计算出孩子节点的下标，进而访问
• 最后进行后序遍历即可

代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
bool minheep, maxheep;
vector<int> vec;
vector<int> post;
void judgeMaxHeep(int index) {
	if (index * 2 <= m) {//存在左节点
		if (vec[index] < vec[index * 2]) {
			maxheep = false;
		}
		else {
			judgeMaxHeep(index * 2);
		}		
	}
	if (index * 2 + 1 <= m) {//存在右节点
		if (vec[index] < vec [index * 2 + 1]) {
			maxheep = false;
		}
		else {
			judgeMaxHeep(index * 2 + 1);
		}
	}
}
void judgeMinHeep(int index) {
	if (index * 2 <= m) {//存在左节点
		if (vec[index] > vec[index * 2]) {
			minheep = false;
		}
		else {
			judgeMinHeep(index * 2);
		}
	}
	if (index * 2 + 1 <= m) {//存在右节点
		if (vec[index] > vec[index * 2 + 1]) {
			minheep = false;
		}
		else {
			judgeMinHeep(index * 2 + 1);
		}
	}
}
void postorder(int index) {
	if (index * 2 <= m) {
		postorder(index * 2);
	}
	if (index * 2 + 1 <= m) {
		postorder(index * 2 + 1);
	}
	post.push_back(vec[index]);
}
void printPost() {
	if (post.size() >= 1) {
		cout << post[0];
	}
	for (int i = 1; i < m; i++) {
		cout << ' ' << post[i];
	}
	cout << endl;
}
int main() {
	//根据层次遍历判断是否为最大或者最小堆
	cin >> n >> m;
	vec.resize(m + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> vec[j];
		}
		minheep = maxheep = true;
		judgeMaxHeep(1);
		judgeMinHeep(1);
		if (maxheep == true) {
			cout << "Max Heap" << endl;
		}
		else if (minheep == true) {
			cout << "Min Heap" << endl;
		}
		else {
			cout << "Not Heap" << endl;
		}
		post.clear();
		postorder(1);
		printPost();
	}

	return 0;
}