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

堆的定义

堆其实就是一棵完全二叉树(若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边),定义为:具有n个元素的序列(h1,h2,...hn),当且仅当满足(hi>=h2i,hi>=h2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。

大顶堆

堆顶元素(即第一个元素)为最大项,并且(hi>=h2i,hi>=h2i+1),通俗地说父节点比子节点大。

小顶堆

堆顶元素为最小项,并且(hi<=h2i,hi<=2i+1),父节点比子节点小。

堆的性质

当前节点的序号为index,其左右两个自节点的序号为index*2和index*2+1,其父节点的序号为int(index/2);

满二叉树

一棵深度为k,且有 2k+1−1 个节点的二叉树,称为满二叉树(Full Binary Tree)。 这种树的特点是每一层上的节点数都是最大节点数。

完全二叉树

而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树(Complete Binary Tree)。高度(深度): 即层数k,注意【根】定义为height(root)=0。

完全二叉树的性质

  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)

完全二叉树层次遍历转后序遍历(不构造树)

从1开始

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.

Sample Input

Sample Output

作者: CHEN, Yue
单位: 浙江大学
时间限制: 200 ms
内存限制: 64 MB
代码长度限制: 16 KB

代码

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.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

作者: 陈越
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
 代码

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注