二叉树的五种基本形态图(二叉树合集（二）：霍夫曼树(图文详解))
地址匹配二叉树匹配(一)二叉树的基础；包含4种扫描，用文字详细说明) ) ) )。
二叉树集(二)火星帽子树(文字详细解) ) ) ) ) )
二叉树集(三) :线索二叉树(文字详细解)
二叉树的集合(四)对称二叉树(递归和迭代的实现) ) )
二叉树集(五) :二叉搜索树(包括照片详细解、基本操作) ) ) ) ) ) )
二叉树合集(六)高度平衡二叉树
前言火星帽树是二叉树的一种特殊形式，也称为最优二叉树，其主要作用是数据压缩和码长优化。
2重要概念2.1路径和路径长度是一棵树中可以从一个节点到达下的儿孙节点之间的路径，称为路径。 分支的数量被称为路径长度。 设根节点的层数为1，则从根结点到第l层节点的路径长度为L-1。
图2.1
图2.1中所示的二叉树从节点a到节点d的路径长度为2，并且从节点a到节点c的路径长度为1。
2.2如果对节点的权重和加权路径长树中的节点赋予某种意义的值，则将该值称为该节点的权重。 节点的加权路径长度是从根结点到该节点的路径长度与该节点的权重的积。
图2.2显示了拥有权利的二叉树
图2.2
2.3树加权路径长度树的加权路径长度被定义为所有叶节点的加权路径长度之和，并标记为WPL。
图2.2所示二叉树的WPL :
WPL=6 * 2 3 * 2 8 * 2=34；
3火星帽子树3.1定义了作为n个叶子节点给出的权重，制作了一棵二叉树。 当加权路径的长度最小时，这种二叉树被称为最佳二叉树，也称为火星帽子树(Huffman Tree )。
如图3.1所示，两根二叉树
图3.1
叶的节点为a、b、c、d，对应的权重分别为7、5、2、4。
3.1.a树中的WPL=7 * 2 5 * 2 2 * 2 4 * 2=36
3.1.b树中的WPL=7 * 1 5 * 2 2 * 3 4 * 3=35
用ABCD构成叶节点的二叉树的形态有很多种类，但WPL最小的树只有3.1.b所示的形态。 3.1.b树是火星帽树。
3.2结构火星帽木结构火星帽木主要应用于编码，称为火星帽码。 这里，考虑使用3.1中的ABCD节点及其对应的权重，构成以下长度的代码。
AACBCAADDBBADDAABB。 从编码规则:根节点出发，左侧标记0，右侧标记1。
使用上述编码规则，如图3.1所示对图3.2进行编码。
图3.2
构建过程：
3.1.a所示的二叉树被称为等长码，由于共有4个节点，需要用2位的码来表示，编码结果如下。
对于节点代码A00B01C10D11，启用AACBCAADDBBADDAABB的代码如下所示：
00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01
长度是36。
3.1.b结构过程如下。
1 )选择节点权重最小的两个节点制作二叉树，如图3.3所示。
图3.3
2 )那么，现在可以把火星帽子树看成是用T1、a、b做的，继续步骤1。
选择由b和T1构成的二叉树如图3.4所示。
图3.4
3 )当前只有T2和a两个节点，请转至步骤1。
选择a和T2构成二叉树的话如图3.5所示。
图3.5
经过以上步骤可以制作火星帽子树。 通过观察发现，火星帽子树中权重越大的节点越接近根节点。
图3.5火星帽子树编码结果显示：
节点代码A0B10C110D111对应于AACBCAADDBBADDAABB，编码如下：
0 0 110 10 110 0 0 111 111 10 10 0 111 111 0 0 10 10
代码长度是35。
因此，使用二叉树可以适当地缩短码长，特别是在码长、权重分布不均匀的情况下，使用火星帽子码可以大幅缩短码长。
3.3代码实现# include iostream # include stdlib.husingnamespacestd； 常数最大值=10000； //初始设定权重的最大值const int MaxBit=4； //初始设定的最大编码位数const int MaxN=10； //默认的最大节点数struct HaffNode//哈夫曼树的节点结构{ int weight； //权重int flag； 标记int parent； //父母节点的下标int leftChild； //左旁注int rightChild； //右边孩子的下标； 存储结构代码//霍夫曼编码的数据元素结构{ int bit[MaxBit]； //数组int
start;//编码的起始下标 int weight;//字符的权值};void Haffman(int weight[], int n, HaffNode haffTree[])//建立叶结点个数为n权值为weight的哈夫曼树haffTree{ int j, m1, m2, x1, x2; //哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点 for (int i = 0; i<2 * n - 1; i++) { if (i<n) haffTree[i].weight = weight[i]; else haffTree[i].weight = 0; //注意这里没打else那{}，故无论是n个叶子节点还是n-1个非叶子节点都会进行下面4步的初始化 haffTree[i].parent = 0; haffTree[i].flag = 0; haffTree[i].leftChild = -1; haffTree[i].rightChild = -1; } //构造哈夫曼树haffTree的n-1个非叶结点 for (int i = 0; i<n - 1; i++) { m1 = m2 = MaxValue;//Maxvalue=10000;(就是一个相当大的数) x1 = x2 = 0;//x1、x2是用来保存最小的两个值在数组对应的下标 for (j = 0; j<n + i; j++)//循环找出所有权重中，最小的二个值--morgan { if (haffTree[j].weight<m1&&haffTree[j].flag == 0) { m2 = m1; x2 = x1; m1 = haffTree[j].weight; x1 = j; } else if(haffTree[j].weight<m2&&haffTree[j].flag == 0) { m2 = haffTree[j].weight; x2 = j; } } //将找出的两棵权值最小的子树合并为一棵子树 haffTree[x1].parent = n + i; haffTree[x2].parent = n + i; haffTree[x1].flag = 1; haffTree[x2].flag = 1; haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight; haffTree[n + i].leftChild = x1; haffTree[n + i].rightChild = x2; }}void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])//由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode{ Code *cd = new Code; int child, parent; //求n个叶结点的哈夫曼编码 for (int i = 0; i<n; i++) { //cd->start=n-1;//不等长编码的最后一位为n-1, cd->start = 0;//,----修改从0开始计数--morgan cd->weight = haffTree[i].weight;//取得编码对应权值的字符 child = i; parent = haffTree[child].parent; //由叶结点向上直到根结点 while (parent != 0) { if (haffTree[parent].leftChild == child) cd->bit[cd->start] = 0;//左孩子结点编码0 else cd->bit[cd->start] = 1;//右孩子结点编码1 //cd->start--; cd->start++;//改成编码自增--morgan child = parent; parent = haffTree[child].parent; } //保存叶结点的编码和不等长编码的起始位 //for(intj=cd->start+1;j<n;j++) for (int j = cd->start - 1; j >= 0; j--)//重新修改编码，从根节点开始计数--morgan haffCode[i].bit[cd->start - j - 1] = cd->bit[j]; haffCode[i].start = cd->start; haffCode[i].weight = cd->weight;//保存编码对应的权值 }}int main(){ int i, j, n = 4, m = 0; int weight[] = { 2,4,5,7 }; HaffNode*myHaffTree = new HaffNode[2 * n - 1]; Code*myHaffCode = new Code[n]; if (n>MaxN) { cout << "定义的n越界，修改MaxN!" << endl; exit(0); } Haffman(weight, n, myHaffTree); HaffmanCode(myHaffTree, n, myHaffCode); //输出每个叶结点的哈夫曼编码 for (i = 0; i<n; i++) { cout << "Weight=" << myHaffCode[i].weight << " Code="; //for(j=myHaffCode[i].start+1;j<n;j++) for (j = 0; j<myHaffCode[i].start; j++) cout << myHaffCode[i].bit[j]; m = m + myHaffCode[i].weight*myHaffCode[i].start; cout << endl; } cout << "huffman's WPL is:"; cout << m; cout << endl; return 0;} 4 结语本文主要介绍了火星上的帽子树的实际意义和如何构造一棵二叉树。学习火星上的帽子树主要是掌握火星上的帽子树的构造思想以及构造过程，至于代码实现则是次要的，而且火星上的帽子编码实现过程中运用到了贪心算法。