我要招人

去企业版

首页 > 试题广场 >

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

[单选题]

已知一棵有 2011 个结点的树，其叶结点个数为 116 ，该树对应的二叉树中无右孩子的结点个数是。

```
115
```
```
116
```
```
1895
```
```
1896
```

查看答案及解析

百里酚蓝

普通树转化为二叉树后，度为1的结点只有左孩子而无右孩子，问题就可转化为求叶子结点（度为0）加上度为1结点的总数，即n0+n1。由二叉树公式：n=n0+n1+n2，且n2=n0-1，所以n0+n1=n-n0+1，即2011-116+1=1896。

发表于 2018-11-12 01:29:44 回复(2)

喵大人喵喵喵

树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数 = 分支结点数 +1=2011 - 116+ 1=1896 。通常本题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数 =2011 - 115=1896 。

发表于 2017-05-17 03:19:16 回复(3)

牛客112

由题可知，叶结点数目115个，即0度点个数115个，根据二叉树性质，2度点数目为115-1=114。二叉树结点总是从左往右展开，所以1度的点只可能是没有右结点类型。可得出2011-115=1896

编辑于 2018-04-24 11:45:52 回复(0)

wcz2023

总结一下。

方法一：

对于树中的每一个分支结点（有孩子的结点，与之对应的是叶子结点），总能找到一个最右端的孩子结点，这个结点转为二叉树后无右孩子（因为它没有右边的兄弟）。所以说树中每一个分支结点总有一个孩子结点转换成二叉树后无右孩子，此外根节点本身转换后也没有右孩子，因此，总数就是：分支结点数+1 = 2011-116+1

方法二：

画一颗奇葩的树（所有叶节点都在一个结点下），数一数。

编辑于 2020-05-01 08:57:40 回复(0)

蜗牛201910032052148

看错了什么忽略了叶子结点也没有右孩子

发表于 2019-10-19 17:40:57 回复(0)

天蓝时代

结合连通图 e=n1+n2+1的性质就可以计算得到结果

发表于 2020-03-11 17:32:17 回复(0)

米奇伤心屋

链接详情:https://blog.csdn.net/qq_33514421/article/details/102774026

发表于 2021-09-15 13:10:20 回复(0)

jfjdjdjs

没有右孩子，就是度为1和度为0的结点个数。就等于总结点个数减去度为2的结点个数。

发表于 2019-09-28 19:02:13 回复(0)

浪子亭

当树中有孩子结点时才能转换为二叉树的左孩子结点右孩子结点树=总结点数-左孩子结点树-根结点无右孩子结点数=总结点数-右孩子结点数

发表于 2018-04-15 14:42:27 回复(3)

天佑lyp

一般肯定满足特殊例子，那么树中7个节点5个叶节点。花个草图就能找到规律了，该树对应的二叉树中无右孩子的结点个数=节点数-叶子节点+1

发表于 2017-07-30 17:55:23 回复(0)

G-matt

剩下的(2011-116=1985[都是父子关系，转成2叉树的时候都在左边])116节点转成2叉树，父节点和叶节点没有没右节点

发表于 2022-11-13 09:49:25 回复(0)

牛客834072161号

公式咋来的？二叉树中无右孩子代表了，兄弟节点中处于最后一个的节点的个数。怎么和叶子节点关联上的。

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

李贵鹏，(°_°)…

采用特殊值法，由树转化而来的二叉树中，没有右孩子，就意味着它在树的形态下没有右兄弟，则可假设这116个叶子结点都在最后一层，也只有前115个有右兄弟，剩下的所有结点都没有右兄弟。2011-115＝1896

发表于 2022-11-19 13:53:42 回复(0)

牛客162818418号

https://www.zhihu.com/question/553107689想知道这个错在哪啊大佬们

发表于 2022-09-12 23:53:37 回复(0)

MnM~

将树转化为二叉树，对每一个分支节点，其类型可概括为以下3种。

我们可以发现，每一种情况下，对于一个分支结点转化为二叉树形式后，都使其子节点最右边没有右结点，即产生一个没有右结点的结点。

分支结点本身必定至少有一个及以上的子节点，所以每个分支结点会产生一个没有右结点的结点。

然后，发现根节点除了其最右端子节点没有右结点外，它本身也没有。

所以，总共没有右结点的结点个数为：分支节点数+1.（注意：根节点也是分支结点）

发表于 2022-04-05 17:18:02 回复(0)

恶寒轻轻

还是用特殊法好理解一些，其他的答案想我不理解，因为树转二叉树除了这个方法（左孩子兄弟法）还有其他的吗？怎么根据树有116个叶子得到对应二叉树也有116个叶子的？

编辑于 2021-11-23 17:23:55 回复(0)

牛客392168958号

作为解析最好不要用特殊值法

证明如下：

由树转二叉树的规则可知想要找到该树中对应的二叉树中无右孩子的结点即要找到该树中所有有孩子的节点的最右侧的孩子

那么可以断言对于该树每一个有孩子的节点该节点的孩子中一定有个最右的孩子并且根节点会贡献两个我们要找的节点原因是根节点有孩子可以贡献一个根节点自己在转为二叉树之后也没有右孩子

所以最后的结论就是该树中对应的二叉树中无右孩子的结点=该树的非叶子节点个数+1

发表于 2021-07-11 19:19:56 回复(0)

BS_W

If we have a tree with M nodes and this tree have N leaf nodes, this tree have M - N + 1 nodes without right child in its corresponding binary tree.

Proof:

In Binary tree, we consider 4 kinds of nodes: With both children (i.e. n₂), with left child but no right child (set as x), with right child but no left child (set as y), without children (i.e., n₀). Based on property of binary tree, n₂= n₀ - 1. So, M can be shown as: M = x + y + 2n₀ - 1;

Because leaf nodes in the tree will have no left child in corresponding binary tree. So, y + n₀= N; While, the number of nodes without right child in its corresponding binary tree is: x + n₀; Thus, the answer is: x + n₀= M - (y + n₀) + 1 = M - N + 1.

发表于 2019-06-30 07:47:15 回复(1)

重威

已知叶子节点的个数为116，则度为2的节点的个数为116-1=115的个数为，那么度不是二的就是没有有孩子的节点个数2011-115=1896

编辑于 2019-06-12 10:39:14 回复(0)

提交观点

问题信息

树

上传者：喵大人喵喵喵

难度：

19条回答 568收藏 6045浏览

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

问题信息

热门推荐

相关试题