由关键字(25,49,28,10,30,5,16)按次序构造的二叉排序树,在其中查找数20,需依次比较哪几个数?按顺序填写:填空1
时间: 2024-04-06 16:32:01 浏览: 33
在二叉排序树中查找数20的过程如下:
1. 从根节点开始比较,根节点的关键字为25。
2. 由于20小于25,因此在左子树中继续查找。
3. 下一个节点是10,由于20大于10,因此在右子树中继续查找。
4. 下一个节点是16,由于20大于16,因此在右子树中继续查找。
5. 下一个节点是30,由于20小于30,因此在左子树中继续查找。
6. 下一个节点是28,由于20小于28,因此在左子树中继续查找。
7. 下一个节点是没有,因为28没有左子树了,因此查找失败。
因此,需要依次比较的数为25、10、16、30、28。按顺序填写,空1的答案为25、10、16、30、28。
相关问题
对{Jan, Feb, Mar, Apr, May,June,July, Aug, Oct, Nov, Dec}分别进行依据次序生成二叉排序树、增序排序后的次序生成二叉排序树、依据当前次序生成平衡二叉排序表,并计算以上3种情况下的ASL。
1. 依据次序生成二叉排序树
首先,我们将第一个节点Jan作为根节点。然后依次将其他节点插入二叉排序树中,按照二叉排序树的性质,比当前节点小的放在左子树中,比当前节点大的放在右子树中。最终得到的二叉排序树如下所示:
```
Jan
|
Feb
|
Mar
|
Apr
|
May
|
June
|
July
|
Aug
|
Oct
|
Nov
|
Dec
```
可以看到,这是一棵高度为11的二叉树,其ASL为(1+2+3+4+5+6+7+8+9+10+11)/12 ≈ 4.92。
2. 增序排序后的次序生成二叉排序树
将月份名称按照字母顺序排序后为{Apr, Aug, Dec, Feb, Jan, July, June, Mar, May, Nov, Oct},然后按照上述方法构造二叉排序树,得到如下结果:
```
Apr
|
Aug
|
Dec
|
Feb
|
Jan
|
July
|
June
|
Mar
|
May
|
Nov
|
Oct
```
可以看到,这仍然是一棵高度为11的二叉树,其ASL为(1+2+3+4+5+6+7+8+9+10+11)/12 ≈ 4.92。
3. 依据当前次序生成平衡二叉排序树
我们可以使用平衡二叉树来解决上述二叉排序树中存在的高度过大的问题。具体来说,我们可以使用AVL树来实现平衡二叉排序树。AVL树是一种自平衡二叉搜索树,可以保证树的高度不超过log2(n),其中n是树中节点数。
下面是按照当前次序生成的平衡二叉排序树:
```
May
/ \
Feb Nov
/ \ \
Apr Mar Oct
/ / \
Aug July Dec
\ /
Jan June
```
可以看到,这是一棵高度为3的平衡二叉树,其ASL为(1+2+3)/12 ≈ 0.25。
因此,按照当前次序生成的平衡二叉排序树是最优的,其平均查找长度最小。
二叉排序树按先序遍历
二叉排序树按先序遍历的顺序是先访问根节点,然后按照左子树、右子树的顺序依次访问二叉树的节点。 具体实现时可以使用递归来遍历树,先访问当前节点,然后递归遍历左子树,最后递归遍历右子树。 通过先序遍历可以获得二叉排序树的先序递归遍历次序。<span class="em">1</span><span class="em">2</span><span class="em">3</span>