问题
单项选择题
一棵二叉排序树可顺序存放在一组物理上相邻的存储区中，每个结点及左、右指针依次分别放在该存储区的3个连续单元中。现对一棵结点按字母的字典顺序构成的二叉排序树从根结点户开始顺序放在一个存储区中，结果如图4-13所示。其中Li为第i个结点的左指针，Ri为第i个结点的右指针，则L2应为 (1) ，L4应为 (2) ，R1应为 (3) 。该二叉排序树的前序遍历序列为 (4) ，后序遍历序列为 (5) 。
图4-13 二叉排序树的存储
5（）
A．PBQHCJ
B．PBHCJQ
C．BCHJPQ
D．CJHBQP
E．BHCJQP
答案
参考答案：D
解析：
解答本题最关键的一步是要构造出与题目对应的二叉树，可以利用的条件有4个：二叉排序树、顺序存放、根结点P，以及存储结构图中出现的结点关键字。
构造树的过程是这样的：
首先画出根结点P，然后在存储结构图4-13中找出下一个结点关键字B(因为题目告诉我们，二叉排序树是顺序存放在一组物理上相邻的存储区中的)，由于B＜P，所以B以左子结点的身份加入排序二叉树；接着从结构图中找下一个结点关键字Q，Q＞ P，所以Q以右子结点的身份加入排序二叉树。
接下来的结点是H，因为H＜P，则H在P的左子树中，又因为H＞B，所以H最终作为B的右子树。
再下一个结点是巴同理，因为C＜P，C＞B，C＜H，则C最终作为H的左子树。最后一个结点是J，J＜P，J＞B，J＞H，则J最终作为H的右子树。得到的二叉排序树如图4-19所示。
[*]
由图4-19可得出，L2指向Null；L4指向巴即100C；R1指向 Q，即1006；该二叉排序树的前序遍历序列为PBHCJQ，后序遍历序列为CJHBQP。