设计java 用序列(100,65,88,93,145,118,138,112,188,173,42,75,20,197)建立一个二叉排序树,按照关键字输入顺序画出该树,并求在等概率情况下查找成功的平均查找长度。
时间: 2023-09-24 10:09:01 浏览: 54
首先,根据序列建立二叉排序树的过程如下:
1. 将第一个节点100作为根节点。
2. 依次将65、88、93、145、118、138、112、188、173、42、75、20、197插入到树中。
3. 插入节点的过程中,如果该节点的关键字小于当前节点的关键字,则将其插入到当前节点的左子树中,否则插入到当前节点的右子树中。
建立完成后的二叉排序树如下图所示:
```
100
/ \
65 145
/ \ \
42 88 197
/ / \
20 75 93
\ \
118 138
/
112
\
188
\
173
```
在等概率情况下查找成功的平均查找长度是指,对于任意一个节点,从根节点开始查找到该节点的平均查找次数。由于每个节点被查找的概率相同,因此可以将所有节点的查找次数加起来,再除以节点总数,即可得到平均查找长度。
对于这个二叉排序树,各个节点的查找次数和深度如下表所示:
| 关键字 | 深度 | 查找次数 |
|--------|------|----------|
| 100 | 1 | 1 |
| 65 | 2 | 2 |
| 42 | 3 | 3 |
| 20 | 4 | 4 |
| 75 | 3 | 3 |
| 88 | 3 | 3 |
| 93 | 4 | 4 |
| 145 | 2 | 2 |
| 197 | 3 | 3 |
| 118 | 4 | 5 |
| 138 | 5 | 6 |
| 112 | 6 | 7 |
| 188 | 6 | 7 |
| 173 | 7 | 8 |
将所有节点的查找次数加起来,得到:
1 + 2 + 3 + 4 + 3 + 3 + 4 + 2 + 3 + 5 + 6 + 7 + 7 + 8 = 55
因此,平均查找长度为:
55 / 14 ≈ 3.93
即在等概率情况下,从根节点开始查找任意一个节点的平均查找次数约为3.93次。