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

推荐

dragonaxz

网上看到的解法：

转换出来的二叉树中，一共有2011*2个链域，其中左右链域各2011个。

设非空的左链域有XL个，非空的右链域有XR个，那么XL+XR+1=2011（总节点数为根节点加左右孩子数）

且因为二叉树是由树转化而来，因此节点在树中至少要有一个孩子才能在转化为二叉树后有左孩子（也就是非叶节点），也就是说有2011-116个节点在二叉树中有左孩子，因此XL=2011-116，代入上式可得2011-116+XR+1=2011，因此XR=115。

由此，空的右链域=2011(右链域数)-XR=1896个，得解

编辑于 2017-03-04 15:34:30 回复(12)

你的奥利奥

耍个小聪明，我们假设这棵树是没有右子树的线性链，则这棵树的叶子结点为1，度为1的结点数为2010，这时该树对应的二叉树无右孩子的结点个数为2011。我们发现如果叶子结点每加1，对应的无右孩子的结点数就减1。那么，要满足题目要求，叶子结点数就需要加上115才能等于116，因此对应的无右孩子的结点数就为2011-115=1896。

发表于 2017-07-28 23:34:26 回复(2)

luuuyi

无右孩子包含度为0和1的节点

发表于 2016-12-08 11:22:06 回复(3)

htdwade

可以用分支的观点做。树中每一个分支结点的最右孩子在转化为二叉树后右链域为空，加上根结点转化后也无右孩子，所以二叉树中无右孩子的结点树＝原树中的分支结点数+1

发表于 2017-08-08 19:35:49 回复(0)

褪涩

如果你幸运翻到了我这一片评论，那么你因该会弄懂为什么：求分支节点，从而解出答案

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

发表于 2019-09-03 13:43:12 回复(1)

沙雕青年

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

发表于 2016-12-03 17:09:52 回复(3)

迷糊Tao

树转换为二叉树时，树中每一个分支节点的左右节点中的最右子节点没有右孩子，每一个分支节点都有一个最右的右孩子，根节点也没有右孩子，所以 N = 分支节点数 + 1 = 总节点数 - 叶子节点数 + 1

发表于 2018-06-25 21:50:46 回复(0)

wenhaiz

树对应的二叉树中无右孩子的结点的数目等于原来的树中度为1和度为0的结点之和。

设树中度为2的结点数为n2,度为1的结点数为n1，叶子结点为n0，

则n2+n1+n0=2011;

树的分支数为2*n2+n1=2011-1=2010;

有上式可求得n1 = 1780;

所以答案为n1+n0 = 1780+116=1896.

发表于 2017-04-19 19:49:26 回复(2)

Linkang

网上看到的，目前看到最简单一个理解方法。采用特值法（最后的116个叶子结点的父结点相同，父结点以上的结点都是单结点共1895个单结点，所以转换成二叉树后，从116个叶子结点中多了一个没有右结点的（最后那个），共1895+1=1896） http://blog.csdn.net/u011240016/article/details/53215374

编辑于 2017-04-06 18:02:50 回复(0)

美团到店招聘

树转成二叉树的时候，只要父节点有超过一个孩子，则在转成二叉树的时候，肯定存在右孩子。所以只能包含度为0和度为1的点。

发表于 2017-03-20 20:31:54 回复(0)

zelinx

非叶节点的个数为1895，由原来的树转换为二叉树的过程中，每个非叶节点的儿子节点们都会形成1个空的右指针，因此现在有1895个空的右指针，根是一个特殊的非叶节点，他自己形成一个空的右指针，1895+1=1896！！！！

发表于 2020-07-02 18:12:15 回复(0)

侯卿

简单方法:没有右兄弟转换后就是没有右孩子。而每个非叶子节点都对应着唯一一个没有右兄弟的孩子:2011-116。最后再加上根节点自己也是一个没右兄弟的。所以最后的就是2011-116+1

发表于 2018-03-31 16:37:30 回复(1)

destory27

树中有孩子结点才能转换为二叉树的左孩子结点（2011-116）。右孩子结点 = 2011 - 左孩子结点 - 根结点无右孩子结点 = 2011 - 右孩子结点

发表于 2018-01-17 17:28:40 回复(0)

繁星的夜空2012

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

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

2. 去线

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

3. 层次调整

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

发表于 2016-12-25 20:19:16 回复(0)

cbox

相当于求原来的树上没有右兄弟的孩子的个数，也就是相当于非叶子节点的个数（每一个非页节点都有且只有一个儿子没有右兄弟），加上根节点即可。

发表于 2018-04-25 16:34:25 回复(0)

奔腾的小马达

无右孩子的结点即那些叶子结点和度为1的结点，叶子结点已知是116，因为度为2的结点比叶子结点少一个，所以是115个，整个二叉树由叶子结点（2011） = 度为1的结点 + 叶子结点（116） + 度为2的结点（115）。无右孩子的结点 = 叶子结点 + 度为1的结点 = 116 + 度为1的结点 = 116 + 2011 - 116 - 115 = 2011 - 115 = 1896

发表于 2019-05-15 16:18:17 回复(0)

守望麦田

感觉这道题问题中“二叉树无右孩子的结点个数”这句话按含的意思是度为1的结点都是左孩子，不然没法解。在此基础上，二叉树无右孩子的结点个数为n0+n1，n0表示叶节点，n1表示只有左孩子，n=n0+n1+n2，n2=n0-1，所以n0+n1=n-n0+1=1896，n表示结点总数，n2表示左右孩子都有的结点数。

发表于 2018-06-25 20:35:34 回复(0)

快说我这信号好

网上看到的解法：转换出来的二叉树中，一共有2011*2个链域，其中左右链域各2011个。设非空的左链域有XL个，非空的右链域有XR个，那么XL+XR+1=2011（总节点数为根节点加左右孩子数）且因为二叉树是由树转化而来，因此节点在树中至少要有一个孩子才能在转化为二叉树后有左孩子（也就是非叶节点），也就是说有2011-116个节点在二叉树中有左孩子，因此XL=2011-116，代入上式可得2011-116+XR+1=2011，因此XR=115。由此，空的右链域=2011(右链域数)-XR=1896个，得解

发表于 2018-05-08 18:33:25 回复(0)