【哈夫曼树】

1. 哈夫曼树的基本概念

哈夫曼树又称最优二叉树（最优树），是一类带权路径长度最短的树。

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

路径长度：路径上分支的数目。

树的路径长度：从树根到每个结点的路径长度之和。

---

权：分为结点权和边权，结点权是结点上的权，边权是边上权。

结点的带权路径长度：从该结点到树根的路径长度乘以该结点的权值。

树的带权路径长度：树中每一个叶子结点的带权路径长度之和，即WPL = 

---

哈夫曼树：带权路径长度WPL最小（最小带权路径长度）的二叉树称作最优二叉树或哈夫曼树。

2. 哈夫曼树的算法实现

哈夫曼树中是没有度为1的结点，则一棵有 n 个叶子结点的哈夫曼树共有 2n - 1个结点，

因此可以用存储大小为 2n - 1的一维数组中。

2.1 哈夫曼树的存储结构

typedef struct{
	int weight;                   //结点的权值 
	int parent,lchild,rchild;    //结点的双亲，左孩子，右孩子的下标 
}HTNode,* HuffmanTree;          //动态分配数组存储哈夫曼树

2.2 构造哈夫曼树

【算法步骤】

构造哈夫曼树算法的实现可以分成两大部分：（1）初始化 （2）创建哈夫曼树

（1）初始化

1. 确定哈夫曼树中的结点个数 m = 2n - 1；（其中，n为叶子节点的个数），

2. 动态分配 2n 个存储单元（0号单元未使用，HT[m] 表示根节点），

3. 从1到2n-1个所有单元中双亲、左孩子、右孩子的下标初始化为 0；

4. 依次输入 n 个叶子结点的权值。

---

（2）创建哈夫曼树

共有 n 个叶子结点，循环 n - 1次，通过n - 1次的选择、删除、合并操作来创建哈夫曼树。

1. 选择：从当前数中选择双亲为 0，且权值最小的两个树根结点，

2. 删除：将选出了来的两个结点的双亲改为非0，

3. 合并：最小两个结点的权值和作为一个新结点的权值依次存入到数组的第 n + 1之后的单元中，同时记录左孩子和右孩子的信息。

【算法描述】

void CreateHuffanTree(HuffmanTree &HT , int n){
	int m = 2 * n - 1;   //确定哈夫曼数中的结点个数
	HT = new HTNode[m + 1];   //动态分配 2n 个存储单元（2n == m + 1)
	
	for(int i = 1; i <= m; i++){     //将所有结点进行初始化 
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	} 
	for(int i = 1; i <= n; i++){    //输入 n 个叶子结点的权值 
		cin >> HT[i].weight;     
	}

   ----------初始化操作结束------------- 

	//创建哈夫曼树 
	for(int i = n + 1; i <= m; i++){
		// 1.选择两个权值最小的根节点
		int s1,s2;
		Select(HT, i - 1, s1,s2);       //返回的是两个最小权值结点的下标 
		
	    //2.从森林中删除两个树
		HT[s1].parent = i;
		HT[s2].parent = i;
		
		//3.合并两个结点的权值，并加入到 n + 1个单元中,且指定左孩子、右孩子 
		HT[i].left = s1;
		HT[i].right = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight ;  
	} 
}