英文:
I don't understand how to draw Huffman coding tree
问题
如果我理解正确,哈夫曼树由两个最小频率的元素开始构建,并持续进行。例如,字母A、B、C、D、E、F的频率分别为15、40、60、10、30、45(总和为200)。
首先,D会走向左侧,A走向右侧,形成叶子节点。
其次,E走向右侧,这是让我感到困惑的地方。
第三步,下一个最低频率的字母是B。所以我认为B应该比当前总和(55)小,因此应该走向左侧,如下所示:当前树
但答案是要创建一个新的叶子节点,其中包括B和F,然后C走向55树的左侧。结果如下图所示:答案
我不明白为什么需要创建一个新的叶子节点来包含B和F。有人能解释吗?
我预期B字母应该位于55节点的左侧,使总和达到95,接下来是F(45)走向左侧,最后是C(60)走向左侧。但答案树不是我预期的样子。按照什么标准创建新树(如答案图片中的B + F)?
英文:
If I'm correct, Huffman Tree is made with two minimum frequencies and keeps going.
For example, letters A,B,C,D,E,F has frequencies of 15, 40, 60, 10, 30, 45 (200 total).
first, D would go left and A on right to make leaf nodes.
second, E goes right
this is where it confuses me.
third, the next lowest frequencie letter is B. So I thought B is smaller than the current total(55) and therefore goes on the left like this:Current Tree
But the answer is to draw a new leaf nodes with B and F and then C goes to the left of 55 tree.
Resulting this drawing:answer
I dont understand why B and F needs to make a new leaf node. Can someone explain?
I expected the B letter to go on the left of 55 node which makes the total of 95, next F(45) goes to left, lastly C(60) on the left. but the answer tree is not drawn as what i expected it to be. by what standards does a new tree (like B + F in the answer pic) is made?
答案1
得分: 1
开始使用按频率排序的节点列表:
D(10) A(15) E(30) B(40) F(45) C(60)
然后将频率最低的两个节点 (D + A)
结合在一起,创建一个新节点,其频率为它们的和:
D+A(25) E(30) B(40) F(45) C(60)
在合并两个节点后,新节点 (DA + E)
应插入列表中的适当排序位置:
B(40) F(45) DA+E(55) C(60)
始终合并具有最低频率的两个节点 (B + F)
,并保持列表排序:
DAE(55) C(60) B+F(85)
继续合并两个最低频率的节点 (DAE + C)
:
BF(85) DAE+C(115)
直到只剩下一个节点 (BF + DAEC)
:
BF+DAEC(200)
创建新节点时,例如 DA+E
,节点 DA
是节点 DAE
的左子节点,节点 E
是右子节点。
英文:
Start with a list of nodes sorted by frequency:
D(10) A(15) E(30) B(40) F(45) C(60)
Then combine the two nodes with the lowest frequency (D + A)
to create a new node whose frequency is the sum:
D+A(25) E(30) B(40) F(45) C(60)
After combining two nodes, the new node (DA + E)
should be inserted in the list at the proper sorted position:
B(40) F(45) DA+E(55) C(60)
Always combine the two nodes with the lowest frequencies (B + F)
, keeping the list sorted:
DAE(55) C(60) B+F(85)
Continue combining the two lowest frequencies (DAE + C)
:
BF(85) DAE+C(115)
until there's only one node (BF + DAEC)
:
BF+DAEC(200)
When creating a new node like DA+E
, the node DA
is the left child of node DAE
, and the node E
is the right child.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论