# 完全二叉树与堆C++代码及应用

## 完全二叉树的性质

1. 具有n个节点的完全二叉树的深度为 k=log2n 。
2. 【满二叉树】i层的节点数目为：2i
3. 【满二叉树】节点总数和深度的关系：n=∑ki=02i=2k+1−1
4. 【完全二叉树】最后一层的节点数为：n−(2k−1)=n+1−2k （因为除最后一层外，为【满二叉树】）
5. 【完全二叉树】左子树的节点数为（总节点为n）：l(n)={n−2k−1,2k−1,n+1−2k≤2k−1因为最后一层全部都在左子树，右子树为【满二叉树】高度为 k-2n+1−2k>2k−1因为左子树为满二叉树，高度为k-1
1. 【完全二叉树】右子树： r(n)=n−l(n)

## PAT 甲级 1147 Heaps （30 分）

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

Your job is to tell if a given complete binary tree is a heap.

### Input Specification

Each input file contains one test case. For each case, the first line gives two positive integers: M ( 100), the number of trees to be tested; and N (1  N  1,000), the number of keys in each tree, respectively. Then M lines follow, each contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

### Output Specification

For each given tree, print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all. Then in the next line print the tree’s postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.

## PAT 甲级 1155 Heap Paths （30 分）

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

One thing for sure is that all the keys along any path from the root to a leaf in a max/min heap must be in non-increasing/non-decreasing order.

Your job is to check every path in a given complete binary tree, in order to tell if it is a heap or not.

### Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer  (), the number of keys in the tree. Then the next line contains  distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

### Output Specification

For each given tree, first print all the paths from the root to the leaves. Each path occupies a line, with all the numbers separated by a space, and no extra space at the beginning or the end of the line. The paths must be printed in the following order: for each node in the tree, all the paths in its right subtree must be printed before those in its left subtree.

Finally print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all.

代码

[评分人数: 1 平均分: 5]