首页 > 试题广场 >

假设某棵二叉查找树的所有键均为1到10的整数，现在我们要查找

[单选题]
假设某棵二叉查找树的所有键均为1到10的整数，现在我们要查找5。下面____不可能是键的检查序列。 
  • 10,9,8,7,6,5
  • 2,8,6,3,7,4,5
  • 1,2,9,3,8,7,4,6,5
  • 2,3,10,4,8,5
  • 4,9,8,7,5
  • 以上均正确
查看答案及解析
添加回答
推荐
小牛91头像 小牛91
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根节点点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
先看A选项，第一个节点值为10，比要查找的5大，所以要接下来要比较10的左子树，左子树上的值一定比10小，而选项A中的第二个查找值是9，合理。此时，9仍然比待查找的数字5大，要继续查找9的左子树，左子树比9小，而查找的下一位数字为8，合理。依次类推。。。。
编辑于 2015-06-19 17:24:46 回复(4)
*翎头像 *翎
关键在于: "查找路径"一定是"查找树"的"不带分支"的"子查找树"。 关键点: 不带分支，查找树。 法1:构建二叉查找树，看是否有分支; 法2:构建没分支的查找路径，看是否是二叉查找树
编辑于 2017-08-22 18:04:37 回复(1)
main方法栈帧头像 main方法栈帧
按照B的顺序查找
6左子树的右子树是7
比6大
所以不符合二叉排序树
发表于 2021-11-05 15:48:51 回复(0)
karaysn头像 karaysn
B项 6的后面出现了7，3和4，一组比6大，一组比7小，所以不对
发表于 2017-12-03 14:59:57 回复(0)
牛牛12315头像 牛牛12315
二叉排序树的查找不是中序遍历之 吗？ 此题是么意思 
发表于 2015-09-04 11:48:15 回复(0)
熊猫的斑竹先森头像 熊猫的斑竹先森
这道题怎么回事，还是没看懂啊，很多人说B中7>6所以不行，但是8还>2呢C中8还>3呢？？？
发表于 2015-08-22 09:55:21 回复(1)
王汉杰头像 王汉杰
对任意点，后面的元素要么全部大于它，要么全部小于它。B不符。
发表于 2015-09-17 09:08:01 回复(11)
丁小玲头像 丁小玲
B 这个题目不用进行画，利用二叉排序树的概念进行判断即可，对于选项B来说：6>5，应该在左子树上面开始查找，其左子树上的所有节点应该都小于6，但是后续序列中出现7>6，所以选B。
发表于 2015-05-25 17:44:04 回复(0)
wangChaoNK头像 wangChaoNK
发表于 2017-05-27 20:17:07 回复(1)
美团到店招聘头像 美团到店招聘
这道题目很好判断。对于二叉排序树的比较，当与某个结点进行比较时，如果相等，就结束。如果不等的话，要么在该结点的左子树里找，那么比较路径后面的所有值都比根结点小；要么在该结点的右子树里找，那么比较路径后面的所有值都比根结点大；所以根本不用去判断二叉树的形状，直接根据路径就能看出该路径对不对。
例如：A： 10 9 8 7 6 5，对于10来说，之后的值都比它小，满足；对于9，之后的值都比它小，满足，以此类推。
B：2 8 6 3 7 4 5，对于2，之后的值都比它大，满足；对于8，之后的值都比它小，满足；对于6，之后的值有比它大，也有比它小的，所以错误！
发表于 2017-02-17 10:34:01 回复(1)
分形叶头像 分形叶
B.
注意到序列6,3中3<6那么6以后的数字都在6的左子树上，即6后面的数应该都小于6，但是7>6,故是错误的
编辑于 2015-08-02 10:00:54 回复(3)
放作夥头像 放作夥
突然想到一种方法。
A.10,9,8,7,6,5。 逐个检查， 10后面的 数都比10小，ok。9后面的数都比9小，ok。
B.2,8,6,3,7,4,5。 逐个检查，2后面的数都比2大，ok。但6的后面有比6大的也有小的
发表于 2015-08-29 15:48:21 回复(1)
修心不唯心头像 修心不唯心
后面的结点不是都大于它就是都小于它
发表于 2020-03-15 10:17:38 回复(0)
ABCD头像 ABCD
A.         5      
         6        
       7          
     8            
   9              
10                

B.          5
         4 
      3    7  
        6  
     2    8

C.        
      5
         6
      4  
         7
      3    
   2    8
1    9

D.       5
      4
   3    8
2    10

E.5  
    7
       8
    4    9

我觉得都可以呀
发表于 2015-06-03 15:30:22 回复(2)
迷茫的小学生allin秋招头像 迷茫的小学生allin秋招
对于B选项，序列：2,8,6,3,7,4,5
对于数字2，5 > 2，根据二叉查找树的定义，数字2后面的所有数字均应大于等于2，满足；
对于数字8, 5< 8，数字8后面的所有数字均应小于8，满足；
对于数字6，5 < 6，数字6后面的所有数字均应小于6，
但是7 > 6，不满足，所以该检查序列不可能。

对于E选项，序列：4,9,8,7,5
对于数字4，5>4，则数字4后面的所有数字均应大于等于4，满足；
对于数字9，5<9，则数字9后面的所有数字均应小于9，满足；
同理，对于数字8、7也是这样的规律

发表于 2024-06-22 17:36:28 回复(0)
有一套的小飞象想当offer收割机头像 有一套的小飞象想当offer收割机
这个题可以单独把比5大的数及比5小的数列出 如C选项：1,2,9,3,8,7,4,6,5 大于5有：9,8,7,6 满足从大到小 小于5有：1,2,3,4 满足从小到大 B选项：2,8,6,3,7,4,5 大于5有：8,6,7 不满足从大到小所以不可能
发表于 2023-02-22 18:30:43 回复(0)
孤天祭头像 孤天祭
手滑选错乐
发表于 2020-08-31 09:01:54 回复(0)
GoodFellow201904261341544头像 GoodFellow201904261341544
楼上正解，对后面的元素，要么全部大于他，要么全部小于他
发表于 2019-08-30 14:39:45 回复(0)
sunlight_run头像 sunlight_run
判断方法是：对任意一点，后面元素要么全部全部大于它，要么全部小于它
发表于 2017-06-27 14:52:54 回复(1)
海阔天空666头像 海阔天空666
对任意点，后面的元素要么全部大于它，要么全部小于它。B不符。其实你这句话更精确的说法是，对于每个分支的根节点其组左子树的值都要比分支的根节点要小，右子树的值比分支的根节点要大
发表于 2017-04-17 21:27:58 回复(0)
爱吃青菜皮卷面的byr头像 爱吃青菜皮卷面的byr
二叉树的概念：
若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点
     因此，若5大于根节点的值，则右子树查找，后续所有结点的值都大于它的根节点。 同理，若5小于根节点的值，则左子树查找，后续所有结点的值都小于它的根节点。 对于B选项，2<5，右子树查找，后面的结点都大于2，没问题。 8>5，左子树查找，后面的结点都小于8，没问题。 6>5, 左子树查找， 后面的结点都小于6（但是有7），有问题，B选项 错误。

发表于 2017-02-16 11:48:55 回复(0)
提交观点

问题信息

设计 算法工程师 阿里巴巴 树 2015
来自：阿里巴巴2015算法工...
上传者：陈木木
难度：
35条回答 19274浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号