一棵有124个叶结点的完全二叉树，最多有多少结点？

请教数据结构高手

---

最多有248个结点。

根据完全二叉树性质，叶子结点数n0等于树结点数n的二分之一，即n0=n/2 ，或叶子结点数n0等于树结点数n加上1之和的二分之一，即n0=(n+1)/2。

两陪世闷个公式变形得，n=2*n0或n=2*n0－芦弯1，题中要求树的最多结点数，即树的结点数等于叶子数的2倍，n=2*n0＝2*124＝248。

扩展资料：

完全二叉树性质推导：

假设n0是度为0的节点总数（即叶子结点数），n1是度为1的节点总数，n2是度为2的节点总数。

因为n= n0+n1+n2（其中n为完全二叉树的节点总数），又因为一个度为2的节点会有2个子结点，一个度为1的结点会有1个子结点，返磨除根结点外其他节点都有父结点，得到n= 1+n1+2*n2；

由n= n0+n1+n2和n= 1+n1+2*n2两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）向下取整。可根据完全二叉树的结点总数计算出叶子结点数。

参考资料来源：百度百科—完全二叉树

参考资料来源：百度百科—叶子结点

---

你们都是用文字解释的，感觉还是用图来对初学者解释比较友好，画的比较糙，凑活看一下

题目描述一共有124个叶子结点，首先通过计算，得知第七层最多有64个叶子节点，不合符条件，所以这棵树的高度必须大于7，也就是有八层。

第八层如果是满的，会有128个叶子节点，所以当第八层有120个叶子节点烂毁时，加上第七层空出来的四个叶子节点，正好是124个叶子节点,所以求得一共有127+120=247个节饥虚备点

如图所示A为前7层的整体，B为第八层的一部分.

但这道题的求得是最大节点数,我们来看另一种情况

请点击输入图片

重点来了，在第七层C处增加一个左孩子誉搜，叶子节点数目保持不变，但是增加了一个节点，从而结点总数为，前七层的总结点 1+2+4+8+16+32+64=127，再加上第八层的121个叶子结点，127+121=248个

---

124个叶子节点.表示有7层

2的7次方啊

124+2的7次洞颤郑方-1

124+127

即251

呵呵.不过答案是248

这是7层最多的节点

251是错的。

124个叶子结点纳颂并不是在最后一层的。

最后一层应该只有121个结点，所以，答案应该是121+127＝248个结点

题目是说叶子结点个数，并不是末层结点的个数

121是如何算的啊

128-（（128-124） * 2 - 1）

会不会是247？

应该是奇数？

248

第7层最多 127个

127+121

可以这样来求解，假设末层结点数为X，则洞枝有：

(64-（124-X）)*2 = X 当末层结点数为偶数时

或者(64-（124-X）)*2 = X + 1 奇

也即，X = 120 或者 X = 121然后再进行验证即可。

127＋120

247应该也是正确答案。这要看备选答案里有没有247了

对的，加上最多这个条件当然应该是248了。

---

完整的完全二叉树的节点个数等于叶子节点的两倍减去1，
这是根据树的层次来的，除去最后一层的第n层的节点告扰个数等于2的（n-1）次方，则完整的完全二叉树的节点个数等于2的m次方减去1（设共有m层）。
124个叶子节点，说明它不是完整的，2的6次方等于64，2的7次方等于128，64<124<128，说明该树共有8层(7+1),因为完全二叉树每个节点（叶子节点除外）都有两个子节点，完整的8层袜陵旦完全二叉树共有128个叶子节点，该树为124个，128-124=4，说明有4个叶子节点在次高层汪缺，即第7层有4个叶子节点，说明该树比完整的8层完全二叉树少了8个节点（这4个叶子节点在完整二叉树中有8个子节点），可以计算了
完整的8层的完全二叉树有2的8次方-1=255个节点
该树的节点个数为255-8=247个。
因为问的是最大有多少个节点，在第7层的叶子节点中还有一个可以有1个子节点，则其不再是叶子节点，它的子节点才是叶子节点，
最大等于247+1=248个

---

没那么复杂，只要记住：完丛团全二叉树的叶子结点数等于树总结点除二就行了。

所以这里最多有124 x 2 = 248 个结点蚂迅。

如果不能整除那就＋1就是叶子结点数。

//若有讲的不恰渗物橘当之处，请评论区留言，谢谢！

---