完全⼆叉树的性质
完全⼆叉树的性质
定义
满⼆叉树
⼀棵深度为k ，且有 $2^{k+1}-1$ 个节点的⼆叉树，称为满⼆叉树（Full Binary Tree ）。 这种树的特点是每⼀层上的节点数都是最⼤节点数。
完全⼆叉树
⽽在⼀棵⼆叉树中，除最后⼀层外，若其余层都是满的，并且最后⼀层或者是满的，或者是在右边缺少连续若⼲节点，则此⼆叉树为完全⼆叉树（Complete Binary Tree ）。⾼度（深度）
二叉树的基本性质即层数k ，注意【根】定义为$height(root)=0$
。
性质
1. 具有n 个节点的完全⼆叉树的深度为 k =log 2n  。
2. 【满⼆叉树】i 层的节点数⽬为：2i
3. 【满⼆叉树】节点总数和深度的关系：n =∑k i =02i =2
k +1−14. 【完全⼆叉树】最后⼀层的节点数为：n −(2k −1)=n +1−2k  （因为除最后⼀层外，为【满⼆叉树】）
5. 【完全⼆叉树】左⼦树的节点数为（总节点为n ）：
l (n )=n −2k −1,
n +1−2k ≤2k −1 因为最后⼀层全部都在左⼦树，右⼦树为【满⼆叉树】⾼度为 k-22k −1,n +1−2k >2k −1 因为左⼦树为满⼆叉树，⾼度为k-1
6. 【完全⼆叉树】右⼦树： r (n )=n −l (n ){Processing math: 100%