3、已知一组元素为(40, 22, 87, 62, 12,37, 25, 65);(1)画出按元素排列顺序输入生成的一棵二叉 搜索树。(2)以广义表的形式给出该二叉搜索树。 (3)给出删除节点22之后的二叉搜索树。(20 分)。
时间: 2023-09-17 14:06:21 浏览: 53
### 回答1:
(1) 二叉搜索树如下图所示:
```
40
/ \
22 87
/ \ / \
12 37 62 65
\
25
```
(2) 该二叉搜索树的广义表表示为:(40, (22, (12, (), ()), (37, (25, (), ()), ())), (87, (62, (), ()), (65, (), ())))
(3) 删除节点22后的二叉搜索树如下图所示:
```
40
/ \
25 87
/ \ / \
12 37 62 65
```
### 回答2:
(1)按照元素排列顺序输入,生成的二叉搜索树如下:
40
/ \
22 87
/ \ /
12 37 62
\ \
25 65
(2)以广义表的形式表示该二叉搜索树为:(40, (22, (12, ∅, ∅), (37, ∅, ∅)), (87, (62, ∅, (65, ∅, ∅)), (25, ∅, ∅)))
(3)删除节点22之后的二叉搜索树如下:
40
/ \
25 87
/ \ /
12 37 62
\ \
25 65
### 回答3:
(1) 根据元素的排列顺序,可以根据二叉搜索树的规则逐个插入元素构建一棵二叉搜索树。首先,根据根节点的定义,将根节点值设为40。然后,将22插入根节点的左子树,因为22小于40。接下来,将87插入根节点的右子树,因为87大于40。然后,将62插入根节点的左子树的右子树,因为62大于22但小于40。继续按照这样的规则,将12插入根节点的左子树的左子树,将37插入根节点的左子树的右子树的左子树,将25插入根节点的左子树的右子树的左子树的右子树,将65插入根节点的右子树的左子树。
二叉搜索树如下:
40
/ \
22 87
/ \ /
12 37 62
\
65
(2) 以广义表的形式给出该二叉搜索树为:
(40 (22 (12 () ()) (37 () (25 () ()))) (87 (62 () (65 ()) ) ()))
(3) 删除节点22之后的二叉搜索树,需要重新调整节点的位置。首先找到要删除的节点22,因为22没有子节点,所以可以直接删除。删除节点时需要考虑到二叉搜索树的规则,即需要保持左子树的值小于根节点的值,右子树的值大于根节点的值。在删除节点22后,可以将37移动到根节点的左子树,25作为37的右子树。
删除节点22之后的二叉搜索树如下:
40
/ \
37 87
/ \ /
12 25 62
\
65
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)