使用有序列表中的元素分别是1、5、8、0、2、0、6、4、3、9、0构造小根堆,所得到前序、中序、后序遍历结果是什么,重复数字不可以忽略不计
时间: 2023-09-18 20:10:36 浏览: 13
首先,根据小根堆的定义,父节点的值一定小于等于其子节点的值。因此,我们可以用以下步骤构造小根堆:
1. 将列表中的第一个元素1作为堆的根节点。
2. 依次将5、8插入堆中,插入时需要满足小根堆的条件,因此5插入到根节点的左子节点,8插入到根节点的右子节点。
3. 插入0时,由于0小于1,因此将0插入到根节点的左子树中。此时,根节点的左子节点为0,右子节点为5。
4. 插入2时,由于2大于根节点的值1,因此将2插入到根节点的右子树中。此时,根节点的左子节点为0,右子节点为5,右子节点的左子节点为2,右子节点的右子节点为8。
5. 插入0时,由于0小于5,因此将0插入到5的左子树中。此时,根节点的左子节点为0,右子节点为5,右子节点的左子节点为2,右子节点的右子节点为8,左子节点的左子节点为0。
6. 依次插入6、4、3、9、0,重复数字也需要插入,最终得到的小根堆如下所示:
```
0
/ \
2 5
/ \ / \
4 3 6 8
/ \
9 0
```
接下来,我们来求得小根堆的前序、中序、后序遍历结果:
1. 前序遍历结果为:0 2 4 9 0 3 6 5 8
2. 中序遍历结果为:9 4 0 2 3 0 6 5 8
3. 后序遍历结果为:9 0 4 3 6 2 8 5 0
注:前序遍历的顺序是先遍历根节点,然后遍历左子树,最后遍历右子树;中序遍历的顺序是先遍历左子树,然后遍历根节点,最后遍历右子树;后序遍历的顺序是先遍历左子树,然后遍历右子树,最后遍历根节点。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)