首页 > 试题广场 >

设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子

[单选题]
设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（） 
  • m - n
  • m - n - 1
  • n + 1
  • 条件不足，无法确定
查看正确选项
添加回答
Neway头像 Neway

按照这个计算 不应该是 按照图中 的来说 m = 9 , n = 0，貌似没有答案？




发表于 2015-11-17 23:03:57 回复(3)
牛客646077号头像 牛客646077号
第一颗树就是二叉树的的左子树加根节点，左孩子右兄弟
发表于 2015-08-19 20:55:55 回复(2)
BambooWorld头像 BambooWorld
@劲 正解
编辑于 2016-02-24 17:16:23 回复(1)
牛客207398号头像 牛客207398号
选A
森林转二叉树的过程是这样的：

（1）把每棵树转换为二叉树。

（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。

所以转换后的二叉树的左子树节点的个数加根节点的个数就是第一棵树的节点个数，即二叉树总节点个数m减去根节点右子树节点个数n。
发表于 2016-09-15 11:12:32 回复(0)
Rootlee头像 Rootlee
树转二叉树步骤：
1.加线，所有兄弟节点之间加线。
2.抹线，对于所有节点，除了与左孩子节点之间的线，抹掉其他线。
3.旋转。

森林转二叉树：
1.森林中每棵树转成二叉树（每个二叉树根节点都没有右孩子）
2.后一个二叉树的根节点变成第一个二叉树根节点的右孩子，以此类推。

所以本题答案为m-n
发表于 2017-08-21 13:44:53 回复(0)
sunlight_run头像 sunlight_run
森林中第一棵树就是二叉树的根节点+左子树
发表于 2017-06-29 16:49:48 回复(0)
Beasly头像 Beasly
二叉树的结点数为m，则在计算第一棵树的结点数时，不需要+1
发表于 2022-03-14 20:47:18 回复(0)
你永远得不到的祖奶奶头像 你永远得不到的祖奶奶
所有节点数减去右兄弟，剩下的就是第一棵树。
发表于 2020-06-23 09:47:56 回复(0)
Fan24头像 Fan24
森林的总结点数=第一棵树结点数+转化为二叉树的根节点的右子树结点数。
画个图就很容易理解了
发表于 2020-06-09 09:50:07 回复(0)
谱乐头像 谱乐
平衡二叉树
发表于 2018-05-07 08:35:37 回复(0)
牛客348577号头像 牛客348577号
m-n
发表于 2016-09-15 11:22:14 回复(0)
食堂的饺子头像 食堂的饺子
注意树转二叉树和森林转二叉树的不同！
发表于 2016-07-20 11:01:54 回复(0)
huixieqingchun头像 huixieqingchun
注意森林与二叉树的转换方法。
发表于 2016-05-08 13:37:03 回复(0)
提交观点

问题信息

树
难度：
13条回答 30750浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号