哈夫曼树又称最优二叉树，是一类带权路径长度最短的二叉树，有着广泛的应用。
基本概念
权：将树中的结点赋上一个有着某种意义的数值
路径：从A结点道B结点所经过的分支序列
路径长度：从A结点道B结点所经过的分支数目
查找效率
平均查找长度(ASL)取决于树的高度
ASL=(1+2*2+3)/4=2 ASL=(1+2+3+4)/4=2.5
O(log2n) O(n)
二叉树 单链表
带权路径长度
路径长度：路径上所经历边的个数
结点的权：结点被赋予的数值
树的带权路径长度 WPL树中所有叶结点的带权路径长度之和，记为
WPL=7*2+2*2+3*3=24 WPL=7*1+2*2+3*2=17
哈夫曼树 也称最优二叉树，含有n个带权叶子节点带权路径长度最小的二叉树
带权路径长度：树的根节点A结点的路径长度与A结点上的权的乘积
树的路径长度：一棵树中从根节点到每个结点的路径长度之和
树的带权路径长度：树中所有叶子节点的带权路径长度之和
WPL=2*2+2*4+2*5+2*8=38
WPL=4*2+5*3+8*3+2*1=49
WPL=8*1+5*2+4*3+2*3=36
哈夫曼树的构造算法
- 将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F
- 生成一个新结点，井从F中找出根结点权值最小的两棵树作为它的左右子树，且新结点的权值为两棵子树根结点的权值之和
- 从F中删除这两个树，并将新生成的树加入到F中
- 重复2,3步骤，直服务器托管网到F中只有一棵树为止
哈夫曼树的性质
- 每个初始结点都会成为叶节点，双支结点都为新生成的结点
- 权值越大离根结点越近，反之权值越小离根结点越远
- 哈夫曼树中没有结点的度为1
- n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1
构造哈夫曼树的方法
哈夫曼树的形态不是唯一的，第二步中的左右子树位置并不一定是小在左大在右，但具有一组权值的哈夫曼树的WPL是唯一的
哈夫曼树的构造算法:
编码对于一个字符串的序列，用二进制来表示字符
哈夫曼编码
构造一个哈夫曼树
#include
#include
#define MAX_N 1000
typedef struct _huff_node {
int weight;
int parent, lchild, rchild;
} HuffNode;
void huffman_tree(int n, int *weight, HuffNode *huff) {
// 初始化哈夫曼树的n个叶子结点
for (int i = 0; i 这个代码读入叶子结点个数和权值数组，然后构造哈夫曼树，并输出每个节点的权值、父节点、左子节点和右子节点。
代码解释：
-
#include和#include分别引入了标准输入输出库和标准库的头文件。 -
#define MAX_N 1000定义了一个宏，表示叶子结点的最大数量。 -
typedef struct _huff_node {...} HuffNode;定义了一个名为HuffNode的结构体，表示哈夫曼树中的节点。结构体包含了权值（weight）、父节点（parent）、左子节点（lchild）和右子节点（rchild）等字段。 -
void huffman_tree(int n, int *weight, HuffNode *huff) {...}是构造哈夫曼树的函数。参数包括叶子结点个数n、权值数组weight[]和存储哈夫曼树的数组huff[]。 -
for (int i = 0; i初始化哈夫曼树的n个叶子结点。遍历每个叶子结点，设置其权值为weight[i]，并将父节点、左子节点和右子节点初始化为-1。 -
for (int i = n; i构造哈夫曼树的非叶子结点。从第n个位置开始，遍历每个非叶子结点，选择权值最小的两个节点作为其左右子节点，并更新相关字段。 -
int main() {...}是主函数。在主函数中，首先声明了叶子结点个数n和权值数组weight[MAX_N]，以及存储哈夫曼树的数组huff[MAX_N * 2 – 1]。 -
scanf("%d", &n);读入叶子结点的个数n。 -
for (int i = 0; i通过循环读入叶子结点的权值数组weight[]。 -
huffman_tree(n, weight, huff);调用huffman_tree函数构造哈夫曼树。 -
for (int i = 0; i遍历哈夫曼树的所有结点，并输出每个结点的权值、父节点、左子节点和右子节点的信息。 -
return 0;表示程序正常结束。
总体来说，通过构造函数的方式实现了构造哈夫曼树的功能，并提供了一个简单的演示程序来展示结果。使用了结构体来存储每个节点的信息，并通过循环来遍历和处理服务器托管网每个节点，最终输出了哈夫曼树的结构信息。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
基类的成员函数可以被继承，可以通过派生类的对象访问，但这仅仅指的是普通的成员函数，类的构造函数不能被继承。构造函数不能被继承是有道理的，因为即使继承了，它的名字和派生类的名字也不一样，不能成为派生类的构造函数，当然更不能成为普通的成员函数。 在设计派生类时，对…
