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

本文共3680个字,预计阅读时间需要10分钟。

堆的定义

堆其实就是一棵完全二叉树(若设二叉树的深度为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 s