二叉树叶子节点数的问题

来源：百度知道 编辑：UC知道 时间：2024/06/24 08:02:47
已知完全二叉树有500个结点，求共有多少个叶子结点，此类题目有什么公式吗？

满二叉树的节点数为 2的N次方-1，由此可知此完全二叉树对应的满二叉树的节点数为511，层数为9

由此，此完全二叉树最后一层（9层）有500-2的八次方+1=245个节点。那么8层有2的七次方-(245+1)/2=5个节点是叶子节点。

所以共有叶子节点245+5 =250个。（最后一层节点数+倒数第二层的叶子节点数）

共有245个叶子结点，其计算公式如下；

（2^i-1）<= N <=（2^(i+1)-1） 根据这个公式把i求出来，（N代表总的结点数，i表示前i是满的，第i+1层不一定是满的）

其叶子结点数=N-(2^i-1）