设一棵二叉树B是由森林T转换而来的,若T中有n个非叶子结点,则二叉树B中无右孩子的结点个数为______。
A. n-1
B. n
C. n+1
D. n+2
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
树中每个节点的右孩子对应其在原树中的右兄弟(即同父节点的下一个子节点); 森林中各棵树的根节点依次连接,后一棵树的根节点作为前一棵树根节点的右孩子。
因此,二叉树中 “无右孩子的节点” 等价于原森林中 “没有右兄弟” 的节点。 无右孩子节点的来源 非叶子节点的最后一个子节点: 森林中每个非叶子节点(有子节点的节点)有若干个子节点,其中最后一个子节点没有右兄弟(即没有下一个同级子节点),因此在转换后的二叉树中无右孩子。 若森林中有n个非叶子节点,则这部分贡献n个无右孩子的节点。 森林中最后一棵树的根节点: 森林中各棵树的根节点依次作为前一棵树根节点的右孩子,因此最后一棵树的根节点没有右兄弟(没有下一棵树的根节点作为右孩子),在转换后的二叉树中无右孩子。这部分贡献1个无右孩子的节点。
n-1
C
登录后提交答案