构建哈夫曼树与哈夫曼编码

"这篇资源主要介绍了哈弗曼树和哈弗曼编码的创建方法，提供了相关的C++代码实现。在创建哈弗曼树的过程中，通过将权重最小的节点合并来构造树形结构，最终得到一棵最优二叉树。在创建哈弗曼编码时，根据哈弗曼树的结构，自底向上遍历并分配0和1，形成具有唯一性的编码。" 哈弗曼树（Huffman Tree）是一种特殊的二叉树，也称为最优二叉树，通常用于数据压缩。它的构建基于哈弗曼编码（Huffman Coding），这是一种变长编码方式，可以对出现频率不同的字符进行编码，使得频率高的字符编码较短，频率低的字符编码较长，从而达到高效压缩数据的目的。 创建哈弗曼树的过程如下： 1. 初始化：首先，为每个字符创建一个节点，节点包含字符本身、对应的权重以及父节点、左子节点和右子节点的引用。在这个例子中，使用`htnode`结构体表示每个节点，其中`weight`存储权重，`parent`、`lchild`和`rchild`分别存储父节点和子节点的索引。 2. 合并过程：将所有节点放入一个队列（这里用数组模拟），并不断取出两个权重最小的节点合并为一个新的节点，新节点的权重是两者的和，且这两个节点作为新节点的左右子节点。重复此过程直到队列只剩下一个节点，即为哈弗曼树的根节点。 3. 创建哈弗曼树的函数`createht()`中，首先初始化了所有节点的父节点为-1，表示它们尚未被合并。然后从27个节点开始（可能是因为26个英文字母加上一个结束符），每次合并两个最小权重的节点，直到所有节点都被合并成一个树。 创建哈弗曼编码的过程： 1. 依据哈弗曼树的结构，从叶子节点（原始字符节点）开始，沿着树向根节点遍历。如果经过左子节点，则在编码中添加0；如果经过右子节点，则添加1。当到达根节点时，编码完成。 2. 在`createhcode()`函数中，遍历所有的字符节点，为每个字符生成编码。通过跟踪当前节点的父节点，判断是从左子节点还是右子节点到达该节点，以此来决定编码的0或1。这个过程自底向上进行，直到遇到根节点，此时编码完整。 3. 结果编码存储在`hcode`结构体中，包括字符的编码字符串`cd`和编码的起始位置`start`。 4. 最后，`encode()`函数用于显示给定字符串的哈弗曼编码。 以上就是哈弗曼树和哈弗曼编码的基本概念以及如何用C++实现它们。这个过程的关键在于理解和利用节点的权重关系构造出最优二叉树，进而生成唯一的变长编码，实现高效的数据压缩。