2. 考研
  3. 设一棵二叉树是由森林转换而来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点个数为( )。

设一棵二叉树是由森林转换而来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点个数为( )。

admin2019-12-10  117
问题 设一棵二叉树是由森林转换而来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点个数为(    )。
选项 A、n—1
B、n
C、n+1
D、n+2
答案C
解析 首先，对于一棵树来讲，每个非终端结点（除了树的根结点）转换成二叉树后都对应一个无右孩子的结点，因为一个非终端结点至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子。为什么要除去根结点？因为根结点比较特殊，树转换成二叉树之后，根结点本身也将会没有右孩子。所以对于一棵具有n个非终端结点的树来讲，将其转换成二叉树之后，二叉树中无右孩子的结点个数为n+1个。其实，此时已经可以选出答案了，因为一棵树也可以算是一个森林。
如果一个森林有多棵树（假设有x棵），我们先把所有树的根结点拿出来。除根结点之外的非终端结点（n—x个）转换成二叉树之后都是对应一个无右孩子的结点，可得到n—x个无右孩子的结点。但是，x个根结点是不是就对应2x个无右孩子的结点？显然不是，因为下一棵数将会成为上一棵树根结点的右孩子（见图5—3），所以只有森林的最后一棵树的根结点才会变成无右孩子的结点，故x个根结点将会得到x+1个无右孩子的根结点，所以一共可以得到n—x+(x+1)=n+1个无右孩子的根结点。

从图5—3可以看出，三棵树的根结点A、E、G转换成二叉树之后，只有最后一棵树的根结点G是没有右孩子的。
综上分析，二叉树中无右孩子的结点个数为n+1个，故选C选项。
解题技巧：使用特殊值代入法，如图5—4所示。

可以从图5—4中很直观地看出无右孩子结点比非终端结点多1。
补充例题：设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是(    )。
A．m—n
B．m—n—1
C. n+1
D．条件不足，无法确定
解析：由转换规则可知，二叉树中除了左子树和根结点来源于原森林中第一棵树，其余结点来源于森林中的其他树，其他树的结点总数为n，则第一棵树的结点个数为m—n，故选A选项。
转载请注明原文地址:https://kaotiyun.com/show/uG3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)