哈夫曼树和哈夫曼编码

哈夫曼树和哈夫曼编码,第1张

哈夫曼树和哈夫曼编码 什么是哈夫曼树

哈夫曼树,又称最优二叉树,是带权路径长度最短的数,可用来构造最优编码,用于信息传输,数据压缩等方面,是一种应用广泛的二叉树。
首先介绍一些与哈夫曼树相关的基本概念:

  1. 路径:书中一个节点到另一个节点之间的分值序列,构成两个节点间的路径。
  2. 路径长度:路径上分支的条数称为“路径长度”。
  3. 树的路径长度:从树根到每个节点的路径长度之和成为“数的路径长度”。
  4. 节点的权:给树中节点赋予一个数值,该数值成为“节点的权”。
  5. 带权路径长度:节点到树根间的路径长度与节点的权的乘积,称为该节点的“带权路径长度”。
  6. 数的带权路径长度:树中所有叶子节点的带权路径长度之和,称为“树的带权路径长度”,通常记为WPL、

由于哈夫曼树是一颗二叉树,可以用前面介绍的二叉树的存储方法,但哈夫曼树有其自己的特点,因此一般采用如下介绍的静态三叉链表来存储
哈夫曼树的建立算法中,哈夫曼树没有度为1的结点,这类二叉树又称正则二叉树。对于n个叶子的哈夫曼树,算法中构建了n-1个度为2的结点,所以哈夫曼树共有2n-1个节点,可以存储在一个大小为2n-1的一位数组中。

哈夫曼树的建立过程见上图:
由于每个节点急需要孩子的信息,又需要双亲的信息,因此每个节点可设计成如下所示的三叉链表节点结构:

WeightParentLchildRchild

其中,Weight为节点的权值,Parent为双亲节点在数组中的下标,Lchild为左孩子节点在数组中的下标,Rchild为右孩子节点在数组中的下标。
其中哈夫曼树的静态三叉链表存储结构,其类型定义如下:

#define N 30
#define M * N - 1
typedef struct {
	int Weight;
	int Parent, Lchild, Rchild;
} HTNode, HuffmanTree[M +1];

静态三叉链表数组中,前n个元素存储叶子节点,后n-1个元素村塾不断生成的新节点即度为2的分支节点,最后一个元素将是哈夫曼树的根节点。
哈夫曼算法的实现如下可分为初始化和构建哈夫曼树两部分。

  1. 初始化所有节点
  2. 构造新节点
    代码如下:
void CrdtdHuffmanTree (HuffmanTree ht, int w[], int n) {
	m = 2* n - 1;
	for (int i = 1; i < n; i++) {
		ht[i].Weight = w[i];
		ht[i].Parent = 0;
		ht[i].Lchild = 0;
		ht[i].Rchild = 0;
 	}	
	
	for (int i = n + 1; i <= m; i++) {
		ht[i].Weight = 0;
		ht[i].Parent = 0;
		ht[i].Lchild = 0;		
		ht[i].Rchild = 0;
	}

	for (int i = n +1; i <= m; i++) {
		//在ht的前i-1项中选双亲为0且权值最小的两节点s1, s2
		select(ht, i - 1, &s1, &s2);
		ht[i].Weight = ht[s1].Weight + ht[s2].Weight;//创建新节点,赋权值	
		//赋新节点左右孩子指针
		ht[i].Lchild = s1;
		ht[i].Rchild = s2;
		//改s1, s2的双亲指针
		ht[s1].Parent = i;
		ht[s2].Parent = i;
	}
}

哈夫曼编码是最优二进制前缀编码,其算法实现如下:

  1. 构造哈夫曼树
  2. 在哈夫曼树上求各叶子节点的编码


例如,上图哈夫曼树中E的哈夫曼编码为:01,A的哈夫曼编码为:000, B的哈夫曼编码为:001, C的哈夫曼编码为100, D的哈夫曼编码为:101, F的哈夫曼编码为:11

代码如下:(下方代码是从叶子节点逆向走到根节点的方式获取哈夫曼编码)

void CrtHuffmanCodel (HuffmanTree ht, HuffmanCode hc, int n) {
	//从叶子到根,逆向求各叶子节点的编码
	char *cd;
	int start;
	cd = (char *) malloc (n * sizeof(char));//临时编码数组	
	cd[n - 1] = '';			//从后向前诸位求编码,首先放编码结束符
	//从每个叶子开始,求相应的哈夫曼编码
	for (int i = 1; i <= n; ++i) {
		start = n - 1; c = i; p = ht[i].Parent;//c为当前节点,p为其双亲
		while (p != 0) {
			--start;
			if (ht[p].Lchild == c) cd[start] = '0';//左分支得‘0’
			else cd[start] = '1';
			//上溯一层
			c = p;
			p = ht[p].parent;
		}
		hc[i] = (char *) malloc ((n - start) * sizeof(char));//动态申请编码串空间
		strcpy(hc[i], &cd[start]);//复制编码
	}
	free(cd);
}

以上代码就可以从哈夫曼树中获取到哈夫曼编码了。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5594276.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表(0条)

保存