设计java 用序列(100,65,88,93,145,118,138,112,188,173,42,75,20,197)建立一个二叉排序树,按照关键字输入顺序画出该树,并求在等概率情况下查找成功的平均查找长度。
时间: 2023-08-03 15:07:18 浏览: 221
首先,建立二叉排序树的步骤如下:
1. 将第一个数 100 作为根节点。
2. 将第二个数 65 与根节点比较,小于根节点则作为左子节点,否则作为右子节点。
3. 将第三个数 88 与根节点比较,小于根节点则与左子节点比较,大于左子节点则作为左子节点的右子节点,否则作为左子节点的左子节点。
4. 依次对每个数进行比较插入,最终得到如下的二叉排序树:
```
100
/ \
65 145
/ \ \
42 88 188
/ \ \
75 93 197
/ \
112 138
/
118
/
20
```
接下来,我们需要计算在等概率情况下查找成功的平均查找长度(ASL)。由于每个关键字出现的概率相等,因此可以使用公式 ASL = (深度之和) / (节点总数) 来求解。
节点总数为 14,深度之和为 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5 = 47。
因此,ASL = 47 / 14 = 3.357。
阅读全文