哈夫曼编码（参考实验指导书相关内容） （1）二叉树结点定义 （2）创建二叉链表节点 （3）哈夫曼树结点定义 （4）采用前序遍历递归方法求出叶子结点的编码 （5）通过遍历哈夫曼树输出哈夫曼编码

哈夫曼编码是一种基于频率的有损数据压缩技术，用于构建最优的前缀码。以下是关于哈夫曼编码的一些关键部分：

（1）二叉树结点定义：在哈夫曼树的构建过程中，每个结点通常表示一个字符及其出现的频率。结点由两个属性组成：一个字符（通常是小写字母、数字或其他符号），以及与其关联的频率值。这个结构可以简单地定义为一个包含字符和频率的键值对。

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

（2）创建二叉链表节点：为了方便后续操作，比如合并频率最小的结点，我们使用了一个特殊的二叉链表。这种链表的结点也包括字符和频率，并连接到左和右子节点，同时增加了一个`parent`指针链接到其父节点。

class HuffmanTreeNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
        self.parent = None

（3）哈夫曼树结点定义：在实际的哈夫曼树中，结点是带权路径长度（WPL）最短的二叉树结点，这通常需要动态构建。哈夫曼树的根结点没有父节点（parent=None），其他的结点都有一个指向父节点的引用。

（4）前序遍历法求叶节点编码：当我们完成哈夫曼树的构建后，通过前序遍历（根-左-右）的方式给每一个叶子节点分配编码。因为每次合并都是将频率最低的两棵树合并成一个新的树，所以从左子节点开始记录序列，直到遇到非叶子节点。

（5）遍历哈夫曼树输出哈夫曼编码：从根节点出发，对于每个字符，沿路径向左走代表0，向右走代表1。当到达叶子节点时，就得到该字符的哈夫曼编码。整个过程可以是迭代的，也可以递归实现。