|
1 前言 这篇文章是对网友在文章的下的提问，做出的解答。 2 问题描述 哈夫曼树相关的基础知识。 3 哈夫曼树的定义 哈夫曼树（Huffman Tree）：是在叶子结点和权重已经知道的情况下，带权路径长度最小的二叉树，哈夫曼树也被称为最优二叉树。 路径长度：从一个结点到另一个结点多经过的边数就被称为路径长度。 树的带权路径长度（WPL）：所有叶子结点的权重*路径长度之和，就被称为书的带权路径长度。 下面我们来举个例子： 可知：从A结点到H结点经过三条边，所以路径长度是3，又因为H点的权重为4，所以H点的带权路径长度是3*4 = 12；树的带权路径长度是3*4 + 2*2 + 2*3 + 2*1 = 24。 4 构建一个哈夫曼树 由哈夫曼树的定义可知，权值越小的结点应该在越下层。 以下图四个结点为例（先将结点从小到大排好）： (1)选择两个最小的结点相加得到他们的父结点，并从结点列表中删除这两个结点，加入他们的父结点。 (2)再次选择两个最小的结点相加得到他们的父结点，并从结点列表中删除这两个结点，加入他们的父结点。 (3)重复上面的操作 5 总结 (1)哈夫曼树（Huffman Tree）： 是带权路径长度最小的二叉树 (2)树的带权路径长度（WPL）： 所有叶子结点的权重*路径长度之和，就被称为书的带权路径长度。 (3)构建哈夫曼树可以从最小的结点由最底层向上构建。 实习编辑：衡辉 稿件来源：深度学习与文旅应用实验室（DLETA） |
|
|
