题1

题1

题目

Q:在下列关于二叉树遍历的说法中, 正确的是 ( ).
A. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点, 则它一定是该子树的前序遍历结果序列的最后一个结点
B. 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点, 则它一定是该子树的中序遍历结果序列的最后一个结点
C. 若有一个叶结点是二叉树中某个子树的中序遍历结果序列的最后一个结点, 则它一定是该子树的前序遍历结果序列的最后一个结点
D. 若有一个叶结点是二叉树中某个子树的前序遍历结果序列的最后一个结点, 则它一定是该子树的中序遍历结果序列的最后一个结点

分析

A:中序遍历把二叉树分成了两个部分，左侧是左子树的待遍历串，右侧是右子树的待遍历串，因为递归，每个子串都是左根右这么执行

而前序遍历是根左右这么执行，两个都是以右结尾，所以如果这个右是叶子结点，也一定是同一个执行到最后的元素
而必须是通过中序才能确定先序，因为中序才能把左右子树的长度确定

解

C
二叉树中序遍历的最后一个结点一定是从根开始沿右子女指针链走到底的结点,设用 指示。
若结点 不是叶结点 (其左子树非空),则前序遍历的最后一个结点在它的左子树中,A、B 错误;
若结点 是叶结点,则前序与中序遍历的最后一个结点就是它, 正确。
若中序遍历的最后一个结点 不是叶结点,它还有一个左子女 ,结点 是叶结点,那么结点 是前序遍历的最后一个结点, 但不是中序遍历的最后一个结点, D 错误。