最优二叉树（哈夫曼树）

golang工程师应该会的数据结构与算法 /

@author 汪春波

基本的概念。

树的路径长度：是从树根到树中每一结点的路径长度之和，在结点数目相同的二叉树中，完全二叉树的路径长度最短；

权：在一些应用中会赋予树中结点一个有意义的实数，这个数字称为权；其实就是访问频率。

带权路径长度：结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度；

树的带树路径长度（树的代价）：所有叶结点的带树路径长度之和。

最优二叉树（哈夫曼树）

假设有一组权值 5，29，7，8，14，23，3，11
请尝试构造哈夫曼树。

每次取出最小的两个作为孩子节点，相加得出父节点，来推出得到哈夫曼树。

最优二叉树（哈夫曼树）

最后得出：
最优二叉树（哈夫曼树）

因为我们这里可以看到得出的节点，都有对应的权。

权越大，距离跟越近。

本文章首发在 LearnKu.com 网站上。

Markdown 文本

版主 2.5k 声望

司机 @ 欣昊玉

创业给我教学和编程带来了洞见，期待与您共同成长。