从最后一个非叶子节点开始,依次执行堆调整操作,保证每个节点都大于其子节点,这一步怎么实现的
时间: 2024-03-04 08:50:27 浏览: 31
这一步可以通过递归实现。从最后一个非叶子节点开始,先比较该节点与其左右子节点的大小,如果该节点比左右子节点中最大的一个还要大,就不需要进行堆调整操作;否则,将该节点与左右子节点中最大的一个进行交换,然后对交换后的子节点递归执行堆调整操作,直到该节点满足大于其子节点的要求为止。这样就可以保证整个堆是一个大根堆。
相关问题
从最后一个非叶子节点开始,依次执行堆调整操作,保证每个节点都大于其子节点,这一步怎么实现的,这一步的流程图
下面是从最后一个非叶子节点开始,依次执行堆调整操作的流程图:
![堆调整操作流程图](https://img-blog.csdn.net/20180509092909654?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1bWJsci9jcmVhdGVfYmFsYW5jZV9zbWFsbF9jZWF0aW9u/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)
从最后一个非叶子节点开始,依次执行堆调整操作的步骤如下:
1. 找到最后一个非叶子节点,即列表中的第 N/2 个节点(N 为节点总数,节点编号从 0 开始);
2. 对该节点进行堆调整操作,保证该节点大于其子节点;
3. 依次处理前面的节点,直到处理完根节点(即列表中的第 0 个节点);
4. 最终,整个堆就会被调整成一个大根堆。
给定一棵二叉树的先序遍历序列和中序遍历序列,求解: 1、这棵树的后序遍历序列; 2、从这棵树的右侧观察该树,从根节点到叶子节点,依次输出能被观测到的节点序列。
1、根据先序遍历序列和中序遍历序列,可以重建出原二叉树。具体方法是,先找到先序遍历序列的第一个节点作为根节点,然后在中序遍历序列中找到对应的位置,以此将中序遍历序列分成左子树和右子树两部分。然后对左子树和右子树分别递归,重建出左子树和右子树。最后将根节点插入到后序遍历序列的最后面即可得到后序遍历序列。
2、从右侧观察二叉树,能被观测到的节点序列就是从根节点到叶子节点的最右侧节点。可以采用先序遍历的方式遍历二叉树,在遍历过程中记录下每个节点的深度和从左侧观察到的最右深度,对于每个节点,如果其深度大于当前最右深度,则说明该节点能被观测到,更新最右深度并将该节点加入结果序列。最后得到的结果序列就是从根节点到叶子节点,依次输出能被观测到的节点序列。