首页 > 试题广场 > 设森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1
[单选题]

设森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后,且根结点的右子树上有()个结点。

  • n1-1
  • n1
  • n1+n2+n3
  • n2+n3+n4
推荐
选D。考察的是森林转二叉树的步骤过程。
  1. 将森林中的每个树转化成二叉树。
  2. 第一棵二叉树不动,从第二棵二叉树开始,一次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。
森林中的每个树转化成二叉树的过程
  1. 加线。在所有的兄弟结点之间加一条线。
  2. 去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除其他孩子结点之间的连线。
  3. 调整。以树的根结点为轴心,将整个树调节一下(第一个孩子是结点的左孩子,兄弟转过来的孩子是结点的右孩子)

如图所示:森林T节点为4,2,4,3     转化合并形成的二叉树根结点的右子树上有9个节点,代入选项则D正确。


编辑于 2019-08-15 14:25:17 回复(0)
4棵树也是一样的啊~森林中的第一棵树占据了最终二叉树的顶点和左子树,右子树就是n-n1=n2+n3+n4.所以选D。为了赚分而来

发表于 2019-08-14 19:36:04 回复(0)
选D

设森林T中的四棵树分别为T1T2T3和T4,T转换为二叉树Bt,
则Bt的根结点T1根结点,Bt的左子树由T1的子树森林构成,Bt的右子树由T2T3和T4组成。
故Bt的右子树的结点数目即是T2T3、T4三棵树的结点数目之和,即为n2+n3+n4。

发表于 2019-08-14 17:51:45 回复(0)
A
发表于 2019-08-14 15:09:13 回复(0)