🏷️ 知识点：Ds.05.03.02
引入线索二叉树的目的是（ ）。
A. 加快查找结点的前驱或后继速度 B. 方便插入和删除 C. 方便找到双亲 D. 使遍历结果唯一
[tag_link]
正确答案：A
结论
利用空指针域保存前驱/后继线索。
推导
利用空指针域保存前驱/后继线索。
易错点
把线索当作双亲指针
n个结点的线索二叉树上含有的线索数为（ ）。
A. 2n B. n-1 C. n+1 D. n
[tag_link]
正确答案：C
结论
2n指针域减去n-1孩子指针，余n+1条线索。
推导
2n指针域减去n-1孩子指针，余n+1条线索。
易错点
漏算根结点空指针
判断线索二叉树中*p结点有右孩子结点的条件是（ ）。右孩子条件由p->rtag==0标识。
A. p!=NULL B. p->rchild!=NULL C. p->rtag==0 D. p->rtag==1
[tag_link]
correct answer: C
结论
rtag=0表示右指针为真实右孩子，rtag=1表示右线索。
推导
先读标志位而不是只看指针值：rtag=0时rchild保存孩子地址，rtag=1时rchild保存后继线索。因此判定有右孩子必须检查rtag==0。
易错点
不要把非空右指针与真实孩子混同。
一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是（ ）。
A. 不确定 B. 0个 C. 1个 D. 2个
[tag_link]
correct answer: D
结论
根的左域无先驱而为空，先序最后叶的右域无后继而为空，共2个。
推导
先序序列的首结点没有先驱，树的左子树又为空，所以根的左域无法填线索；先序末结点没有后继，其右域也无法填线索。因此还剩2个空链域。
易错点
线索只填可确定的前驱/后继。
在线索二叉树中，下列说法不正确的是（ ）。
A. 中序线索树中有右孩子时后继为右子树最左下结点 B. 中序线索树中有左孩子时前驱为左子树最右下结点 C. 线索二叉树利用n+1个空指针存放前驱和后继信息 D. 每个结点通过线索都可直接找到前驱和后继
[tag_link]
correct answer: D
结论
先序前驱或后序后继通常需要双亲信息，D错误。
推导
逐项检查可知，中序前驱和后继可沿孩子或线索取得，且n个结点确有n+1个空指针域可线索化；但先序前驱、后序后继等方向可能需要回到双亲，普通线索结构不能保证直接取得。
易错点
线索不保证所有方向均可直接访问。
二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继
[tag_link]
correct answer: D
结论
标准二叉线索无双亲指针，后序后继需回溯双亲。
推导
后序次序是左、右、根。访问完某结点后，可能要回到双亲，再判断兄弟子树或双亲本身；标准二叉链表没有双亲指针，所以后序后继不能总在常数步内求出。
易错点
后序前驱可由线索，后继不可。
若X是二叉中序线索树中一个有左孩子且X不为根的结点，则X的前驱为（ ）。
A. X的双亲 B. X的右子树中最左的结点 C. X的左子树中最右的结点 D. X的左子树中最右的叶结点
[tag_link]
correct answer: C
结论
中序LNR，X前驱是左子树中最右结点，不必为叶。
推导
中序次序是左、根、右。X有左孩子时，X之前最后访问的必是左子树中沿右链到达的最右结点；该结点可以仍有左孩子，所以不能额外限定为叶结点。
易错点
不要额外限定为最右叶。
若X是后序线索二叉树中的叶结点，且X存在左兄弟Y，则X的右线索指向（ ）。
A. X的双亲 B. 以Y为根的子树的最左下结点 C. X的左兄弟Y D. 以Y为根的子树的最右下结点
[tag_link]
correct answer: A
结论
后序LRN中叶X之后访问其双亲，右线索指向双亲。
推导
X有左兄弟Y，说明后序遍历先完成Y子树，再访问作为右孩子的叶X，随后访问二者的双亲。因此X的后序后继就是双亲，右线索应指向双亲。
易错点
后序后继不是左兄弟子树。