线索二叉树是一种（）结构。

正确答案：A

参考答案：D

参考答案：n+1

正确答案：B
解析：非空先序线索二叉树有1或2个空指针，如图13-39所示。

易知，先序序列的最后一个结点一定是叶子结点，该结点无后继，于是其右指针为空。先序序列的第一个结点一定是根结点，其无前驱，若根结点无左子树，显然其左指针为空，同时注意到，第一个结点的右指针、最后一个结点的左指针以及夹在第一个结点(根结点)和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索，均非空，于是该树中共有2个空指针；若根结点有左子树，那么根结点的左指针指向其左子树，同时也注意到，第一个结点(根结点)的右指针、最后一个结点的左指针以及夹在第一个结点和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索，均非空，于是该树中便只有一个非空指针。因此①错误。易知，任一非空中序线索二叉树中，中序遍历的第一个结点肯定是左子树为空的结点，它无前驱，其左指针为空；最后一个结点肯定是右子树为空的结点，它无后继，其右指针为空；第一个结点的右指针、最后一个结点的左指针以及夹在第一个结点和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索，均非空。因此，空指针一定是2个。因此②准确。非空后序线索二叉树有1或2个空指针(如图13—40所示)。

其推理论证类似于非空先序线索二叉树，在此不再赘述。因此③不准确。

正确答案：B

参考答案：利用二叉树的一些空闲指针指向该结点的前驱或后继,这种指针叫线索,线索后了的二叉树,称为线索二叉树.

正确答案：B

正确答案：A

（15）【答案】A)
【解析】在结点的空指针域中存放的该结点在某种遍历次序下的前驱或后继结点的指针叫做线索（thread），其中在空的左指针域存放的指向其前驱结点的指针叫做左线索，空的指针域存放的指向其后的指针叫做右线索。对一棵二叉树中的所有结点空指针 域按照某种遍历次序加线索的过程叫做线索化，被线索化了的二叉树称作结索二叉树，将二叉树存储为对称序线索二叉树，则结点C的左线索指向其中序遍历前驱结点A。

正确答案：B

正确答案：D