数据结构—哈弗曼树

（学期接近尾声，学数据结构13周了，还是好菜。）

1.哈夫曼树

树中的每个结点赋予一个数值，称为权。 从根结点到该结点之间的路径长度与该结点权的乘积为节点的带权路径长度。 所有叶子结点的带权路径长度之和最小的二叉树称为哈弗曼树。

2.哈夫曼树的构造算法

（1）根据给定的n0个权值对应构成n0棵二叉树的森林F，每棵二叉树中都只有一个带权值wi的根结点，其左右孩子为空。 （2）森林F中选取两棵结点权值最小的子树分别作为左右子树构造成一棵新的二叉树，并且新的二叉树的权值为左右子树权值之和。 （3）森林F中，用新的二叉树代替这两棵子树。 （4）重复（2）和（3），直到只剩一棵树，这棵树便是哈弗曼树。

示例：

这里有个定理：对于有n0个叶子结点的哈弗曼树，共有2*n0-1个结点。

// 哈弗曼树结点类型 typedef struct { char data; double weight; int parent; int lchild; int rchild; }HTNode;

↓ht[0]~ht[n0-1]存放叶子结点，ht[n0] ~ht[2*n0-2]存放非叶子结点。

// 构造哈弗曼树 void CreateHT(HTNode ht[],int n0) { int i,k,lnode,rnode; double min1,min2; for(i=0;i<2*n0-1;i++)//所有结点相关域置初值-1 ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n0;i<=2*n0-2;i++)//构造n0-1个分支结点 { min1=min2=32676; lnode=rnode=-1; for(k=0;k<=i-1;k++)//在ht[0...i-1]中找权值最小的两个结点 if(ht[k].parent==-1)//只在没构成二叉树的节点中找 { if(ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } else if(ht[k].weight<min2) { min2=ht[k].weight;rnode=k; } } ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; ht[lnode].parent=i;ht[rnode].parent=i; } }

3.哈夫曼编码

规定哈夫曼树中左分支为0，右分支为1，从根结点到每个叶子结点所经过的分支对应的0和1组成的序列。

示例：

代码就不粘了￣□￣｜｜