完全二叉树和满二叉树

在排序算法中有一种叫做堆排序的方法，堆一般是用完全二叉树实现，所以记录下完全二叉树和满二叉树

完全二叉树：若设二叉树的深度为h，除第h层外，其他各层（1~h-1）的节点数都达到最大个数，第h层所有节点都连续集中在最左边，这就是完全二叉树

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。满二叉树一定是完全二叉树，不同的是最后一层的所有节点都有两个字节点。

图片来源：https://blog.****.net/njdragonfly/article/details/6373199

完全二叉树的特点：

性质1 ：总层数为n，第$i(0&lt;i&lt;n)$i(0<i<n)层上节点个数为$2^{i-1}$2i−1，第n层的叶子节点最多为 $2^{n-1}$2n−1

证明:
  (1)第一层的节点个数为$2^{0}$20;
  (2)第二层的节点个数为$2^{1}$21;
  (3)第$i$i层的节点个数为$2^{i-1}$2i−1;
  (4)最后一层叶子节点最多为$2^{n-1}$2n−1（满二叉树）;

性质2: 深度为n的二叉树，最多有2ⁿ-1:
证明：
  假设第i层的节点数为X _i,则
$\sum_{i=0}^{n}X_{i} &lt;= \sum_{i=0}^{n}2^{i-1}=2^{n}-1$i=0∑n​Xi​<=i=0∑n​2i−1=2n−1

性质3:对于非空的二叉树，如果叶子节点数为$n_{0}$n0​,度为2的节点数为$n_{2}$n2​,度为1的节点数为$n_{1}$n1​,z则有$n_{0} = n_{2} + 1$n0​=n2​+1
证明：
  设$N$N为二叉树的节点总数，则有$N = n_{0} + n_{1} + n_{2}$N=n0​+n1​+n2​.另一方面，除根节点之外，其余所有节点有唯一的一个进入分支。设$B$B为二叉树的分支数，那么：$B = N-1$B=N−1,这些分支是由度为1和度为2的节点发出的，所以：$B = n_{1} + 2*n{2}$B=n1​+2∗n2,综上所述：
$n_{0} = n_{2} + 1$n0​=n2​+1

性质4: 具有$N$N个节点的完全二叉树的深度为$k$k为$[\log_{2}^{n}]+1$[log2n​]+1
证明：
  假设一颗完全二叉树的深度为$k$k，节点个数为$N$N,则有：
$2^{k-1}-1&lt;N\leq2^{k}-1$2k−1−1<N≤2k−1
  即：
$2^{k-1} \leq N&lt;2^{k}$2k−1≤N<2k
  同时取对数：
$k-1 \leq \log_{2}^{N} &lt; k$k−1≤log2N​<k
  所以$k$k的 取值为：$[\log_{2}^{n}]+1$[log2n​]+1

性质5:
对于具有 N 个节点的完全二叉树，如果按照从上至下和从左到右的顺序
对二叉树中的所有节点从 1 开始顺序编号，则对于任意的序号为 $i$i 的
节点，有,
(1) 如果 $ i> 1$ 则序号为 $i$i 的节点的双亲节点的序号为$i/2$i/2 如果 i = 1则序号为 $i$i 的节点是根节点, 无双亲节点；
(2) 如果 $2i \leq N$2i≤N 则序号为 i 的节点的左孩子节点的序号为 $2i$2i 如果$2i &gt; N$2i>N 则序号为 $i$i 的节点无左孩子；
(3) 如果 $2i+1 \leq N$2i+1≤N,则序号为 $i$i 的节点的右孩子节点的序号为$2i+1$2i+1,如果 $2i+1 &gt; N$2i+1>N,则序号为$i$i的节点无右孩子；