a. 给出将3,1,4,6,9,2,5,7插入到初始为空的二叉查找树中的结果; b. 给出删除根后的结果。
时间: 2024-02-02 18:04:58 浏览: 25
a. 将3,1,4,6,9,2,5,7插入到初始为空的二叉查找树中的结果如下图所示:
```
3
/ \
1 4
\ \
2 6
/ \
5 9
/
7
```
b. 删除根节点3后,将它的右子树中最小的节点5作为根节点,再将左子树插入到新根的左子树中,得到下面的二叉查找树:
```
4
/ \
1 6
\ \
2 9
/
7
\
5
```
注意,如果右子树为空,则直接将左子树作为新根节点即可。
相关问题
指出将3,1,4,6,9,2,5,7插入到初始为空的二叉查找树中的结果。
根据提供的引用内容,我们可以使用递归树的方法来插入给定的元素到一个初始为空的二叉查找树中。下面是将3, 1, 4, 6, 9, 2, 5, 7插入到初始为空的二叉查找树中的结果:
```
3
/ \
1 4
\ \
2 6
\
9
/
7
/
5
```
将关键字序列(9,1,23,14,55,20,84,27)顺序依次插入初始为空的二叉排序树,并求出等概率情况下查找成功的平均查找长度
等概率情况下查找成功的平均查找长度(ASL)可以通过以下公式计算:
ASL = (根结点深度 + 左子树的ASL + 右子树的ASL) / N
其中,N为关键字序列的长度。
对于本题,可以先构造出二叉排序树,然后再计算等概率情况下查找成功的平均查找长度。
将关键字序列(9,1,23,14,55,20,84,27)依次插入初始为空的二叉排序树,得到的树结构如下:
```
9
/ \
1 23
\ / \
14 20 55
/ \
27 84
```
根结点深度为2,左子树的ASL为(0+1+2)/4=0.75,右子树的ASL为(1+1+2)/4=1.00。因此,等概率情况下查找成功的平均查找长度为:
ASL = (2 + 0.75 + 1.00) / 8 = 0.34375
因此,等概率情况下查找成功的平均查找长度为0.34375。