单选题 下面关于哈夫曼树的叙述中,正确的是______。
【正确答案】 C
【答案解析】哈夫曼树是一种特殊的二叉树,但它不是完全二叉树,也不是平衡二叉树,给出n个权值{w 1 ,w 2 ,…,w n }构造一棵具有n个叶子节点的哈夫曼树的方法如下。
第1步,构造n个只有根节点的二叉树集合F={T 1 ,T 2 ,…,T n },其中每棵二叉树T i 的根节点带权为w i (1≤k≤n)。
第2步,在集合F中选取两棵根节点的权值最小的二叉树作为左右子树,构造一棵新的二叉树,令新二叉树根节点的权值为其左右子树上根节点的权值之和。
第3步,在F中删除这两棵二叉树,同时将新得到的二叉树加入到F中。
第4步,重复第2步和第3步,直到F只含有一棵二叉树为止,这棵二叉树便是哈夫曼树。
综上所述,我们可以知道哈夫曼树中权值最小的两个节点互为兄弟节点。