所有结点度为0或2
满二叉树 所有结点度为0或2 且叶子节点都在最后一层
叶子结点只会出现在最后两层，且最后一层叶子结点靠左对齐

真二叉树性质

1.度为1的结点只有左子树
2.度为1的结点要么只有1个，要么有0个结点
3.同样结点数量的二叉树，完全二叉树的高度最小

假设完全二叉树的高度为h(h≥1),那么有2^h-1个结点（最后一层至少有一个），有2^h-1个结点（满二叉树）。

如果高度h，总的结点树为n

2^h-1 ≤ n < 2^h ===推出===》 h - 1 ≤ < h ===》h = floor( ) + 1

一棵树有n(n>0)个结点的完全二叉树，从上到下，从左到右从1开始进行编号，对于任意第i个结点

image.png

1.如果i = 1，它是根结点
2.如果i > 1, 它的父结点编号为floor(i / 2) ,
3.如果 2i < n ,它的左子结点编号为2i
4.如果2i > n, 它没有左子结点
5.如果2i + 1 ≤ n， 它的右子结点编号为2i + 1

思考

一个完全二叉树有768个结点，求叶子结点树个数。

假设：叶子结点树为n0,度为1的节点数为n1， 度为2的结点树为n2

二叉树的边数 = n1 + 2 * n2(度为1有一条边，度为2有两条边) = n - 1（跟结点顶部没有边要减去） = n0 + n1 + n2 - 1 （叶子结点数 + 度为1的结点数 + 度为2的结点数 - 1）
即 n1 + 2 *n2 = n0 + n1 +n2 -1   推出 n0 = n2 + 1 即 叶子结点数等于度为2的结点数 + 1

总结点树 n = n0 + n1 + n2，且n0 = n2 + 1 ，推出 n = 2n0 + n1 - 1
由于完全二叉树n1 要么为0，要么为1

当n1= 1时， n = 2n0,n 必为偶数
此时，叶子结点数n0 = n / 2,非叶子结点数 n1 + n2 = n / 2
当n = 0时，n = 2n0 - 1, n 必为奇数
此时叶子结点数 n0 = (n + 1) / 2

在计算机语言中，除法一般默认为向下取整
所以 n0 = floor((n + 1) / 2)
结果为 (768 + 1) / 2 = 384.5 = 384个叶子结点

n = 1, n0 = 1
n = 2, n0 = 1
n = 3 , n0 = 2
n = 4, n0 = 2
.......