具有12个关键字的有序表画出折半查找判定树
时间: 2023-06-20 21:07:14 浏览: 105
折半查找的判定树可以使用递归的方式来构建。首先,我们需要找到中间元素,然后根据中间元素与目标元素的大小关系,判断目标元素在左侧还是右侧子数组中。然后,我们对相应的子数组进行递归搜索,直到找到目标元素或者确定目标元素不存在。
假设关键字为:1, 3, 4, 6, 7, 8, 10, 13, 14, 16, 17, 20
折半查找的判定树如下所示:
```
[10]
/ \
[4] [16]
/ \ / \
[1] [7] [13] [20]
/ \ / \
[6] [8][14] [17]
/
[3]
```
其中,树的节点表示一个子问题,包括目标元素的可能位置和已经排除的位置。根节点表示整个数组,左子树表示左半部分数组,右子树表示右半部分数组。每个节点有两个子节点,分别表示目标元素可能存在于左半部分或右半部分。如果目标元素不存在于当前子数组中,则将该子数组排除,并且不再对该子数组进行搜索。最终,如果找到目标元素,则返回其下标;否则,返回不存在的信息。