首页 > 代码库 > 《大话数据结构》笔记(6-3)--树:赫夫曼树
《大话数据结构》笔记(6-3)--树:赫夫曼树
代码实现:
第六章 树:赫夫曼树
赫夫曼树定义与原理
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称作路径长度。
树的路径长度就是从树根到每一结点的路径长度之和。
对于带权的结点,结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。
假设有n个权值{w1, w2, ..., wn},构造一棵有n个叶子结点的二叉树,每个叶子结点带权wk ,每个叶子的路径长度为lk,则其中带权路径长度WPL最小的二叉树称作赫夫曼树(最有二叉树)。
赫夫曼树的构造
赫夫曼编码
若要设计长短不等的编码,则必须是任一字符的编码都不是其他编码的前缀,这种编码称作前缀编码。
《大话数据结构》笔记(6-3)--树:赫夫曼树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。