题5

题5

题目

Q:在含有 个关键字的小根堆中,关键字最大的记录有可能存储在 ( ) 位置.
A.
B.
C. 1
D.

分析

A:这是小根堆, 关键字最大的记录一定存储在这个堆所对应的完全二叉树的叶结点中;
又因为二叉树中的最后一个非叶结点存储在 中,所以关键字最大记录的存储范围为 。

解

B
假设我们有一个包含7个节点的完全二叉树：

      1
    /   \
   2     3
  / \   / \
 4   5 6   7 

• n = 7, 表示树中共有7个节点。
• = = 3, 表示最后一个非叶节点的索引应该是3。
  观察这棵树，节点3拥有两个子节点（节点6和节点7），它确实是最后一个拥有子节点的节点，也就是最后一个非叶节点。 这证实了 的计算结果。
  我们再来看一个例子，一个包含6个节点的完全二叉树：

      1
    /   \
   2     3
  / \   / 
 4   5 6   

• n = 6, 表示树中共有6个节点。
• = = 3, 表示最后一个非叶节点的索引应该是3。
  观察这棵树，节点3拥有一个子节点（节点6），它依然是最后一个拥有子节点的节点，也就是最后一个非叶节点。 这也证实了 的计算结果