已知如下所示长度为12的表:(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) ①试按表中元素的顺序依次插入一棵初始 为空的二叉排序树,画出插入完成之后的二叉排 序树,并求其在等概率的情况下查找成功的平均 查找长度。 ③按表中元素顺序构造一棵平衡二叉排序 树,并求其在等概率的情况下查找成功的平均查 找长度。
时间: 2023-08-18 17:05:08 浏览: 606
好的,我会尽力回答您的问题。
① 按照元素顺序插入二叉排序树的过程如下:
首先,将 Jan 插入根节点,得到如下的二叉排序树:
```
Jan
/ \
None None
```
接着,将 Feb 插入根节点的右子树,得到如下的二叉排序树:
```
Jan
\
Feb
/ \
None None
```
继续插入 Mar,Apr,May,June,July,Aug,Sep,Oct 和 Nov,最终得到如下的二叉排序树:
```
Jan
/ \
None Feb
/ \
Apr Mar
/ \ / \
July June May Aug
/ \ / \
None Oct Sep Nov
```
在等概率的情况下查找成功的平均查找长度为(1+2+2+3+3+3+3+4+4+4+4+4)/12 = 2.92。
③ 按照元素顺序构造平衡二叉排序树的过程如下:
首先,从表中间取出 July 作为根节点,得到如下的平衡二叉排序树:
```
July
/ \
Apr Nov
/ \ / \
Jan June Oct Dec
\ / /
Feb May Aug
```
在等概率的情况下查找成功的平均查找长度为(1+2+2+3+3+3+3+4+4+4+4+4)/12 = 2.92,与①中的结果相同。
希望这个答案能够对您有所帮助。如果您还有其他问题,请随时问我。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)