A.s→right指向的结点一定是s所指结点的直接后继结点B.s→left指向的结点一定是s所指结点的直

Question

A．s→right指向的结点一定是s所指结点的直接后继结点

B．s→left指向的结点一定是s所指结点的直接前驱结点

C．从s所指结点出发的right链可能构成环

D．s所指结点的left和right指针一定指向不同的结点

Answer 1

正确答案：C
解析：本题考查数据结构基础知识。具有m个结点的二叉树采用二叉链表存储结构，链表中共有m个结点，-每个结点中两个指针(当前结点的左、右孩子指针)，则共有2m个指针。除了树根之外，其余的每个结点都由一个来自父结点的指针所指向，因此该二叉链表结点中的空指针总数必定为2m-(m-1)＝m+1个，可以充分利用这些空指针域来存放结点的前驱和后继信息。对图(a)所示的二叉树进行中序线索化后如图(b)所示。假设指针s指向中序线索二叉树中的某结点，则s→right指向的结点不一定是s所指结点的直接后继结点。当s结点具有右子树时，s→right指向其右子树而不是后继结点。同理，s→left指向的结点不一定是s所指结点的直接前驱结点。索二叉树中，s所指结点的left和right指针可能指向相同的结点，从s所指结点出发的right链可能构成环，如图(c)所示。