题5
题目
Q:设二叉排序树中关键字由 1 到 1000 的整数构成, 现要查找关键字为 363 的结点下述关键字序列中, 不可能是在二叉排序树上查找的序列是 ( ).
A. 2,252,401,398,330,344,397,363
B. 924,220,911,244,898,258,362,363
C. 925,202,911,240,912,245,363
D. 2,399,387,219,266,382,381,278,363
分析
A:要保证可以排列成一棵，左孩子比自己小，右孩子比自己大，的那么一棵二叉树
这个查找序列的结果是一个中序遍历的结果，可以根据这个结果反推出二叉树的结构
没看懂这个选项要怎么使用，评价的依据是什么
解
C
在二叉排序树上查找时, 先与根结点值进行比较, 若相同, 则查找结束, 否则根据比较结果, 沿着左子树或右子树向下继续查找。
根据二叉排序树的定义, 有左子树结点值≤根结点值≤右子树结点值。
C 序列中, 比较 911 关键字后, 应转向其左子树比较 240, 左子树中不应出现比 911 更大的数值, 但 240 竟有一个右孩子结点值为 912 , 所以不可能是正确的序列。