首页 > 试题广场 >

将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v

[单选题]
将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，
则在原来的森林中，u 和 v 可能具有的关系是 （         ）
I．父子关系  II.兄弟关系  III. u 的父结点与 v 的父结点是兄弟关系 
  • 只有 II
  • I 和 II
  • I 和 III
  • I、II 和 III
查看正确选项
添加回答
sgbs头像 sgbs
有谁可以给解释下？？
发表于 2017-06-14 08:31:41 回复(1)
牛客170147894号头像 牛客170147894号
有没有大佬可以解释一下，这样为什么ⅲ不对啊，题目里并没有限制u的父结点是根节点啊？真的晕咯。
发表于 2021-11-15 18:23:02 回复(2)
菲尼克斯弗兰克头像 菲尼克斯弗兰克
rt
发表于 2018-11-07 16:56:45 回复(0)
喜欢吃米饭头像 喜欢吃米饭
关于第三个选项，其实，主要的问题还是在于审题。

发表于 2019-12-07 17:15:27 回复(4)
破天荒x头像 破天荒x
第三个说的是在森林当中u的父节点和v的父节点是兄弟关系，而不是说在二叉树中u的父节点和v的父节点是森林关系
发表于 2018-12-06 21:50:26 回复(0)
孙健-字节跳动头像 孙健-字节跳动
发表于 2017-06-18 11:44:10 回复(9)
virtualx头像 virtualx
不是二叉树中的父节点是原来森林中的父节点所以3不对
发表于 2020-11-19 17:02:03 回复(1)
遇见不相见头像 遇见不相见
发表于 2018-12-17 21:55:19 回复(0)
编程的渣渣啊啊啊头像 编程的渣渣啊啊啊
为什么我觉得是D
发表于 2017-09-04 10:47:40 回复(0)
牛客736456724号头像 牛客736456724号
D选项就是这样说，则在原来的森林中，u的父节点与v的父节点是兄弟关系如图所示，但是这些情况都不能得到“若在二叉树中，结点u是结点v的父节点的父节点”的这一原假设，和题目矛盾了
发表于 2022-09-24 17:11:46 回复(0)
小超同学头像 小超同学
发表于 2020-07-20 17:17:32 回复(2)
丶201809271148851头像 丶201809271148851

发表于 2018-11-20 16:40:49 回复(2)
🍉Mr.Lew头像 🍉Mr.Lew
手滑了
发表于 2018-10-29 20:58:21 回复(0)
mmm_mmm头像 mmm_mmm
森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。树转化为对应二叉树的方法为:孩子兄弟表示法,除左节点外,依次序,将其他节点作为自己的右孩子.
将森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
综上,若在二叉树中，结点 u 是结点 v 的父结点的父结点,分两种情况,转化前,u,v是否在同一棵树上,若在,1,2选项有可能;若不在,那么u,v父节点没有直接联系.
编辑于 2018-08-20 19:54:04 回复(0)
Frank_Sherry头像 Frank_Sherry
分析后可以知道，u和v准确的应该有三种关系：
1）父子关系
2）兄弟关系
3）没有关系（两个结点分属于不同的树中）
根据上述的答案，应该选择1和2
发表于 2018-07-07 14:50:32 回复(0)
坚持编程头像 坚持编程
III不对么？我觉得也是对的
发表于 2018-03-18 15:11:03 回复(5)
凌梦初辰头像 凌梦初辰
u节点可以是和V节点的父节点是兄弟关系

但是第三种达不到那种关系
发表于 2017-09-06 09:39:47 回复(0)
牛客3948586号头像 牛客3948586号
整个的转化过程应该是：森林中的树—>森林中的二叉树—>合并成一个二叉树。关键点应该是把森林中的树转化为二叉树的过程，第三种情形下的u和v已经不再是题设的结构了。具体可以参考一下这个人写的博客http://www.cnblogs.com/zhuyf87/archive/2012/11/04/2753950.html
发表于 2017-08-19 12:21:59 回复(0)
爱豆儿头像 爱豆儿
基本原理是树的孩子兄弟表示法。
我们可以采用如下方法进行转化。
步骤：
①将树中结点的所有兄弟结点用水平线连接起来；
②除保留当前结点同其最左子结点的连接之外，将所有同其余子结点的连接线全部删除；同时将当前结点同其最左子结点的连接线修改为垂直连接；
③将得到的图形顺时针旋转45度，即得二叉树。(或将当前纸面逆时针旋转45度，即得)：将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，
只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依次转换。
转化步骤为：
①将森林中所有的树都转化为二叉树；
②第一棵树T1的根结点作为T的根结点，T1的根结点的子树转化为T的左子树，森林的其它树T2，T3，…Tn转化为T的右子树。
发表于 2017-08-09 14:46:24 回复(0)
提交观点

问题信息

树
上传者：阿奻_
难度：
19条回答 18857浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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