PAT_ Class A _1147 HEAPS

The main idea of the topic is:

There are M queries, and each query is given a complete binary tree hierarchical sequence of length N. It is judged that the binary tree is a large root heap, a small root heap and a non-heap, and then the post-ordered traversal sequence of the complete binary tree is output.

Algorithm idea:

For the complete binary tree, an array can be used to store its hierarchical sequence, and then functions ismaxHeap and isminHeap are used to determine whether the complete binary tree is a large root Heap or a small root Heap respectively. If neither is the case, output NOT Heap, and then use PostTraverse to perform post-order traversal of the complete binary tree. The output node can be accessed when the node.

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; }

Submission Result:

AC code:

#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) {num = 0; Int j = 1; 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; }