首页 > 试题广场 >

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

[单选题]
将森林转换为对应的二叉树，若在二叉树结点中，结点m是结点n的双亲结点的双亲结点，则在原来的森林中，m和n可能具有的关系是____。
1.父子关系
2.m的双亲结点与n的双亲结点是兄弟关系
3.兄弟关系 
  • 只有3
  • 1和3
  • 1和2
  • 1、2和3
  • 只有1
  • 只有2
查看答案及解析
添加回答
慧眼识金头像 慧眼识金
若红色圆为m，绿色圆为n,那么m的双亲结点与n的双亲结点是兄弟关系，对不对？
发表于 2016-03-26 20:22:24 回复(3)
小杨vita头像 小杨vita
m的双亲结点与n的双亲结点是兄弟关系
这个不对吧？
发表于 2015-08-27 03:17:32 回复(2)
风_N++头像 风_N++
只能是1、3，2是不可能的，这道题在2009年计算机专业统考题中出现过：

编辑于 2016-08-30 10:41:59 回复(6)
Zsea头像 Zsea
编辑于 2017-03-31 18:26:35 回复(7)
月光传说头像 月光传说
结点m是结点n的双亲结点的双亲结点有4种情况
 1)  m         2)m       3)m        4)m
      /              /              \              \
    /                \              /                \
  n                  n         n                   n
爷爷           父子      叔侄(关系2)   兄弟
编辑于 2015-09-03 18:59:03 回复(7)
心海盗梦头像 心海盗梦
要注意问的是在原来的森林中。m的双亲节点和n的双亲节点是兄弟是不可能的。
要是在二叉树中，m的双亲结点与n的双亲结点是兄弟关系是可能的。
发表于 2017-04-27 15:07:50 回复(0)
萱萱是个好姑娘头像 萱萱是个好姑娘
我觉得选项2也是正确的诶
发表于 2016-07-20 16:20:28 回复(0)
。为你而战头像 。为你而战
普通树转换为二叉树的方法是：（http://blog.csdn.net/zm1_1zm/article/details/77222460）

①树中所有相同双亲结点的兄弟节点之间加一条连线

②对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线

③整理所有保留和添加的的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置：

整个转换过程如下图从左到右所示

发表于 2017-08-16 10:02:45 回复(2)
xiao_lai头像 xiao_lai
个人觉得1，2，3都有可能。答案为什么没有2
发表于 2016-07-21 14:52:17 回复(0)
救赎i_头像 救赎i_
发表于 2022-07-20 20:43:25 回复(0)
晴平乐头像 晴平乐

树转换为二叉树

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

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

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

                       

森林转换为二叉树

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

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

 

二叉树转换为树

是树转换为二叉树的逆过程。

（1）加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。

（2）去线。删除原二叉树中所有结点与其右孩子结点的连线。

（3）层次调整。

 

二叉树转换为森林

假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。

（1）从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。

（2）将每棵分离后的二叉树转换为树。

 

发表于 2017-09-10 17:37:52 回复(0)
米兰的小铁匠114头像 米兰的小铁匠114
发表于 2016-07-29 17:08:06 回复(2)
JAVA开发区头像 JAVA开发区
2 的反例
发表于 2023-04-13 13:07:19 回复(0)
Phoenixcwx头像 Phoenixcwx
关于情况二我举出了一个例子，不知道怎么解释，始终想不明白，求解答
这里的m父节点 ，m， n的父节点，都是兄弟，甚至n也有可能是他们的兄弟
编辑于 2015-10-07 19:14:38 回复(5)
StrongYoung头像 StrongYoung
根据左孩子，右兄弟，可以得到：
1）对于情况1：当结点m的第二个孩子为n时，转换成二叉树后，m就成了n的双亲的双亲
2）对于情况3：当结点m是R的第i个孩子，n是R的第i+2个孩子，即m与n中间隔了一个兄弟，这个时候，转换成二叉树后，m就成了n的双亲的双亲
发表于 2015-09-30 22:45:33 回复(0)
茴香小包子头像 茴香小包子
选项2 “m的双亲结点与n的双亲结点是兄弟关系”可以改成“m与n的双亲结点是兄弟关系”
发表于 2021-09-15 21:19:43 回复(0)
王者峰范头像 王者峰范
普通的树转换为二叉树，可以用孩子兄弟表示法等价，这时候的二叉树左右指针一个指孩子另一个是兄弟，但是在二叉树看来两个都是孩子，即某节点的父亲可以是该节点的父亲，也可以是兄弟。本题是父亲的父亲，一共四种可能: 1.祖宗（爷爷） 2.叔侄（爸爸的兄弟） 3.爸爸（兄弟的爸爸，就是你爸爸） 4.兄弟（兄弟的兄弟，还是你兄弟）
发表于 2019-10-10 14:33:03 回复(0)
zurp头像 zurp
理解错了，最后说的是在原来的森林中，对于2而言，在二叉树中n的双亲转换过来就是森林中n的兄弟或者双亲，2表述成二叉树中m的双亲节点与n的双亲节点是兄弟关系就可选了
发表于 2018-04-07 10:02:25 回复(0)
aajzhengzong头像 aajzhengzong
注意是在原来的森林中。三不可能
发表于 2017-03-01 12:30:40 回复(0)
huangqinjian头像 huangqinjian

详情可戳： http://blog.csdn.net/sinat_35512245/article/details/54889818

发表于 2017-02-06 09:35:27 回复(0)
提交观点

问题信息

树
来自：阿里巴巴2016研发工...
难度：
27条回答 16526浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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