首页 > 试题广场 >

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当

[单选题]
初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为：（） 
  • 8 3 2 5 1 6 4 7
  • 3 2 8 5 1 4 6 7
  • 3 8 2 5 1 6 7 4
  • 8 2 3 5 1 4 7 6
添加回答
推荐
Aesthetic92头像 Aesthetic92
答案：选A
答案解释：初始化序列：1 8 6 2 5 4 7 3,，小根堆就是要求结点的值小于其左右孩子结点的值，左右孩子的大小没有关系，那么小根堆排序之后为：1 2 4 3 5 6 7 8；
中序遍历：先遍历左孩子，然后访问根结点，最后访问有孩子，故遍历结果为：8 3 2 5 1 6 4 7
编辑于 2015-02-04 21:35:30 回复(1)
牛牛12315头像 牛牛12315
首先从最后一个 非端子结点开始(即2) 因为是建小根堆 所以交换子节点中小于自己的最小那个 3比2大——不换
看6 与4换   接着8与2换且与3换 最后1不换  就形成了最终结果  然后再中序遍历之
发表于 2015-09-04 16:25:00 回复(4)
刘曼头像 刘曼
最小堆：先以数组顺序构建一棵完全二叉树，再从第n/2 +1个元素开始构建最小堆，再进行中序遍历。
发表于 2015-03-12 11:01:53 回复(1)
菩提旭光头像 菩提旭光
假设有数组A = {1, 3, 4, 5, 7, 2, 6, 8, 0}。 建堆思想： 从第n/2个节点开始，进行堆的调整，这个过程叫建堆。

编辑于 2015-08-22 18:35:57 回复(1)
牛客2793674号头像 牛客2793674号
先按数组顺序组成一颗完全二叉树，再从最后一个非叶子节点开始向前建大顶堆


发表于 2017-08-04 16:04:31 回复(1)
朱朱头像 朱朱
用初始序列建立完全二叉树，从完全二叉树的底层开始下滤，下滤完成建立二叉堆，再重新中序遍历
发表于 2015-09-02 15:26:37 回复(0)
香蕉牛奶头像 香蕉牛奶
A
小根堆排序之后为：1 2 4 3 5 6 7 8；
中序遍历：先遍历左孩子，然后访问根结点，最后访问有孩子，故遍历结果为：8 3 2 5 1 6 4 7

发表于 2015-01-28 16:53:54 回复(2)
杨美丽头像 杨美丽
解析： 堆排序：利用堆的性质进行的一种选择排序 答案：A
发表于 2014-10-25 00:25:57 回复(0)
20190716092877头像 20190716092877
这题就是没画图,画个图就清楚了
            1
       8              6
    2    5        4     7
  3
小根堆就是要求结点的值小于其左右孩子结点的值，左右孩子的大小没有关系，从小到大排序
4 和 6 换位置  3和8换位置之后,3再与2换位置
则调整后为
            1
       2            4
    3    5      6     7 
   8
   
然后中序输出就会了
发表于 2019-08-18 18:20:04 回复(0)
阿伊阿伊哦头像 阿伊阿伊哦
直接看后三位，中序遍历，中间为根节点，最小堆根节点肯定小于左右子树，直接选出来
发表于 2017-03-06 16:42:39 回复(0)
提交观点

问题信息

堆 腾讯
来自：腾讯2014校招研发工...
难度：
10条回答 19456浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号