【数据结构】哈夫曼树与哈夫曼编码

左手的ㄟ右手 2024-04-17 05:52 105阅读 0赞

### 定义 ###

**带权路径长度（WPL）**：设二叉树有n个叶子结点，每个叶子结点带有权值 w k w\_k wk，从根节点到每个叶子结点的长度为 l k l\_k lk，则每个叶子结点的带权路径长度之和就是： W P L WPL WPL= ∑ k = 1 n \\sum\_\{k=1\}^\{n\} ∑k=1n

最优二叉树或哈夫曼树：WPL最小的二叉树

### 哈夫曼树的构造 ###

每次将权值最小的两棵二叉树合并  
如何选取两个最小的元素？利用堆

typedef struct TreeNode *HuffmanTree;
    struct TreeNode{
    	int Weight;
    	HuffmanTree Left, Right;
    }
    HuffmanTree Huffman( MinHeap H )
    { 
    	/* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
    	int i; HuffmanTree T;
     	BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/
     	for (i = 1; i < H->Size; i++) { /*做H->Size-1次合并*/
     		T = malloc( sizeof( struct TreeNode) ); /*建立新结点*/
     		T->Left = DeleteMin(H);
     		/*从最小堆中删除一个结点，作为新T的左子结点*/
     		T->Right = DeleteMin(H);
    		 /*从最小堆中删除一个结点，作为新T的右子结点*/
    		 T->Weight = T->Left->Weight+T->Right->Weight;
     		/*计算新权值*/
    		 Insert( H, T ); /*将新T插入最小堆*/
     }
     T = DeleteMin(H);
     return T;

### 哈夫曼树的特点 ###

1.  没有度为1的结点
2.  n个叶子结点的哈夫曼树共有2n-1的结点
3.  哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
4.  对同一组权值，是否存在不同构的两个哈夫曼树？ 有可能  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

### 哈夫曼编码 ###

> 给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？
> 
> \[例\]  
> 假设有一段文本，包含58个字符，并由以下7个字符构：a，e，i，s，t，空格（sp），换行（nl）；这7个字符出现的次数不同。如何对这7个字符进行编码，使得总编码空间最少？

【分析】  
（1）用等长ASCII编码：58 ×8 = 464位；  
（2）用等长3位编码：58 ×3 = 174位；  
（3）不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则可以编码长些？

> 怎么进行不等长编码？ 如何避免二义性？

**前缀码prefix code**：任何字符的编码都**不是**另一字符编码的前缀  
可以无二义地解码

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

> 怎么构造一颗编码代价最小的二叉树？  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]  
> 代价最小且不会有二义性

#### 参考资料 ####

浙大数据结构MOOC

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/e4d14fd5a3a34f77892761031b47d071.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/c5c69897ecba4ea2b3cda3d2726a7061.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/5744373684124a5eb8f2a69b7591a237.png