PAT 1147 Heaps C++版

PAT 1147 Heaps C++版

1.题意

给出一个完全二叉树，让你判断是大根堆还是小根堆，并输出这棵二叉树的后序输出。

2.分析

• step1:因为是完全二叉树，所以很好判断是否是大根堆小根堆。
• step2:那如何输出后序序列呢？可以通过构建一棵静态二叉树的方法，然后遍历输出即可。

3.代码

#include<cstdio> 
#include<queue>
#include<iostream>
#define maxn 10005

using namespace std;

struct tree{
	int left;
	int right;
	int data;
}; 

int M,N;
int arr[maxn];//用于存储数据 
queue<int> que;//用于存储数据的 
tree bs[maxn];//用于建静态二叉树bs 
vector<int> ans;//用于保存结果 
 
void solve(){
	int i = 1,index = 1;//表示正在用到哪个元素 【从2开始】	
	while(!que.empty()){//当队列非空时 		
		bs[index].data = que.front();
		if(i < N) bs[index].left = ++i; 
		else bs[index].left = -1;
		if(i < N) bs[index].right = ++i;	
		else bs[index].right = -1;//以-1标记没有子节点 
		que.pop();//队首元素出队 
		index++;
	}
}

//后序遍历 
void postOrd(int root){
	if(bs[root].left!=-1) postOrd(bs[root].left);
	if(bs[root].right!=-1) postOrd(bs[root].right);
	ans.push_back(bs[root].data); 
}

int main(){	
	cin >> M >> N;		
	int i,j; 
	while(M--){//输入各组测试数据 	 
		for(i = 1;i<= N;i++){//从1开始 
			cin >> arr[i] ;
			que.push(arr[i]);//推入到queue中 
		}
		bool minHeap = false, maxHeap = false;//初始状态均为false 	
		for(i = 1;i<= N;i++){//判断是大根堆还是小根堆 
			int temp1 = i*2, temp2 = i*2+1;
			if( temp1 <= N ){//如果在N这个范围内 
				if(arr[temp1] > arr[i]) minHeap = true;
				if(arr[temp1] < arr[i]) maxHeap = true;
			}
			if(temp2 <= N){
				if(arr[temp2] > arr[i]) minHeap = true;
				if(arr[temp2] < arr[i]) maxHeap = true;
			}
		}
		if(maxHeap && minHeap) cout <<"Not Heap\n";
		else if(maxHeap) cout <<"Max Heap\n";
		else if(minHeap) cout <<"Min Heap\n";		
		
		solve();		
		ans.clear();
		postOrd(1);
		for(i = 0;i< N;i++){
			if (i!=N-1) cout << ans[i]<<" ";
			else cout <<ans[i]; 
		}
		cout <<"\n";
	}
}

4.测试用例

1 8
98 72 86 60 65 12 23 50

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

5.执行结果