问题
单项选择题
以下关于哈夫曼树的叙述,正确的是()
A.哈夫曼树一定是满二叉树,其每层结点数都达到最大值
B.哈夫曼树一定是平衡二叉树,其每个结点左右子树的高度差为-1、0或1
C.哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点
D.哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近
答案
参考答案:D
解析:
本题考查数据结构基础知识。哈夫曼树是一类带权路径长度最短的树,根据一组权值构造出来。构造过程为:
①根据给定的n个权值(w1,w2,…,wn),构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵树Ti中只有一个带权为W1的根结点,其左右子树均空。
②在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树,置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
③从F中删除这两棵树,同时将新得到的二叉树加入到F中。根据权值集合{0.25,0.30,0.08,0.25,0.12}构造的哈夫曼树如下图所示,从中可以知道,哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近。