怎么算完全二叉树中叶子节点数？

Question

如题所述

Answer 1

方法1: 先计算完全二叉树的总节点数,根据总节点数,得出叶子节点数.

完全二叉树的前7层是满二叉树,根据公式: 节点数 = 2^N - 1,
其中,N是7,所以其节点数是 2^7 - 1 = 127  (注:2^7表示2的7次方)
加上第8层的8个节点,该完全二叉树的总节点数是127+8=135
根据公式 n0 = (N奇 + 1)/2 = (135+1)/2 = 68
n0是叶子节点数,N奇 表示总节点数135是奇数,
所以,叶子节点数是68

公式 n0 = (N奇 + 1)/2 的推导,可参考文章"完全二叉树总结点数与叶结点数关系分析"

方法2: 

完全二叉树的第7层的节点数是2^(7-1)=2^6=64
第8层的节点数是8,这8个都是叶子节点,8是偶数,表示第7层有4个节点是这8个节点的父节点,
那么,第7层的叶子数是64-8/2=60
所以,总的叶子节点数是60+8=68