有数据WG={3,2,4,5,1}, (1)画出所构建的Huffman 树; (2)所建Huffman 树的树高是多少? (3)求所建Huffman 树的带权路径长度WPL。
时间: 2023-08-31 16:29:08 浏览: 70
### 回答1:
好的,请问您想了解什么关于Huffman树的相关知识呢?
1. 关于Huffman树的构建:
对于给定的一组数据 WG={3,2,4,5,1},Huffman树的构建过程如下:
首先,将所有的数据结点看作是一棵只有叶子节点的树。
然后,将这些叶子节点按照它们的权值大小从小到大进行排序,然后取出权值最小的两个点作为一组。以它们的权值之和作为它们的父节点的权值,并且用这个新的点来代替这两个节点。
然后,在剩下的点中,找到剩余的两个最小值,将它们作为一组,创建一个新节点,设置该节点为它们的父节点,权值为这两个节点的权值之和。
重复上述步骤,直到所有的节点都被合并为一棵树,这棵树就是Huffman树。
因此,在这个例子中,根据构造规则,我们可以得到如下Huffman树:
15
/ \
7 8
/ \ /
3 4 5
2. 构建的Huffman树的树高是多少?
树高指的是从根节点到叶子节点的最长路径长度,因此我们可以看到,在这个例子中,从根节点到最深的叶子节点的路径长度为3,因此构建的Huffman树的树高是3。
3. 求构建的Huffman树的带权路径长度WPL。
带权路径长度是指,每个叶节点到根节点的路径长度乘以该叶节点的权值之和。因此,在这个例子中,我们计算每个叶子节点到根节点的路径的长度和权值的乘积,并将它们相加得到该Huffman树的带权路径长度。计算公式如下:
WPL = 3*1 + 4*2 + 5*2 + 7*1 + 8*1 = 28
因此,我们得出了构建的Huffman树的带权路径长度是28。
### 回答2:
(1)根据给定的数据WG={3,2,4,5,1},我们可以构建Huffman树。首先,将这些数值分别作为叶子节点,根据每个节点的权重值(出现频率)构建Huffman树。具体步骤如下:
首先,找出权重值最小的两个节点。根据数据WG,可以得到1和2两个节点。
将这两个节点合并,形成一个新节点,其权重值为1+2=3。
再次找出权重值最小的两个节点。根据数据WG,可以得到3和3两个节点。
将这两个节点合并,形成一个新节点,其权重值为3+3=6。
继续上述步骤,最终可以构建出Huffman树。其中,叶子节点对应的数值即为数据WG。
以下为所构建的Huffman树:
24
/ \
/ \
12 12
/ \ / \
/ \ / \
6 6 3 3
/ \ / \
/ \ / \
3 3 2 1
(2)所建Huffman树的树高即为从根节点到叶子节点的最长路径。根据构建的Huffman树,可以看出树高为3。
(3)求所建Huffman树的带权路径长度WPL。带权路径长度是指叶子节点的权重值与其到根节点的路径长度的乘积之和。根据构建的Huffman树,可以得到WPL=3*2 + 3*2 + 6*2 + 6*2 + 12*3 = 12 + 12 + 12 + 12 + 36 = 84。所以所建Huffman树的带权路径长度为84。
### 回答3:
(1) 根据给定的数据 WG={3,2,4,5,1},我们可以根据Huffman算法来构建Huffman树。首先,将数据按照权值从小到大进行排序:{1, 2, 3, 4, 5}。然后,选取权值最小的两个节点进行合并,并将合并后的节点权值为这两个节点的权值之和。重复这个步骤,直到只剩下一个节点,这个节点就是Huffman树的根节点。
具体步骤如下:
1. 将排序后的节点依次画成一个森林。
Step 1: {1} {2} {3} {4} {5}
2. 合并权值最小的两个节点,并将合并后的节点权值标记为合并前两个节点的权值之和。
Step 2: {1} {2} {3} {4, 5}
3. 重复步骤2,直到只剩下一个节点。
Step 3: {1} {2, 3} {4, 5}
Step 4: {1, 2, 3} {4, 5}
Step 5: {1, 2, 3, 4, 5}
4. 最后的Huffman树如下所示:
1, 2, 3, 4, 5
/ \
1, 2, 3 4, 5
/ \
1 2
(2) 所建Huffman树的树高为2。
(3) 求所建Huffman树的带权路径长度(WPL)。带权路径长度是指每个叶子节点到根节点的路径长度乘以该节点的权值之和。根据上面构建的Huffman树,我们可以计算出每个叶子节点的路径长度和权值,并进行相乘再相加,即可得到WPL。
节点 路径长度 权值 权值*路径长度
1 2 1 2
2 1 2 2
3 1 3 3
4 2 4 8
5 2 5 10
带权路径长度(WPL)=2+2+3+8+10=25。