题29

题29

题目

Q:若 是二叉中序线索树中一个有左孩子的结点,且 不为根,则 的前驱为 ( ).
A. 的双亲
B. 的右子树中最左的结点
C. 的左子树中最右的结点
D. 的左子树中最右的叶结点

分析

A:中序访问的顺序是左根右
会先去左边，然后一路往左子树深处搜
搜到底部了，回退到底部的左子树的根，再到右子树，再从右子树往上回退
这里的前驱是指，访问顺序上的逻辑关系



或许应该这么说，中序遍历会先把左子树遍历完，而在遍历左子树的时候，依然遵循的是先把更小的左子树遍历完的规则，每一个更小的左子树都是最右边的结点最后访问，然后再回退到它的上级的大一级的子树的根节点中

解

C
在二叉中序线索树中, 某结点若有左孩子, 则按照中序 “左根右” 的顺序, 该结点的前驱结点为左子树中最右的一个结点 (注意, 并不一定是最右叶结点)。