将下列序列解析为完全二叉树,请问以下序列中能构成最小堆的是( )
4, 5, 7, 7, 8, 10, 4
10, 9, 8, 7, 3, 2, 1
3, 4, 5, 5, 5, 9, 6
3, 14, 10, 20, 30, 9, 12
满二叉树
一个深度为k,节点个数为2^k-1的二叉树为满二叉树,即一棵树深度为k,没有空位。
完全二叉树
一棵深度为k有n个节点的二叉树,对树中节点按从上至下、从左至右的顺序进行编号,如果编号为i(1<=i<=n)的节点与满二叉树中编号为i的节点的二叉树中位置相同,则这棵树为完全二叉树。满二叉树是特殊的完全二叉树。
最小堆
最小堆是一种经过排序的完全二叉树,其中任意非终端节点数值均不大于其左子节点和右子节点的值。
================================================================
可以根据四个答案的序列画出对应的完全二叉树。
4, 5, 7, 7, 8, 10, 4:
4
5 7
7 8 10 4
并不满足任一非终端节点的数据值均不大于其左子节点和右子节点的值。
10, 9, 8, 7, 3, 2, 1:
10
9 8
7 3 2 1
此为最大堆,并非最小堆。
3, 4, 5, 5, 5, 9, 6:
3
4 5
5 5 9 6
满足任一非终端节点的数据值均不大于其左子节点和右子节点的值。
3, 14, 10, 20, 30, 9, 12:
3
14 10
20 30 9 12
并不满足任一非终端节点的数据值均不大于其左子节点和右子节点的值。
一个深度为k,节点个数为2^k-1的二叉树为满二叉树,即一棵树深度为k,没有空位。
完全二叉树
一棵深度为k有n个节点的二叉树,对树中节点按从上至下、从左至右的顺序进行编号,如果编号为i(1<=i<=n)的节点与满二叉树中编号为i的节点的二叉树中位置相同,则这棵树为完全二叉树。满二叉树是特殊的完全二叉树。
最小堆
最小堆是一种经过排序的完全二叉树,其中任意非终端节点数值均不大于其左子节点和右子节点的值。
================================================================
可以根据四个答案的序列画出对应的完全二叉树。
4, 5, 7, 7, 8, 10, 4:
4
5 7
7 8 10 4
并不满足任一非终端节点的数据值均不大于其左子节点和右子节点的值。
10, 9, 8, 7, 3, 2, 1:
10
9 8
7 3 2 1
此为最大堆,并非最小堆。
3, 4, 5, 5, 5, 9, 6:
3
4 5
5 5 9 6
满足任一非终端节点的数据值均不大于其左子节点和右子节点的值。
3, 14, 10, 20, 30, 9, 12:
3
14 10
20 30 9 12
并不满足任一非终端节点的数据值均不大于其左子节点和右子节点的值。