首页 计算机科学 数据结构 树

# 哈夫曼树

1. 定义
1、路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。
2、路径长度：路径的上分支的数目。
3、结点的路径长度：从根到该结点的路径长度。
4、树的路径长度：从树根到每一个结点的路径长度之和。
5、结点的权：在一些应用中，赋予树中结点的一个有某种意义实数。
6、结点的带权路径长度：从根结点到各个叶结点的路径长度与相应结点权值的乘积。
7、树的带权路径长度：所有叶结点的带权路径长度之和。
8、最优二叉树 / 赫夫曼树： 假设有 n 个权值 (w1,w2…wn)，试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为 wi ，则其中带权路径长度 WPL 最小的二叉树称作最优二叉树或赫夫曼树。

2. 存储结构
对于有 n 个叶子结点的赫夫曼树，结点总数为 2n-1 个，为实现方便，将叶子结点集 中存储在前面部分 1~n 个位置，而后面的 n－1 个位置中存储其余非叶子结点。
静态三叉链表中：weight|parent|LChild|RChild

// 用静态三叉链表实现的哈夫曼树类型定义如下：
#define N 20 /* 叶子结点的最大值。*/
#define M 2*N-1 /* 所有结点的最大值。*/
typedef struct{
	int weight ; /* 结点的权值 */
    int parent ; /* 双亲的下标 */
	int LChild ; /* 左孩子结点的下标 */
	int RChild ; /* 右孩子结点的下标 */
} HTNode, HuffmanTree[M+1]; 
/* HuffmanTree 是一个结构数组类型，0 号单元不用。 */

3. 算法实现

/* 构造哈夫曼树 ht [M+1]， w [ ] 存放 n 个权值。*/
void CrtHuffmanTree(HuffmanTree ht, int w[ ], int n){ 
	for(i=1;i<=n;i++) ht[i] ={ w[i],0,0,0}; /* 1 ~ n 号单元存放叶子结点，初始化 */
	m=2*n-1;
	for(i=n+1;i<=m;i++) ht[i] ={0,0,0,0}; /* n+1 ~ m 号单元存放非叶结点，初始化 */
	/* 创建非叶结点，建哈夫曼树 */
	for(i=n+1; i<=m; i++){ 
// 在 ht [1] ~ ht [i-1] 的范围内选择两个 parent 为 0 且 weight 最小的结点，其序号分别赋值给 s1、s2 返回 
		select(ht, i-1, s1, s2); 
		ht [i].weight= ht [s1].weight+ ht [s2].weight;
		ht [s1].parent=i;
        ht [s2].parent=i;
		ht [i].LChild=s1;
        ht [i].RChild=s2;
	} /* 哈夫曼树建立完毕 */
}

# 哈夫曼编码

1. 概念

1. 前缀码：
如果在一个编码系统中，任一个编码都不是其他任何编码的前缀 (最左子串)，则称该编码系统中的编码是前缀码。
2. 哈夫曼编码：对一棵具有 n 个叶子的哈夫曼树，若对树中的每个左分支赋予 0， 右分支赋予 1 (也可规定左 1 右 0)，则从根到每个叶子的通路上，各分支的赋值分别构成一 个二进制串，该二进制串就称为哈夫曼编码。

2. 算法实现

typedef char * HuffmanCode[N+1]; /* 存储哈夫曼编码串的头指针数组 */
/* 从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码 */
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n){
	char *cd;
	cd=(char * )malloc(n* sizeof(char ));	/* 分配求当前编码的工作空间 */
	cd[n-1]＝’\0’;							/* 从右向左逐位存放编码，首先存放编码结束符 */
    
    /* 求 n 个叶子结点对应的哈夫曼编码 */
	for(i=1;i<=n;i++){ 
		start=n-1; 							/* 初始化编码起始指针 */
		c=i;
        p=ht[i].parent; 				/* 从叶子结点开始向上倒推 */
		while(p!=0){ 
            //start;
			if(ht[p].LChild==c) cd[start]=’0’; /* 左分支标 0*/
			else cd[start]=’1’; 			/* 右分支标 1*/
			c=p; p=ht[p].parent; 			/* 向上倒推 */
		}
		hc [i]=(char *)malloc((n-start)*sizeof(char)); /* 为第 i 个编码分配空间 */
		strcpy(hc[i], &cd[start]);					 /* 把编码复制到 hc [i] 中 */
	}
	free(cd);
}
-->