huffma树及其应用-笔记(.)

迷南。 2022-12-27 09:25 101阅读 0赞

huffma树及其应用  
1 编码性质与最优二叉树  
1.1 前缀码:某个前缀码不会在另一个前缀码中出现,否则会造成歧义.  
1.2 编码长度:  
如果可以,我把带权路径长度理解成:结点的权值为结点被访问的次数,  
那么结点的带权路径长度就是访问这个节点总共走了多长的路: 权值(次数) \* 每次的长度  
二叉树的带权路径长度 = ∑(叶子结点的权值 与 该节点的路径长度的乘积)  
1.3 最优编码  
即带权路径长度的最小值  
2 huffman树  
2.1 huffman树的构造原理  
核心策略是让权值大的节点路径短,权值小的结点路径长  
2.1.1 最终目标是将所有字符结点合并到一棵二叉树中,先合并者深, 路径长  
2.1.2 先找两个未合并的权值最小的结点,合并成一个新节点  
2.1.3 新节点权值设为其子结点之和,忽略被合并结点  
2.1.4 重复上述过程,直到所有节点都归入一棵树  
2.2 huffman树不唯一:因为在选取最小的两个结点的时候,不同的树选取的结点可能不同  
2.3 huffman树编码的算法实现  
选择树的顺序存储结构:n个字符则huffman树必然有 2\*n-1 个结点  
(n0 = n; n0 = n2 + 1; N = n0 + n2 = 2 \* n - 1)  
编码方案存储: 对应一个数组,各元素是一字符串地址

typedef struct 
    {
        
    	unsigned int weight;
    	unsigned int lchild, rchild, parent;
    }HTNode;
    typedef HTNode * HuffmanTree;
    typedef char * HuffmanCode;
    Status HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
    {
        
    	if (n <= 1) return ERROR;
    	m = 2 * n - 1;
    	//0号空间不存放结点
    	HT = new HTNode[m + 1];
    	//初始化二叉树-开始
    	for (p = HT + 1, i = 1; i <= n; p++, w++, i++)
    	{
        
    		p->weight = *w;
    		p->lchild = 0;
    		p->rchild = 0;
    		p->parent = 0;
    	}
    	for (i = n + 1; i <= m; i++, p++)
    	{
        
    		p->weight = 0;
    		p->lchild = 0;
    		p->rchild = 0;
    		p->parent = 0;
    	}
    	//初始化二叉树-结束
    	
    	for (i = n + 1; i <= m; i++)
    	{
        
    		//HT[1...i-1]中找未合并(双亲结点未0)的自耦夏普的两个节点
    		Select(HT, i-1, s1, s2);
    		
    		HT[s1].parent = i;
    		HT[s2].parent = i;
    		
    		HT[i] = HT[s1].weight + HT[s2].weight;
    		HT.lchild = s1;
    		HT.rchild = s2;
    	}
    	
    	HC = (HuffmanCode)malloc(sizeof(n + 1) * sizeof(char *));
    	//n个字符的huffman编码最大长度(无限大无意义)是n
    	cd = (char*)malloc(n * sizeof(char));
    	cd[n-1] = '\0';
    	for (i = 1; i <= n; i++)
    	{
        
    		start = n-1;
    		for (c = i, f = HT[c].parent; f != 0; c = f, f = HT[f].parent)
    			if (HT[f].lchild == c)
    				cd[--start] = '0';
    			else 
    				cd[--start] = '1';
    		HC[i] = (char*)malloc((n-start) * sizeof(char));
    		strcpy(HC[i], &cd[start]);
    	}
    	free(cd);
    }

3 总结与推广