关于各种非空线索二叉树中空指针的个数有如下说法:①任一非空先序线索二叉树有2个空指针。②任一非

Question

关于各种非空线索二叉树中空指针的个数有如下说法：

①任一非空先序线索二叉树有2个空指针。

②任一非空中序线索二叉树有2个空指针。

③任一非空后序线索二叉树有2个空指针。

其中说法准确的个数是(5)。

A．0

B．1

C．2

D．3

Answer 1

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

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

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