现有如下的单词,int break else switch double case char float for do if while 请以这些单词构造一棵最大堆 (大根堆) 给出构造的过程
时间: 2023-09-08 15:05:34 浏览: 190
### 回答1:
以下是构造最大堆的步骤:
1. 将这些单词放入一个数组中,从左到右依次为:int、break、else、switch、double、case、char、float、for、do、if、while
2. 从最后一个非叶子结点开始,即最后一个case,将它与其左右孩子(char和float)比较,如果case大于两个孩子中较大的一个,则交换之,如果case小于两个孩子中较大的一个,则继续比较该孩子与其左右孩子,直到不再存在孩子为止。
3. 接着从倒数第二个非叶子结点开始,将它与其左右孩子(double和case)比较,如果else大于两个孩子中较大的一个,则交换之,如果else小于两个孩子中较大的一个,则继续比较该孩子与其左右孩子,直到不再存在孩子为止。
4. 依次类推,直到根结点(int)。
### 回答2:
最大堆是一种满足完全二叉树性质,并且父节点的键值大于或等于其子节点的键值的二叉树。
我们可以使用上述给定的单词来构造一棵最大堆。
首先,我们将单词按照字母顺序排列,得到如下序列:
break case char double do else float for if int switch while
接下来,我们按照完全二叉树的性质,从左到右、从上到下的顺序,将单词依次放入堆中。
首先,我们放入最大的单词 "while",作为根节点。
然后,我们放入 "switch" 和 "int" 作为第二层的两个子节点。
再然后,我们放入 "for","if","else","double","char" 和 "case" 作为第三层的子节点。
最后,我们放入 "break" 和 "do" 作为第四层的子节点。
在这个过程中,我们按照字母序将单词依次放入堆中,并保持堆的完全二叉树性质和最大堆的性质,即父节点的键值大于或等于其子节点的键值。
通过上述过程,我们成功构造了一棵最大堆。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)