哈夫曼树/哈夫曼编码

137 阅读 0 评论 91 点赞

我是靠谱客的博主烂漫水杯，这篇文章主要介绍哈夫曼树/哈夫曼编码，现在分享给大家，希望可以做个参考。

本算法采用二叉链表来构造二叉树，并用递归算法求哈夫曼编码

构造哈夫曼树

概念：哈夫曼树为带权路径最短的二叉树
构造过程：每次选出最小的两个顶点，分别作为左右分支，构造出父节点，父节点权值为两顶点之和，然后将其加入到顶点集合中，并删除之前取出的两个顶点。

哈夫曼编码

算法思想：通过递归，从根结点往每个叶子结点来进行编码。通过一个临时数组来按照左零右一存储下来，若遇到叶子结点，则将存储的路径作为该字符的编码。

代码

复制代码

void CreateHuffmanTree(BinaryTree &T, ElemType a[],int n)
{
	TNode **Data = new TNode *[n];
	for (int i = 0; i < n; i++)
	{
		TNode *p = new TNode;
		p->data = a[i];
		p->lchild = NULL;
		p->rchild = NULL;
		Data[i] = p;
	}
	for (int i = 0; i < n - 1; i++) //n个结点 需要n-1次循环
	{
		//每次取两个最小的结点构造哈夫曼树
		TNode *p = new TNode;
		p->data = Data[0]->data + Data[1]->data;
		p->lchild = Data[0];
		p->rchild = Data[1];
		//删除两个最小结点
		for (int i = 2; i < n; i++)
			Data[i - 2] = Data[i];
		//增加新建的结点
		int j = n - i - 2; //j指向未加入哈夫曼树的最大顶点
		if (j != 0)  //j不等于0 用直接插入排序 插入新建的顶点
		{
			if (p->data < Data[j]->data)
			{
				for (j; j >= 0 && p->data < Data[j]->data; j--)
					Data[j + 1] = Data[j];
				Data[j + 1] = p;
			}
			else
				Data[j] = p;
		}
		else //j等于0 说明为哈夫曼树的根结点 直接赋值
			Data[j] = p;
	}
	//最后数组里只有一个结点 则哈夫曼树构造完成
	T = Data[0];
	delete []Data; //释放辅助数组空间
}

void CreateHuffmanCode(BinaryTree T,char *Code[], int n)
{
	static int i = 0; //i为编码字符的编号
	static int j = 0; //j为每个字符应编码的长度 初试话为0
	static char *c = new char[n];
	if (T)
	{	
		
		if (!T->lchild && !T->rchild) //如果为叶子结点 则按照左0右1规则编码
		{
			c[j++] = ''; //结束符
			Code[i] = new char[j]; //分配j的长度
			strcpy(Code[i++],c); //串复制
			j--; //取消结束符
		}
		if (T->lchild) //左0
		{
			c[j++] = '0';
			CreateHuffmanCode(T->lchild,Code,n);
			j--;
		}
		if(T->rchild) //右1
		{
			c[j++] = '1';
			CreateHuffmanCode(T->rchild,Code,n);
			j--;
		}
	}
	delete []c;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
void CreateHuffmanTree(BinaryTree &T, ElemType a[],int n)
{
	TNode **Data = new TNode *[n];
	for (int i = 0; i < n; i++)
	{
		TNode *p = new TNode;
		p->data = a[i];
		p->lchild = NULL;
		p->rchild = NULL;
		Data[i] = p;
	}
	for (int i = 0; i < n - 1; i++) //n个结点 需要n-1次循环
	{
		//每次取两个最小的结点构造哈夫曼树
		TNode *p = new TNode;
		p->data = Data[0]->data + Data[1]->data;
		p->lchild = Data[0];
		p->rchild = Data[1];
		//删除两个最小结点
		for (int i = 2; i < n; i++)
			Data[i - 2] = Data[i];
		//增加新建的结点
		int j = n - i - 2; //j指向未加入哈夫曼树的最大顶点
		if (j != 0)  //j不等于0 用直接插入排序 插入新建的顶点
		{
			if (p->data < Data[j]->data)
			{
				for (j; j >= 0 && p->data < Data[j]->data; j--)
					Data[j + 1] = Data[j];
				Data[j + 1] = p;
			}
			else
				Data[j] = p;
		}
		else //j等于0 说明为哈夫曼树的根结点 直接赋值
			Data[j] = p;
	}
	//最后数组里只有一个结点 则哈夫曼树构造完成
	T = Data[0];
	delete []Data; //释放辅助数组空间
}

void CreateHuffmanCode(BinaryTree T,char *Code[], int n)
{
	static int i = 0; //i为编码字符的编号
	static int j = 0; //j为每个字符应编码的长度 初试话为0
	static char *c = new char[n];
	if (T)
	{	
		
		if (!T->lchild && !T->rchild) //如果为叶子结点 则按照左0右1规则编码
		{
			c[j++] = ''; //结束符
			Code[i] = new char[j]; //分配j的长度
			strcpy(Code[i++],c); //串复制
			j--; //取消结束符
		}
		if (T->lchild) //左0
		{
			c[j++] = '0';
			CreateHuffmanCode(T->lchild,Code,n);
			j--;
		}
		if(T->rchild) //右1
		{
			c[j++] = '1';
			CreateHuffmanCode(T->rchild,Code,n);
			j--;
		}
	}
	delete []c;
}