已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（）。
树转换为的二叉树没有右孩子，就说明在原来的树结构该结点没有右兄弟，也就是说，该节点是其父节点最右边的孩子。 有多少个有孩子的节点，就有多少个“最右的孩子节点”，因此2011-116=1895。 此外，对于根节点而言，它没有父节点当然也没有兄弟，因此也是没有右孩子的。所以+1=1896
---------------------
作者：zhuhuyou4801
来源：CSDN
原文：https://blog.csdn.net/zhuhuyou4801/article/details/76566193
版权声明：本文为博主原创文章，转载请附上博文链接！
---------------------
作者：zhuhuyou4801
来源：CSDN
原文：https://blog.csdn.net/zhuhuyou4801/article/details/76566193
版权声明：本文为博主原创文章，转载请附上博文链接！
发表于 2019-07-25 12:48:29
回复(2)
普通树转换为二叉树后
1.有子结点的结点有且仅有一个无右孩子的子结点
2.根节点无右孩子
所以：
对应二叉树中无右孩子的的结点个数 = 有子节点的的结点数 + 1 = 2011 - 116 + 1 = 1896
发表于 2019-02-15 09:40:00
回复(5)
特殊法，2011个结点，分为1895个中间结点和116个叶结点，按照树转化二叉树选择可以得出无右孩子的结点个数为1895+1=1896。
发表于 2022-07-03 16:12:05
回复(0)
只有度为2的根节点的子节点的左孩子的有有兄弟,因此有右孩子的节点数为116-1=115,无右孩子的为2011-115=1896
发表于 2021-11-07 11:16:45
回复(0)
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数=分支结点数+1=2011-116+ 1=1896。通常本题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子，故无右孩子的结点个数=2011-115=1896。