大家都在看
哈夫曼树的构建过程
最佳答案
哈夫曼树:
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼树的构造：
假设给定的权值如下：3,5,7,8,10,15；
首先取集合中最小的两个数：3+5=8，再删除集合中3和5的值，把8放入原集合,
原集合变成:7,8,8,10,15；
8
/ \
3 5
再从7,8,8,10,15中再取2个最小的数构成一个树
15
/ \
8 7
/ \
3 5
再从8,10,15,15中再取2个最小的数构成一个树:
18
/ \
8 10
再从15,15,18中取两个最小数:15,15,构成树:
30
/ \
15 15
/ \
8 7
/ \
3 5
最后把18,30构成树(此时集合中已经没元素了，就形成了哈夫曼树):
48
/ \
30 18
/ \ / \
15 15 8 10
/ \
8 7
/ \
3 5
希望你能看懂！！
声明：知趣百科所有作品均由用户自行上传分享，仅供网友学习交流。若您的权利被侵害，请在页面底部查找“联系我们”的链接，并通过该渠道与我们取得联系以便进一步处理。