题25
题目
Q:【2011 统考真题】对下列关键字序列, 不可能构成二叉排序树中一条查找路径的是 ( )
A. 95,22,91,24,94,71
B. 92,20,91,34,88,35
C. 21,89,77,29,36,38
D. 12,25,71,68,33,34
分析
A:和题21是一个考点
我这里的画法是错误的，我是先入为主的在往正确的树结构上画，没有遵从这个查询的顺序，树后面插那个结点是根据数据的序列来看的，这里的94在24后面，那么94就应该是21的子树的一部分
解
A
在二叉排序树中, 左子树结点值小于根结点, 右子树结点值大于根结点。在选项 A 中, 当查找到 91 后再向 24 查找, 说明这一条路径 (左子树) 之后查找的数都要比 91 小, 而后面却查找到了 94 (解题过程中, 建议配合画图), 因此错误。
画图法: 各选项对应的查找过如下图, 选项 B、C、D 对应的查找树都是二叉排序树, 选项 A 对应的查找树不是二叉排序树, 因为在 91 为根的左子树中出现了比 91 大点的结点 94。
(a) 选项
(b) 选项B的查找过程
(c) 选项C的查找过程
(d) 选项D的查找过程
