哈夫曼树

几个和哈夫曼树相关的概念

路径:一个节点到另一个节点的通路

路径长度:一条路径每经过一个节点长度加1

权:给节点赋一个有意义的数值,称为节点的权

带权路径长度:根结点到该结点之间的路径长度与该结点的权的乘积,通常记为WPL


哈夫曼树

在n个带权节点构成的二叉树中,WPL最小的数就被称为哈夫曼树

在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则

那就是:权重越大的结点离树根越近


构造哈夫曼树

这些就是上学期离散的知识了

  • 在所有节点里挑两个权最小的构成二叉树,根节点的权就是这两个节点权的和
  • 把两个旧的权删去加入新的权,然后重复步骤一
  • 重复一和二

一直到最后所有的节点构成了一棵新的二叉树为止

节点结构

typedef struct {
    int weight;//权
    int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
}HTNode;

哈夫曼中的查找算法

 


哈夫曼树的实现

 


哈夫曼编码

哈夫曼编码就是在哈夫曼树的基础上构建的

这种编码方式最大的优点就是用最少的字符包含最多的信息内容

根据发送信息的内容,通过统计文本中相同字符的个数作为每个字符的权值,建立哈夫曼树

对于树中的每一个子树,统一规定其左孩子标记为 0 ,右孩子标记为 1

这样,用到哪个字符时,从哈夫曼树的根结点开始,依次写出经过结点的标记

最终得到的就是该结点的哈夫曼编码

发表评论

您的电子邮箱地址不会被公开。