题3 题目 设 为一棵二又树上的两个结点,在中序遍历时, 在 前的条件是 ( ). A. 在 右方 B. 是 祖先 C. 在 左方 D. 是 子孙 分析 中序遍历的顺序是左根右 n在前面，那肯定得是n在左边 解 C 中序遍历时,先访问左子树,再访问根结点,后访问右子树。 在 前的 3 种可能性如下图所示,从中看出 总是在 的左方。 【另解】设 和 的最近公共祖先 ,则有以下可能: 情形 和 分别在 的左、右 (右、左) 分支上; 情形 或 为 结点,另一结点在 的分支上。只有 和 分别处于 的左、右分支上, 为祖先结点且 位于 的左分支, 为祖先结点且 位于 的右分支,符合题意。
