首页 > 试题广场 >

高度为h(h0)的满二叉树对应的森林由()棵树构成

[单选题]
高度为h(h>0)的满二叉树对应的森林由()棵树构成 
  • 1
  • log2h
  • h/2
  • h
查看正确选项
添加回答
chaoLegend头像 chaoLegend
二叉树转换成森林中树的个数，与该树根节点一直往右遍历到叶子节点的节点数相同。h高的完全二叉树最右可能有h或h-1个节点。而高度为h的满二叉树对应的森林所含的树的个数一定是h，故树的数量为h。
编辑于 2015-08-30 18:33:39 回复(0)
光明顶头像 光明顶
当只把它当作一道选择题做时，我是直接取特殊值h=2，转换为森林时，此时一个右孩子，所以两棵树组成，得D

发表于 2016-10-24 21:03:10 回复(0)
free斩头像 free斩

选D
发表于 2015-01-07 02:30:06 回复(0)
sunlight_run头像 sunlight_run
解析：二叉树转森林过程：1.从根节点开始，如果有右节点，则将根节点与由孩子连线删除。2.再依次对分离后的二叉树进行1中操作
明显：当二叉树为满二叉树时，森林中树的个数与高度相等
但是，当二叉树不是满二叉树，如缺了A，则此时森林中树的个数为2，而高度为3，就错了
发表于 2017-06-29 09:58:28 回复(0)
Lamuda头像 Lamuda
左孩子，右兄弟。高度为h，说明他有h层，右子树的右子树的右子树……有h层，所以，选D
发表于 2019-05-10 15:29:42 回复(0)
梦境迷离头像 梦境迷离
h=2时 log以2为底 log2^2 与h=2相等。 特殊值不行，除非再多弄一个值且大于2
编辑于 2018-02-12 12:33:32 回复(0)
黏黏糖头像 黏黏糖
森林与二叉树的转换是使用左孩子右兄弟法，那么有多少个兄弟就会有多少棵树。二叉树每延伸一层，说明该节点多了一个兄弟，即多了一棵树。故答案为D：h
发表于 2017-05-08 15:16:17 回复(0)
xingshanxie头像 xingshanxie
原来森林是断开右节点和父节点的链接
发表于 2017-03-04 20:57:17 回复(0)
huixieqingchun头像 huixieqingchun
此题要注意，是满二叉树，还要熟悉森林与二叉树的转换。
发表于 2016-05-11 14:54:43 回复(0)
revivedSuN头像 revivedSuN
孩子兄弟表示法转
发表于 2015-10-21 23:58:57 回复(0)
提交观点

问题信息

树
难度：
10条回答 9399浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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