下面关于哈夫曼树的叙述中,正确的是(58)。A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树

Question

下面关于哈夫曼树的叙述中，正确的是(58)。

A．哈夫曼树一定是完全二叉树

B．哈夫曼树一定是平衡二叉树

C．哈夫曼树中权值最小的两个结点互为兄弟结点

D．哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点

Answer 1

正确答案：C
解析：哈夫曼树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。具有以下特征：
  (1)当叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。即哈夫曼树不一定是完全二叉树。
  (2)在最优二叉树中，权值越大的叶子离根越近。
  (3)最优二叉树的形态不唯一，但WPL最小。
  哈夫曼树的构造：
  (1)根据给定的n个权值{w1，w2，…，wn}构造n棵二叉树的集合F={Tl，T2，…，Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；
  (2)在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右予树上根结点的权值之和。
  (3)将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
  (4)重复(2)和(3)直到F中只含一棵树为止，这棵树就是哈夫曼树。
平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。而哈夫曼树并未要求左右两个子树的高度差的绝对值不超过1，根据其构造可知，是从上往下顺序排下来的，且左孩子结点大于父孩子结点。