数据结构-哈夫曼树和哈夫曼编码.ppt

"数据结构-哈夫曼树和哈夫曼编码" 哈夫曼树（Huffman Tree）是一种特殊的二叉树，它的特点是：有 n 个叶子结点，不存在度为 1 的结点，总的结点数为 2n-1，深度≤ n-1，形态不唯一。哈夫曼树的定义是：带权路径长度 WPL 最小的二叉树。哈夫曼树的构建算法是：根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合 F = {T1, T2, …, Tn}，然后重复选择 F 中权值最小的两棵二叉树，作为左、右子树构造新的二叉树，并置新的二叉树根结点的权值为其左、右子树根结点的权值之和，直至 F 中只含一棵树为止。 哈夫曼编码（Huffman Coding）是一种变长编码方法，即根据字符出现的频率不同，采用不同的编码长度，使得出现频率高的字符编码短，频率低的字符编码长。哈夫曼编码的特点是：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。哈夫曼编码的构建方法是：首先建立哈夫曼树，然后对边编号，求出叶子结点的路径，最后得到字符编码。 哈夫曼树和哈夫曼编码在数据压缩和信息 theory 中有着广泛的应用，例如：文本压缩、图像压缩、视频压缩等。 哈夫曼树的定义和特点： * 带权路径长度 WPL 最小的二叉树 * 有 n 个叶子结点 * 不存在度为 1 的结点 * 总的结点数为 2n-1 * 深度≤ n-1 * 形态不唯一 哈夫曼树的构建算法： 1. 根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合 F = {T1, T2, …, Tn} 2. 在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和 3. 从 F 中删去这两棵树，同时将刚生成的新树加入到 F 中 4. 重复步骤 2 和 3，直至 F 中只含一棵树为止 哈夫曼编码的特点和构建方法： * 变长编码 * 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 * 根据字符出现的频率不同，采用不同的编码长度 * 构建方法：建立哈夫曼树，对边编号，求出叶子结点的路径，得到字符编码