已知如下11个元素的有序表(8,16,19,23,39,52,63,77,81,88,90),画出其二分查找的判定树,给出查找元素88和17的折半查找过程。
时间: 2023-09-13 09:05:22 浏览: 201
二分查找的判定树如下所示:
```
52
/ \
19 81
/ \ / \
8 39 63 88
/ \ \
23 77 90
```
查找元素88的过程如下:
1. 从根节点52开始,将88与根节点的元素比较,发现88比52大,因此在右子树中查找。
2. 在右子树的根节点81处,将88与81比较,发现88比81小,因此在左子树中查找。
3. 在左子树的右子树中查找,发现88与90不相等,再在左子树的左子树中查找,发现88与77不相等,最后在左子树的根节点63处查找,发现88与63不相等,但是因为此时已经到达叶子节点,无法继续查找,因此查找失败。
查找元素17的过程如下:
1. 从根节点52开始,将17与根节点的元素比较,发现17比52小,因此在左子树中查找。
2. 在左子树的根节点19处,将17与19比较,发现17比19小,因此在左子树中查找。
3. 在左子树的右子树中查找,发现17与23不相等,而左子树的左子树是空的,因此查找失败。
阅读全文