返回主页
已有13条笔记
[数据结构 P1465] 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是______。
未通过
对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是______。
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选项： (−∞,95]→[22,95]→[22,91]→[24,91] ， 94 越界，错误。
B选项： [21,+∞)→[21,98]→[21,77]→[29,77]→[36,77]→[38,77] ，正确。
C选项： (−∞,92]→[20,92]→[20,91]→[34,91]→[34,88]→[35,88] ，正确。
D选项： [12,+∞)→[25,+∞)→[25,71]→[25,68]→[33,68]→[34,68] ，正确。
本题选A。
方法二：二叉搜索树 + 中序遍历
折半查找过程对应一棵二叉搜索树，其中序遍历序列单调递增。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案