python数据结构之树（3）—— 哈夫曼树

python数据结构之树（3）—— 哈夫曼树

入门小菜鸟，希望像做笔记记录自己学的东西，也希望能帮助到同样入门的人，更希望大佬们帮忙纠错啦~侵权立删。

目录

一、哈夫曼树的概念

1、背景定义

2、哈夫曼树

二、哈夫曼编码

三、python实现哈夫曼树的构建以及哈夫曼编码

1、创建一个节点

2、创建哈夫曼树

3、编码哈夫曼编码

4、具体调用

5、输出以及画图展示

 四、哈夫曼树的作用

---

一、哈夫曼树的概念

哈夫曼树也叫最优二叉树，在了解他的定义之前，我们先来看看以下这几个词的定义。

1、背景定义

路径：从树中一个节点到另一个节点间的分支构成这两个节点间的路径。

路径长度：路径上的分支数目。

树的路径长度：从树根到每一个结点的路径长度之和。在一条路径中，每经过一个结点，路径长度都要加 1，所以，如果规定根结点所在层数为1层，那么从根结点到第 k 层结点的路径长度为 k - 1 。

结点的权：给每一个结点赋予一个新的数值。

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

比如说：结点 b 的带权路径长度为 4 * 2 = 8

树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作“WPL” 。

WPL = 3 * 2 + 4 * 2 + 8 * 2 + 2 * 2 + 5 * 2 + 7 * 2 = 58

2、哈夫曼树

当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵二叉树时，如果构建的这棵二叉树的带权路径长度最小，那么这棵树就是哈夫曼树。

在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则：权重越大的结点离树根越近。

构建哈夫曼树的方法：

（1）在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；

（2）在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；

重复（1）和（2），直到所有结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

注意：为了让得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。

---

二、哈夫曼编码

简单来说，哈夫曼编码是通过哈夫曼树来构造的编码。

编码过程：

（1） 利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；
（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。

---

三、python实现哈夫曼树的构建以及哈夫曼编码 1、创建一个节点

一个节点需要有对应的名字编号（叶子节点才有，就是我们要编码的那些才有，其余为None）；节点权重，节点的左右孩子。

class Node():
    def __init__(self,name = None,weight = None):
        self.name = name #节点的名字编号
        self.weight = weight #节点的权重
        self.lchild = None #节点的左孩子
        self.rchild = None #节点的右孩子

2、创建哈夫曼树

首先创建叶子节点列表，然后循环 *** 作叶子节点列表：对他们的权重进行排序；

取出权重最小的两个组成新的二叉树，该二叉树的根节点的权值为这两个节点权值之和；

然后将这两个节点分别从叶子列表中取出赋给这个根节点的左右孩子，然后这个根节点成为新的叶子节点，进入列表；

直至叶子列表中剩下最后一个节点则跳出循环。

跳出循环后这棵哈夫曼树就构建好了，根节点就是叶子列表的第一个。

初始创建self.code用于保存每个叶子节点的Haffuman编码,range的值只需要不小于树的深度就行。

class Huffmantree():
    #初始化
    def __init__(self,name_weight):
        self.leaf = [Node(x[0],x[1]) for x in name_weight] #创建叶子节点列表
        while len(self.leaf) != 1:
            self.leaf.sort(key=lambda x:x.weight,reverse=True) #对他们的权重从大到小排个序
            node = Node(weight=(self.leaf[-1].weight+self.leaf[-2].weight)) 
            #将最小的两个节点组成一棵新的二叉树，对应的两个节点的权重之和赋给新二叉树的根
            node.lchild = self.leaf.pop(-1)
            node.rchild = self.leaf.pop(-1)
            #以上两个pop *** 作从叶子节点列表取出这两个权值最小的作为新二叉树的根的两个孩子
            self.leaf.append(node) #叶子节点列表添上这个新二叉树的根
        self.root=self.leaf[0] #根节点
        self.code = list(range(5))
        #self.code用于保存每个叶子节点的Haffuman编码,range的值只需要不小于树的深度就行

3、编码哈夫曼编码

左0右1，将编码不断地填入self.code[i]

    def getcode(self,tree,length = 0):
        if not tree: #没有树的话直接退出
            return
        elif tree.name: #如果是对应的叶子节点就输出编码
            print(tree.name + "的编码是：")
            for i in range(length):
                print(self.code[i])
            return
        #处理左孩子
        self.code[length]=0
        self.getcode(tree.lchild,length+1)
        #处理右孩子
        self.code[length]=1
        self.getcode(tree.rchild,length+1)

4、具体调用

charweights=[('a',5),('b',4),('c',3),('d',8),('f',15),('g',2)]
tree=Huffmantree(charweights)
tree.getcode(tree.root)

5、输出以及画图展示

---

 四、哈夫曼树的作用

为了进行哈夫曼编码，哈夫曼编码可以进行无损压缩。

---

欢迎大家在评论区批评指正，谢谢大家~