我要招人

去企业版

首页 > 试题广场 >

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序

[单选题]

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。

```
95， 22， 91， 24， 94， 71
```
```
92， 20， 91， 34， 88， 35
```
```
21， 89， 77， 29， 36， 38
```
```
12， 25， 71， 68， 33， 34
```

查看正确选项

.牛妹

二叉排序树定义：

1.若左子树不为空，则左子树所有节点都小于根节点

2.若右子树不为空，则右子树所有节点都大于根节点

3.左右子树又分别是一棵二叉排序树

画出A的查找路径，会发现94位于91的左子树中，不满足第一条

发表于 2017-07-01 16:29:07 回复(0)

philian

顺着找就行，比当前节点小，就往左子树上找，比当前节点大，就往右子树上找。A中91后面跟着24，说明要查找的值比91小，那么接下来就不可能再遇上个比91还大的94

发表于 2016-12-16 18:36:10 回复(0)

RenaissanceWhy

前面的节点，或者比后面的节点都大，或者比后面的节点都小。

例如 95， 22， 91， 24， 94， 71。

95比 22， 91， 24， 94， 71都大

22比91， 24， 94， 71 都小

91 比 24， 94， 71都大 （不符合，91比94小）

24 比 94， 71都小

94 比 71大

编辑于 2017-05-03 14:12:57 回复(3)

我不是匠人

二叉树的查找路径，整体看来是从上往下的折线，存在这种∧分叉的，就是错的。

发表于 2017-01-10 23:22:54 回复(2)

lsyyzx

发表于 2017-05-10 09:59:27 回复(5)

heavysun

每个元素向后看两个，一个大于它，一个小于它就不对

发表于 2019-11-01 21:48:42 回复(2)

hcz110

二叉树的查找路径，应该是从上到下所有节点度为1，而A选项构成排序树时会出现度为2的节点，故不正确。

发表于 2017-06-17 21:21:39 回复(2)

zhangxus

二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树：
1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左右子树也分别为二叉排序树。

按照题目选项给的序列顺序，按照二叉排序树的性质画出二叉排序树，发现A选项91存在左分支，但是左分支里有94不满足小于根节点元素91的要求。（此处需要看分支后边所有元素是否均满足性质要求，不仅仅是左右孩子结点元素）

发表于 2019-08-07 15:14:48 回复(0)

毛姝垚

发表于 2022-11-29 13:47:39 回复(0)

牛客308492346号

选A。我做这个题有两个方法，都很容易理解。

第一张方法是，画出每个选项的二叉排序树（只画序列中有的结点就可以），然后中序遍历二叉排序树，如果中序遍历后的序列不是有序的，则该答案是不可能存在的情况。

第二种方法是，也画出每个选项的二叉排序树，然后自己模拟一颗二叉排序树创建的过程，比如选项A，先创建根节点95，再插入22肯定要插到95的左孩子处，再插入91，24……当插入94的时候，应当插到91的右侧，这与根据序列画出的二叉排序树不相符。

综上，上面两种方法都指向A是错误序列。

发表于 2021-12-14 19:36:37 回复(0)

我不道啊

要点:前面的节点，要么都比后面的节点大，要么都比后面的节点小。比较一个后之就不参加之后的比较

发表于 2018-09-12 22:06:57 回复(0)

哈哈哈哈哈哈哈和哈嗝

一直涨，当下降的时候，后面就不会有比它大的了

发表于 2018-05-08 10:50:43 回复(0)

千寻者

非常感谢！

发表于 2017-07-14 12:22:16 回复(0)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

13条回答 265收藏 31628浏览

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序

问题信息

热门推荐

相关试题