1.节点i的路径长度：从根节点到节点i的路径上所经过边数

2.树的路径长度：所有节点的路径长度之和

内部路径长度：所有内部节点路径长度之和

外部路径长度（有时会把树的路径长度当作外部路径长度）：所有叶子节点路径长度之和

3.节点i的带权路径长度：节点i的路径长度*节点i权值

4.树的带权路径长度（WPL）：所有叶子节点的带权路径长度之和

给出n个节点（都带有权值），可以再自行加入若干节点（不确定），用这n个节点全部做叶子节点，自行加入的节点做内部节点去建立一棵二叉树，其中WPL最小的一棵二叉树称为哈夫曼树（最优二叉树）

注：哈夫曼树WPL的值唯一

但WPL的值最小的哈夫曼树不唯一

如何构建哈夫曼树？

给定n个节点（带权值且只做叶子节点）

1.一开始认为n个节点为n棵树

2.每次找根节点权值最小的两棵树（x，y），再新加入一个节点z做x和y的父亲，新的根节点权值为（x，y），此时将x，y两棵树合并出一棵新树，这棵树的根节点为z

哈夫曼树应用：通过编码进行数据压缩

哈夫曼编码—>变长编码，压缩空间

定长编码：ASCII编码（8bit），Unicode编码（16bit）

缺陷：浪费空间

变长编码：比定长编码省空间

可以使用哈夫曼树来构造变长编码—>哈夫曼编码

1.先统计一条消息中n个字符分别出现频率—>节点权值

2.构造哈夫曼树

3.标上1和0

注：哈夫曼树WPL值即为信息编码所占bit位数

注：变长编码中遵循前缀属性原则（短的编码不能是长编码的前缀，避免二义性）

哈夫曼编码树实现：

1.建立哈夫曼树：把每个字符的频率看作节点的权值，建立哈夫曼树，通过结构体数组模拟存储

节点：权值，父亲的下标，左右孩子节点的下标

（1）查找最小的两个根节点

（2）合并，加入一个新的根节点

注：n个叶子节点，总共有2*n-1个节点

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
class Node
{
public:
	int w;//权值
	int fi;//父亲节点坐标
	int left;//左右孩子节点下标
	int right;
};
class HFM_Tree
{
public:
	int size;//节点个数
	Node* tree;//指针模拟开数组
public:
	HFM_Tree(int w_arr[], int sz) :size(2 * sz - 1)
	{
		tree = new Node[size];
		if (tree == nullptr)
		{
			cout << "开辟失败" << endl;
		}
		else
		{
			//初始化哈夫曼树（从下标为零开始存储）
			for (int i = 0; i < size; ++i)
			{
				tree[i].w = 0;
				tree[i].fi = 0;
				tree[i].left = tree[i].right = 0;
			}
			//构建哈夫曼树
			for (int i = 0; i < sz; ++i)
			{
				tree[i].fi = i;
				tree[i].w = w_arr[i];
			}
			int w1(0);
			int w2(0);//查找最小权值的两个下标
			//放入新节点
			for (int i = sz; i < size; ++i)
			{
				//i位置放新的节点，所以范围最大为i - 1
				Find_Min_w(i, w1, w2);
				//将最小权值的两个根节点连接起来，作为孩子
				tree[w1].fi = tree[w2].fi = i;
				tree[i].w = tree[w1].w + tree[w2].w;
				tree[i].fi = i;//别忘了给新节点加上父亲
				tree[i].left = w1;
				tree[i].right = w2;
			}
		}
	}
	//查找的范围和两个权值，传引用直接修改
	void Find_Min_w(int range, int& w_1, int& w_2)
	{
		//先找最小权值下标
		int min(0);
		for (int i = 0; i < range; ++i)
		{
			if (tree[i].fi == i)
			{
				//找第一个根节点
				min = i;
				break;
			}
		}
		//找出最小权值下标
		for (int i = 0; i < range; ++i)
		{
			if (tree[i].fi == i)
			{
				if (tree[i].w < tree[min].w)
				{
					min = i;
				}
			}
		}
		w_1 = min;
		//再找第二小根节点下标
		for (int i = 0; i < range; ++i)
		{
			if (tree[i].fi == i && i != w_1)
			{
				//找第二个根节点
				min = i;
				break;
			}
		}
		for (int i = 0; i < range; ++i)
		{
			if (tree[i].fi == i && i != w_1)
			{
				if (tree[i].w < tree[min].w)
				{
					min = i;
				}
			}
		}
		w_2 = min;
	}
	//进行哈夫曼编码，左为0，右为1，从下往上找（找出来是倒序的）
	//利用二维数组存储编码，使用一维数组暂存每一个字符编码，将一维数组拷贝到二维数组中

	//叶子节点个数
	char** Create_HFM_code(int n)
	{
		char *temp = new char[n];//树理论最高为n，但实际存不满
		char** code = new char*[n];
		int start(0);//一开始存放编码的位置
		int p(0);//存放节点下标
		int p_f(0);//存放节点父亲下标（用于判断是左孩子还是右孩子）
		for (int i = 0; i < n; ++i)
		{
			start = n - 1;
			temp[start] = '\0';//因为存放的是0，1字符
			p = i;
			p_f = tree[i].fi;
			while (tree[p].fi != p)//一路找到根节点
			{
				start--;
				if (tree[p_f].left == p)
				{
					temp[start] = '0';
				}
				else
				{
					temp[start] = '1';
				}
				p = p_f;
				p_f = tree[p].fi;
			}
			code[i] = new char[n - start];
			strcpy(code[i], &temp[start]);//拷贝哈夫曼编码
		}
		delete temp;
		temp = nullptr;
		return code;
	}
};
int main()
{
	char s[8] = { 'A', 'B', 'C', 'D','E', 'F', 'G', 'H' };
	int w[8] = { 5, 29, 7, 8,14, 23, 3, 11 };
	HFM_Tree tr(w, 8);
	char** code = tr.Create_HFM_code(8);
	for (int i = 0; i < 8; ++i)
	{
		cout << s[i] << ' ' << code[i] << endl;
	}
	return 0;
}