假设用于通讯的电文仅由6个字母A,B,C,D,E,F组成,各个字母在电文中出现的频率分别为6,3, 12, 10, 7, 5,试为这6个字母设计哈夫曼树。(构建新二叉树时,要求新 二叉树的左子树根的权值小于等于右子树根的权值。)
假设用于通讯的电文仅由6个字母A,B,C,D,E,F组成,各个字母在电文中出现的频率分别为6,3, 12, 10, 7, 5,试为这6个字母设计哈夫曼树。(构建新二叉树时,要求新 二叉树的左子树根的权值小于等于右子树根的权值。)
【正确答案】:

所构建的哈夫曼树为:


【题目解析】:构造哈夫曼树的方法:① 将给定的权值按照从小到大排列成{W1,W2,…,Wm},并且构造出树林F={Tl,T2,…,Tm}。此时,其中的每棵树Ti (1≤i≤m)为左、右子树均为空的二叉树,二叉树的根结点的权值为Wi 。② 把F中树根结点的权值最小的两棵二叉树T1和T2合并为一棵新的二叉树T(T的左子树为T1,右子树为T2),并令T的根结点的权值为T1和T2的根结点的权值之和,然后将T按其根结点的权值大小依次加入到树林F中。同时,从F中删去T1和T2这两棵二叉树。③ 重复步骤②,直到构造成一棵哈夫曼树。
Top