数据结构赫夫曼树
发布时间
阅读量：
阅读量
赫夫曼（Huffman）树，是一种具有最小带权路径长度的树结构。其还被称作哈夫曼树或霍夫曼树等不同译名。
若干术语
| 路径 | 由一个结点到另一个节点之间的分支所构成 |
|---|---|
| 路径长度 | 路径上的分支数目 |
| 树的路径长度 | 树根到每一结点的路径长度之和 |
| 带权路径长度 | 结点到树根之间的路径长度与结点上权的乘积 |
| 树的带权路径长度 | 树中所有叶子结点的带权路径长度之和 |
树的带权路径长度计算方法：
，其中，Wk是权值，Lk是结点到根的路径长度。
带权路径长度WPL最小的二叉树称做最优二叉树 或赫夫曼树
举例：图中的3棵二叉树，都有4个叶子结点a、b、c、d，分别带权7、5、2、4，求它们的带权路径长度？
|
| 
还没有任何评论哟~