完全二叉树中叶子结点的计算方法
applestar334 · · 个人记录
| 表示 | 含义 |
|---|---|
| n0 | 叶子结点 |
| n1 | 度为1的结点 |
| n2 | 度为2的结点 |
二叉树上结点关系，总结点数为S
从结点关系上可知：
（1）S=n0+n1+n2；
从树枝上可知，总的树枝与结点数关系有S-1个树枝，其中各中结点贡献为
（2）S-1=n1+2n2+0n0 ==> （2）S=n1+2*n2+1；
由（1）式与（2）式得：n0+n1+n2=n1+2*n2+1 ==>n0=n2+1
重要结论：n0=n2+1
对于二叉树上的叶子结点数来说：S=n0+n1+n0-1 ==> n0=(S+1-n1)/2
对于完全二叉树来说 n1=1 或 n1=0
分情况讨论
(1)当 n1=0时，总结点数S为奇数，n0=(S+1)/2，为整数；
(2)当 n1=1时，总结点数S为偶数，n0=S/2，为整数；
(结论):一个具有S个节点的完全二叉树,其叶子节点的个数n0为: S/2 向上取整，或者(S+1)/2 向下取整。
由于在计算机中整数除法使用的是向下取整，所以n0=(S+1)/2.