已知一棵有2011 个结点的树，其叶结点个数为 116，该树_

可乐妥妥

设度为1的节点有x个，度为0的节点有116个，一共有2011个节点，则度为2的节点有：2011-116-x=1895-x（个）

得到方程式：x+2*（1895-x ）=2011-1

得x=1780个

即度为1的节点有1780个，度为0的节点有116个，度为2的节点有1895-1780=115个。

注意：度为0的节点也是没有右孩子的。答案的意思就是 1780+ 116=1896个。

但是我没明白度为1的节点里有右孩子没有左孩子的怎么办。。。。

发表于 2016-11-29 16:01:27 回复(4)

繁星的夜空2012

这个题吗貌似有问题，指明的树-----它的度难道只能小于等于2吗？

这个题目“该树对应的二叉树”---- 1. 加线

在所有兄弟结点之间加一条连线。

2. 去线

树中的每个结点，只保留它与第一个孩子结点的连线，删除它与其它孩子结点之间的连线。

3. 层次调整

以树的根节点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。（注意第一个孩子是结点的左孩子，兄弟转换过来的孩子是结点的右孩子）

叶子结点数为116 则度为2的结点为116-1=115 则无有孩子结点的个数为2011-115=1896

因为题目写着该树对应的二叉树---好好理解这句话，还有树如何转为二叉树。补充一下知识。就可以解答你的问题。

编辑于 2016-12-28 17:10:43 回复(0)

philian

树——>二叉树，大孩子变左孩子，兄弟变右孩子
因此对应的二叉树没有右孩子，说明该节点在树里右边没有兄弟，也就是说，该节点是其父节点最右边的孩子。有多少个有孩子的节点，就有多少个“最右的孩子节点”，因此2011-116=1895
此外，对于根节点而言，它没有父节点当然也没有兄弟，因此也是没有右孩子的。所以+1=1896

发表于 2016-12-16 18:33:40 回复(8)

左庶长

发表于 2018-01-11 21:59:57 回复(6)

早早安

无右孩子的节点个数=叶子节点数+度为1的节点数=节点总数-度为2的节点数。

叶子节点为116，所以度为2的节点有115.

可以得出：无右孩子的节点个数=2011-115=1896

发表于 2016-11-26 20:55:10 回复(6)

夕一啊

左孩子右兄弟。转换为的二叉树没有右孩子，就说明在原来的树结构该结点没有右兄弟

举几个例子找规律

可知，没有右兄弟的节点数为非叶子节点数加1

原理就如philian说的，有多少个非叶子节点就有多少个最右的孩子，再加上根节点本身，就是没有右兄弟的节点个数

所以这道题非叶子节点数是1895，没有右兄弟的节点数为1896

编辑于 2017-06-28 14:25:32 回复(2)

牛客791903189号

题目分析：树转化为的二叉树中无右孩子的结点个数等价于树中无右兄弟结点的结点个数

求解思路：总结点数=根结点+所有的孩子结点

1.首先，度为1的结点的只有一个孩子结点，所以度为1的结点的孩子结点一定无兄弟结点（⚠️无兄弟结点的是度为1的结点的孩子结点，不是度为1的结点）

2.对于度大于1的结点，一定有超过1个的孩子结点，那么最后一个孩子结点必定没有右兄弟，因此，对于度大于1的结点，有且只有一个孩子结点无右兄弟结点

3.根结点不属于任何一个结点的孩子结点，且其没有兄弟结点

综上，树中无右兄弟结点的结点个数=n-n0

编辑于 2022-10-11 17:05:24 回复(0)

NB响当当

答案怎么得到的我是清楚，但是个人认为这道题是有歧义的，由于题目并未对最后结果做出限制，答案B也是可以推出来的。过程如下：

首先这里提出——二叉树也是树（没歧义吧），因此以下过程直接求解，不需要进行二叉树转化。或者认为二叉树转换成二叉树。

由于有116个叶节点，因此推得在完全二叉树情况下有8层，即第8层拥有叶子节点128个。现去除8层中最右面12个的左孩子，得到116个叶子节点，且这116个叶子节点是无右孩子的。然后这种情况下共有243个节点，缺少2011-243=1768个节点。先创建1768个节点，然后一个接一个接在右孩子位置，得到一颗1768层、拥有1768个度为1的二叉树，然后将上述得到的8层完全二叉树接到这个树的最后一个叶节点的右孩子上。这样，就得到了一颗拥有2011个节点，且拥有116个叶子节点的二叉树，且只有叶子节点没有右孩子。

由于这也是一棵树（除非你说二叉树不是树），就像不能说正方形不是矩形一样（当年高考卷子也是想着法子让你忘记正方形是特殊的矩形）。完全符合题意，然后这个树转化为二叉树后就是它本身。不知道这样看这道题是否有歧义。

发表于 2018-03-20 11:07:17 回复(1)

加油加油加油加油加

我说一下我的做法吧，2011个结点的树对应的二叉树也是2011个结点，n个结点有n+1个空链域。也就是有2012个空链域。二叉树中无右孩子的结点个数，等于右链域为空的个数，那我们现在考虑求出左链域为空的结点个数，等于没有树中没有孩子的结点个数，也就是叶节点的个数=116。因此右孩子为空的=2011+1-116=1896

发表于 2023-10-15 14:29:42 回复(0)

hahaha2333

正确答案看明白了，想知道这个错在哪里了啊，感觉是不是题多少有点问题啊

编辑于 2022-09-12 22:40:45 回复(1)

炒饭君1

这题的关键其实是理解树怎么转化成二叉树

发表于 2022-05-14 17:47:16 回复(0)

ArkiWang

将树看成二叉树，度为1和度为0的节点个数之和即为所求

发表于 2019-11-13 20:04:47 回复(0)

少女的绿箩裙

树转化成二叉树后，无右孩子的结点个数是原树中分支结点的个数+1

发表于 2018-12-05 20:29:27 回复(0)

paprika0826

n0=116，n2=116-1=115，没有右孩子结点，n0+n1=n-n2

发表于 2018-03-30 10:55:58 回复(0)

黏黏糖

树转化为二叉树时，二叉树中无右孩子结点的结点，在原树中，为原父亲结点最右边的孩子。而对于根节点来说，他承担了两个责任。会产生两个无右孩子结点的结点。他有两重身份，一是第二层最右边结点的父亲节点，二是根节点；作为第二层结点的父亲节点，在转化为二叉树时，其最右边孩子满足条件；与此同时，作为根节点，由于原树不是森林，转化为二叉树的根节点作为第二重身份也满足条件。

发表于 2017-05-27 18:06:18 回复(0)

已知一棵有2011 个结点的树，其叶结点个数为 116，该树

问题信息

热门推荐

相关试题