定叶结点,求结点数

2020146224黄子明
  • 1
新手上路,请多包涵

求叶结点为121的完全二叉树的结点个数。我求的是248,但是不对,答案就没有这个选项。我的思路是,树深度为7,把第六层结点分为三类,一类x,子结点为2;二类为y,子结点为1;三类z,子结点为0;设方程2x+y+z=121;x+y+z=64;总结点数为127+2x+y=248-z,取z为0,总结点数为248,我想知道我哪错了?

回复
阅读 639
2 个回答

深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

按你的思路,解得 x = 57,那么 y + z = 7。
根据完全二叉树的性质,子结点为1的节点y只能为1或者0。

若 y = 1,最后一层的叶子节点数为2*57+1=115,节点数为 255-(128-115)=242。

若 y = 0,最后一层的叶子节点为 2*57=114,节点数为 255-(128-114)=241。

一棵完全二叉树,叶节点为121,那么倒数第二层的节点数应该是小于等于121的2^n的最大值,也就是64,此时n=6,整棵树的深度应该是7

再看你列的方程,x是子节点为2的节点数,没有问题
y是子节点为1的节点数,你想想,y是不是只有可能取0或者1?y的取值对叶节点数有影响吗?没有(给一个叶节点加上一个叶节点,这棵树的叶节点数量是不变的),那可以直接取个0,好算
那z也不需要,z就是2^n-x,这道题就是64-x

那这个方程式就简单多了,就是2x+(64-x)=121,x=57,y可能是0或者1

总结点数就是127+57*2+0/1 = 241或242

宣传栏