题目
已知字符及其权值如下：A(6)，B(7)，C(1)，D(5)，E(2)，F(8)，给出构造哈夫曼树[1]和哈夫曼编码[2]的过程，并计算带权路径长度。
已知字符及其权值如下：A(6)，B(7)，C(1)，D(5)，E(2)，F(8)，给出构造哈夫曼树[1]和哈夫曼编码[2]的过程，并计算带权路径长度。
题目解答
答案
假设有n个权值则构造出的哈夫曼树有n个叶子结点[3]。n个权值分别设为ω1ω2…ω2则哈夫曼树的构造规则为： (1)将ω1ω2…ωn看成是有n棵树的森林(每棵树仅有一个结点)。如下图所示。
(2)在森林中选出两个根结点的权值最小的树合并作为一棵新树的左、右子树且新树的根结点权值为其左、右子树根结点权值之和。如下图所示。
(3)从森林中删除选取的两棵树并将新树加入森林。如下图所示。
(4)重复(2)、(3)步直到森林中只剩一棵树为止该树即为所求得的哈夫曼树。如下图所示。
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为ω1,ω2,…,ω2,则哈夫曼树的构造规则为：(1)将ω1,ω2,…,ωn看成是有n棵树的森林(每棵树仅有一个结点)。如下图所示。(2)在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和。如下图所示。(3)从森林中删除选取的两棵树,并将新树加入森林。如下图所示。(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。如下图所示。
(2)在森林中选出两个根结点的权值最小的树合并作为一棵新树的左、右子树且新树的根结点权值为其左、右子树根结点权值之和。如下图所示。(3)从森林中删除选取的两棵树并将新树加入森林。如下图所示。 (4)重复(2)、(3)步直到森林中只剩一棵树为止该树即为所求得的哈夫曼树。如下图所示。假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为ω1,ω2,…,ω2,则哈夫曼树的构造规则为：(1)将ω1,ω2,…,ωn看成是有n棵树的森林(每棵树仅有一个结点)。如下图所示。
(2)在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和。如下图所示。(3)从森林中删除选取的两棵树,并将新树加入森林。如下图所示。(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。如下图所示。解析
步骤 1：构造哈夫曼树
1. 将字符及其权值看成是有6棵树的森林（每棵树仅有一个结点）。
2. 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和。
3. 从森林中删除选取的两棵树，并将新树加入森林。
4. 重复步骤2和3，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
步骤 2：构造哈夫曼编码
1. 从哈夫曼树的根结点开始，向左子树方向走，赋值为0；向右子树方向走，赋值为1。
2. 重复步骤1，直到到达叶子结点，此时的路径上的0和1的序列即为该叶子结点的哈夫曼编码。
步骤 3：计算带权路径长度
1. 带权路径长度（WPL）=所有叶子结点的权值乘以它们的路径长度之和。
2. 计算每个叶子结点的路径长度，乘以权值，然后求和。
1. 将字符及其权值看成是有6棵树的森林（每棵树仅有一个结点）。
2. 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和。
3. 从森林中删除选取的两棵树，并将新树加入森林。
4. 重复步骤2和3，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
步骤 2：构造哈夫曼编码
1. 从哈夫曼树的根结点开始，向左子树方向走，赋值为0；向右子树方向走，赋值为1。
2. 重复步骤1，直到到达叶子结点，此时的路径上的0和1的序列即为该叶子结点的哈夫曼编码。
步骤 3：计算带权路径长度
1. 带权路径长度（WPL）=所有叶子结点的权值乘以它们的路径长度之和。
2. 计算每个叶子结点的路径长度，乘以权值，然后求和。