树八真题2021.10.2

完全二叉树的前7层是完全二叉树，根据公式:？节点数？=?2^N？-?1,

其中n是7，所以节点数是？2^7?-?1?=?127(注:27表示2的7次方)

在第8层加上8个节点，完整二叉树的节点总数为127+8=135。

根据公式？没有吗？=?(n奇数？+?1)/2?=?(135+1)/2?=?六十八

N0是叶节点的个数，n为奇数？表示节点总数135是奇数，

因此，叶节点的数量是68

公式？没有吗？=?(n奇数？+?1)/2?的推导请参考文章《完全二叉树的和点与叶节点数的关系分析》

方法二:？

一棵完全二叉树的第7层节点数是2(7-1)= 2 ^ 6 = 64。

第八层的节点数是8，都是叶子节点，8是偶数，意味着第七层有四个节点是这八个节点的父节点。

那么，第七层的叶子数就是64-8/2=60。

因此，叶节点的总数是60+8=68