Python-三叉树实现三元huffman编码前言什么是huffman编码举个栗子话不多说，直接上代码运行结果截图关于为什么要取余的问题最后参考帖子
前言
上信息论的课，讲到了huffman编码，然后这章的实验内容，就是实现一个三元的huffman编码，编译一段文本，并计算平均最短编码长度以及编码效率。
自己想到了用N元树来做这个问题，然后借鉴了社区一些兄长二叉树的文章（借鉴过程有些曲折，后面会附上链接，这也是为啥想自己发帖总结一下的原因）。
总的来说，各有所长，在下融合取长补短了一些，并且推到了三叉树（当然推广来说N元都是可以实现的），注释会写的尽量详细，方便大家细品！
什么是huffman
在信息论领域，哈夫曼编码（Huffman Coding）是一种高效的数据压缩算法，它通过构建特殊的二叉树（哈夫曼树）来为输入符号分配最短的编码，以达到最小化平均编码长度的目的。在Python中，我们可以利用数据结构来实现这一编码方式。然而，这里的"三元哈弗曼编码"指的是对哈夫曼编码的一种扩展，即使用三叉树（Ternary Tree）代替传统的二叉树进行编码。
在传统的哈夫曼编码中，我们通常选取概率最低的两个节点合并成一个新的节点，新节点的概率是这两个节点的概率之和，新节点的左孩子是概率较低的节点，右孩子是概率较高的节点。而在三元哈夫曼编码中，我们每次选取概率最低的三个节点，形成一个新的三叉节点，其概率是这三个节点的概率之和，这三个孩子分别对应概率最低、次低和最高。
以下是实现三元哈夫曼编码的基本步骤：
1. 我们需要收集输入文本的每个字符及其出现频率，构建一个字典，如`p_dict`，其中键是字符，值是对应的频率。
2. 创建一个队列`Q`，并将其填充为包含所有字符节点的列表，按频率降序排列。
3. 接下来，我们将重复以下过程，直到队列为空：
- 弹出队列中概率最低的三个节点。
- 创建一个新的三叉节点，其概率是这三个节点的概率之和，这三个节点分别作为新节点的左、中、右孩子。
- 将新节点添加回队列。
4. 这个过程会构建出一个哈夫曼树，从根节点到每个叶子节点的路径就构成了字符的哈夫曼编码。编码时，从根节点到左孩子记为0，到中孩子记为1，到右孩子记为2。
5. 遍历哈夫曼树，为每个叶子节点记录其路径，即得到每个字符的哈夫曼编码。
在Python代码中，可以通过定义一个`treenode`类表示树节点，包括节点的值、频率、以及左右孩子。另外，还需要一个队列类`Nodequeue`来管理节点，并实现添加和删除节点的功能，确保队列始终按概率降序排列。
在提供的代码片段中，可以看到`create_noteQ`函数用于初始化队列，`addQ`函数用于将新的节点插入队列并保持降序，而`popNode`函数则用于从队列中弹出概率最低的节点。这些辅助函数帮助构建和维护哈夫曼树。
需要注意的是，三元哈夫曼编码虽然能够减少编码的复杂性，但可能会导致更复杂的树结构，且在实际应用中不如二叉哈夫曼编码常见。不过，对于特定问题，如特定的字符分布，三元或其他N元哈夫曼编码可能会提供更优的编码效率。
总结起来，三元哈夫曼编码是哈夫曼编码的一种变体，利用三叉树结构优化编码过程。在Python中，通过创建树节点类和队列类，可以实现三元哈夫曼编码的构建和字符编码的生成。虽然这种方法可能不常用，但理解和实现它可以帮助深入理解数据压缩和哈夫曼编码的工作原理。
