完全二叉树:
如果二叉树的深度为k,则除第k层外其余所有层节点的度都为2,且叶子节点从左到右依次存在。也即是,将满二叉树的最后一层从左到右依次删除若干节点就得到完全二叉树。满二叉树是一棵特殊的完全二叉树,但完全二叉树不一定是满二叉树。
假设一个二叉树有n个节点:
度为0的节点个数是n0
度为1的节点个数是n1
度为2的节点个数是n2
则有如下公式成立:
n0 = n2 + 1 (1)
n0 = (n +1) / 2 (2)(完全二叉树)
n = n0 + n1 +n2
因为 n0 = n2 + 1
所以 n = 2 * n0 + n1 - 1
因为是完全二叉树,所以 n1 只能等于0或1
所以 n = 2 n0 - 1 或 n = 2 n0
也就是n0 = (n + 1) / 2