下列关于二叉树及森林的叙述中,正确的是?()
A. 完全二叉树不存在度为 1 的结点
B. 任意一个森林可以转换为一棵二叉树
C. 二叉树的分支结点个数比叶结点个数少
D. 链式树的根中保存的是最先计算的运算符
逐一分析各选项如下:
A. ...
用户登录可进行刷题及查看答案
错误。 完全二叉树的定义:除最后一层外,每一层上的结点数均达到最大值,且最后一层上只缺少右边的若干结点。
当完全二叉树的结点数为偶数时,最后一个非叶子结点(即倒数第二层最右边的结点)只有左孩子,度为 1。 例如:结点数为 3 的完全二叉树(根结点 + 左子结点),根结点度为 1。
正确。 森林与二叉树的转换规则基于 “左孩子右兄弟” 表示法:
将森林中的每棵树转换为二叉树(根结点的左子树为原树的子树,右子树为空)。
从第二棵树开始,依次将后一棵二叉树作为前一棵二叉树根结点的右子树。 因此,任意森林均可唯一转换为一棵二叉树,且该过程可逆。
错误。 分支结点指度为 1 或 2 的结点,叶结点指度为 0 的结点。
反例:满二叉树中,叶结点数 = 分支结点数 + 1(如三层满二叉树:叶结点 4 个,分支结点 3 个),此时分支结点数少于叶结点数。
但一般二叉树不满足此关系:例如,单链二叉树(如右斜树)中,分支结点数为 n−1(度为 1),叶结点数为 1,此时分支结点数远多于叶结点数。 因此,该结论仅对满二叉树成立,并非所有二叉树的普遍性质。
错误。 链式树(如表达式树)中,根结点保存的是最终计算的运算符,而非最先计算的运算符。
例如,表达式 (a+b)×c 的表达式树中,根结点为 ×(最后计算),左子树为 +(先计算)。 因此,最先计算的运算符位于子树中,根结点为最终运算符。
结论
正确答案为 B。
登录后提交答案
暂无评论,来抢沙发