首页 > 试题广场 >

一个完全二叉树有124个叶子节点，则该完全二叉树最多有多少个

[单选题]

一个完全二叉树有124个叶子节点，则该完全二叉树最多有多少个节点？（）

查看正确选项

XLOG

解法一：

（１）二叉树性质

１、总结点数＝度为０结点数＋度为１结点数＋度为２结点数（ｎ＝ｎ0＋ｎ1＋ｎ2）

２、总结点数＝各结点度之和＋１（ｎ＝ｎ0＊0＋ｎ1＊1＋ｎ2＊2＋１）

３、叶子节点数＝度为２的结点数＋１（ｎ0＝ｎ2＋1）

４、已知该完全二叉树叶子节点数为124，即可得完全二叉树ｎ2＝ｎ0－１＝123

（2）完全二叉树性质

１、完全二叉树，大多数结点度非０即２，且度为１结点数有且只有一个

２、深度为ｈ的完全二叉树，１～h－１层必定是满的，且第ｈ层结点集中在左侧

（3）完全二叉树最多结点数ｎ＝ｎ0＋ｎ1＋ｎ2＝124＋１＋123＝248

解法二：

（１）完全二叉树叶子节点数为124个，即可推导出最底层深度为8，且第8层最多可有128个叶子节点（128－124＝4，即最右侧分布4个节点）

（２）此时有两种情况，第一种。上一层最右侧的4个节点都是叶子节点，第二种，最右侧3个叶子节点＋其中一个靠左的叶子节点存在一个左节点

（３）显然第二种情况节点数是最多的，１～７层共127个节点、第8层有121个叶子节点，共127＋121＝248

编辑于 2022-04-24 20:52:29 回复(1)

不想改也得改了

nnd没想到还可以有一个长了一个叶结点的倒数第二层结点

发表于 2023-08-05 11:52:16 回复(0)

呵呵一笑倾家荡产

根节点算不算

发表于 2021-10-10 23:09:54 回复(0)

已注销

全满的情况是128个，现在是124，所以肯定两种情况，一种可能上一层有4个叶子结点，另一种可能上一层3个叶子结点加有一个只有左节点，而他的层数是8，所以最多255 - 3×2 - 1 = 248

发表于 2021-08-05 13:41:40 回复(0)

提交观点

问题信息

测试开发工程师哔哩哔哩 2021

上传者：小小

难度：

4条回答 24收藏 837浏览

扫一扫，把题目装进口袋