已知序列{50,72,43,85,75,20,35,45,65,30}请画出依次插入结点构造二叉排序树的过程
时间: 2024-01-06 22:06:31 浏览: 29
好的,我会根据您的要求画出依次插入节点构造二叉排序树的过程。下面是每一次插入节点后的二叉排序树:
```
50
50
\
72
50 72
\ \
43 85
50 72
\ \
43 85
\ /
75 75
50 72
\ \
43 85
\ / \
75 75 20
50 72
\ \
43 85
/ \ / \
20 45 75 20
50 72 35
\ \ \
43 85 45
/ \ / \ / \
20 45 75 20 35 65
50 72 35
\ \ \
43 85 45
/ \ / \ / \
20 45 75 20 35 65
\
30
```
希望这个过程可以帮助您更好地理解二叉排序树的构造过程。
相关问题
已知序列{50,72,43,85,75,20,35,45,65, 30},请画出依次插入结点构造二叉排序树的过程。
好的,我可以帮你画出这个过程。
首先,我们将 50 插入空树中,得到以下 BST:
```
50
```
接下来,将 72 插入 BST 中,得到:
```
50
\
72
```
然后,将 43 插入 BST 中,得到:
```
50
/ \
43 72
```
继续将 85 插入 BST 中,得到:
```
50
/ \
43 72
\
85
```
然后,将 75 插入 BST 中,得到:
```
50
/ \
43 72
\
85
/
75
```
继续将 20 插入 BST 中,得到:
```
50
/ \
43 72
/ / \
20 65 85
\
75
```
然后,将 35 插入 BST 中,得到:
```
50
/ \
43 72
/ \ / \
20 35 65 85
\
75
```
接下来,将 45 插入 BST 中,得到:
```
50
/ \
43 72
/ \ / \
20 35 65 85
/
45
\
46
```
最后,将 30 插入 BST 中,得到:
```
50
/ \
43 72
/ \ / \
20 35 65 85
/ /
30 45
\
46
```
这就是插入结点构造二叉排序树的过程。希望能帮到你!
已知长度为8的表(34,76,45,20,25,54,93 66),按照依次插入结点的方法生成一棵二叉排序树,写出构造过程,求出等概率下查找成功的平均查找长度。
二叉排序树的构造过程如下:
1. 将第一个结点 34 作为根结点。
2. 将第二个结点 76 与根结点比较,大于根结点,作为右子结点。
3. 将第三个结点 45 与根结点比较,小于根结点,作为左子结点。
4. 将第四个结点 20 与根结点比较,小于根结点,继续与左子结点比较,作为左子结点的左子结点。
5. 将第五个结点 25 与根结点比较,小于根结点,继续与左子结点比较,作为左子结点的右子结点。
6. 将第六个结点 54 与根结点比较,大于根结点,继续与右子结点比较,作为右子结点的左子结点。
7. 将第七个结点 93 与根结点比较,大于根结点,继续与右子结点比较,作为右子结点的右子结点。
8. 将第八个结点 66 与根结点比较,大于根结点,继续与右子结点比较,作为右子结点的左子结点的右子结点。
构造完成的二叉排序树如下:
```
34
/ \
20 76
\ / \
25 54 93
/
66
```
等概率下查找成功的平均查找长度为树中每个结点深度的平均值。对于这棵二叉排序树,每个结点的深度分别为 1,2,2,3,3,3,4,所以平均查找长度为:
(1+2+2+3+3+3+4)/8 = 2.5