要使一颗非空二叉树的先序序列与中序序列相同,其所有非叶节点须满足的条件是()
A.只有左子树
B.只有右子树
C.结点的度均为1
D.结点的度均为2
方法一:取交集
前序遍历为&...
用户登录可进行刷题及查看答案
前序遍历为“根左右”,中序遍历为“左根右”,非空二叉树的先序序列与中序序列相同,取交集,都为“根右”,所以只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。
本题选B。
方法二:构造二叉树
这里第一步先构造二叉树,本人拓展一下给出以下结论:
已知二叉树的前序遍历序列与中序遍历序列相同。我们可以构造出二叉树。
前序遍历序列和中序遍历序列均为a, b, c。
所有非叶结点只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。
登录后提交答案
暂无评论,来抢沙发