设结点x和y是二叉树中任意的两个结点,在该二叉树的先根遍历序列中x在y之前,而在其后根遍历序列中x在y之后,则x和y的关系是(51)。

admin2009-02-15  27

问题 设结点x和y是二叉树中任意的两个结点,在该二叉树的先根遍历序列中x在y之前,而在其后根遍历序列中x在y之后,则x和y的关系是(51)。

选项 A、x是y的左兄弟
B、x是y的右兄弟
C、x是y的祖先
D、x是y的后裔

答案C

解析 二叉树的遍历方法主要有以下3种。(1) 前序遍历(先根遍历,先序遍历):首先访问根结点,然后按前序遍历根结点的左子树,再按前序遍历根结点的右子树。(2) 中序遍历(中根遍历):首先按中序遍历根结点的左子树,然后访问根结点,再按中序遍历根结点的右子树。(3) 后序遍历(后根遍历,后序遍历):首先按后序遍历根结点的左子树,然后按后序遍历根结点的右子树,再访问根结点。已知在该二叉树的先根遍历序列中,x在y之前,则说明x可能是y的父结点(祖先),或是y的父结点的左子树里的某个结点。又知在其后根遍历序列中,x在y之后,则说明x可能是y的父结点或是y的父结点的右子树里的某个结点。因此,x只能是y的父结点。
转载请注明原文地址:https://kaotiyun.com/show/jCxZ777K
0

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