大家好，又见面了，我是你们的朋友全栈君。
完全二叉树
若二叉树左子树高度-右子树高度小于等于1且大于等于0则称该二叉树为完全二叉树。
二叉树一般性质：
性质1：二叉树第i层上的结点数目最多为 2 i − 1 ( i ≥ 1 ) 2^{i-1}(i \geq 1) 2i−1(i≥1)
性质2：深度为k的二叉树至多有 2 k − 1 ( k ≥ 1 ) 2^{k-1}(k \geq 1) 2k−1(k≥1)个结点
性质3：包含n个结点的二叉树的高度至少为 log 2 n + 1 \log_2n+1 log2n+1
性质4：在任意一棵二叉树中，若叶子结点的个数为 n 0 n_0 n0，度为2的结点数为 n 2 n_2 n2，则 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
性质4推导:
易知结点总数 n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0+n1+n2，根据二叉树的度之和（边数量）=n-1，可得 n − 1 = n 0 ∗ 0 + n 1 ∗ 1 + n 2 ∗ 2 n-1=n_0*0+n_1*1+n_2*2 n−1=n0∗0+n1∗1+n2∗2。
联合上面两个公式即可得到性质4
完全二叉树性质：
性质1：度为1的结点仅有1个或0个（叶子节点尽可能往左排）
性质2：叶子结点个数 = n 2 =\frac{n}{2} =2n或 = n + 1 2 =\frac{n+1}{2} =2n+1（n为奇数）
利用 n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0+n1+n2与 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1与性质1容易证明。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/138250.html原文链接：https://javaforall.net
