|
1.哈夫曼树只有结点为0.或者结点为2的值。所以如果叶子结点为n的话，那么整个哈夫曼树的所有结点个数为2n-1；因为结点为2的结点个数n0=n2+1;所以总数n=n0+n2=2n0-1;
过程：<1>由已知的n个权值形成哈夫曼树的初态，即在数组ht[]的前n项中填入相应的权值。
<2>建立哈夫曼树。依次将数组ht[]中的第n+1项到第m项作为当前项，并进行以下处理：
1.在前已形成的项目中选择两个权值最小且无双亲的项。
2.将当前项的序号填入两个选择的项作为双亲，将两个选择项的序号填入当前项分别作为左右孩子。
3.将两个选择项的权值相加后填入当前项作为当前项的权值。
<3>由已形成的哈夫曼树求哈夫曼编码。对每个叶节点都进行如下处理：
扫描由叶节点到根节点的各条分支，若果分支中的当前结点与双亲关系是左支关系，则生成编码0，若分之中的当前结点与双亲结点是右支关系，则生成编码1，由此生成的二级制码的序列即为该结点的哈夫曼编码。
程序如下：
#include<iostream>
using namespace std;
#define maxlen 100
struct HaffNode
{
int weight;
int parent;
int lchild;
int rchild;
};
struct HaffCode
{
int bit[maxlen];
int start;
int weight;
};
void Haffman(int w[],int n,HaffNode ht[],HaffCode hc[])
{
int i,j,m1,m2,x1,x2;//m1,m2分别表示最小，次小的权值；x1,x2分别表示当前分支结点的左右儿子
//步骤1.构造哈夫曼树
for (i = 0; i < 2 * n - 1; i++)//哈夫曼树初始化
{
if (i < n)ht[i].weight = w[i];
else
ht[i].weight = 0;
ht[i].parent = 0;
ht[i].lchild = ht[i].rchild = -1;
}
for (i = 0; i < n - 1; i++)//构造哈夫曼树的n-1个分支结点
{
m1 = m2 = 1000;
x1 = x2 = 0;
for (j = 0; j < n + i; j++)
{
if (ht[j].weight < m1 && ht[j].parent == 0)
{
m2 = m1;//最小保存到次小
x2 = x1;
m1 = ht[j].weight;
x1 = j;
}
else if (ht[j].weight < m2 && ht[j].parent == 0)
{
m2 = ht[j].weight;
x2 = j;
}
}
ht[x1].parent = n + i;
ht[x2].parent = n + i;
ht[n + i].weight = ht[x1].weight + ht[x2].weight;
ht[n + i].lchild = x1;
ht[n + i].rchild = x2;
}
//步骤2 由哈夫曼树生成哈夫曼编码
HaffCode cd;
int child,parent;
for (i = 0; i < n; i++)//由哈夫曼树生成哈夫曼编码
{
cd.start = n - 1;
cd.weight = ht[i].weight;
child = i;
parent = ht[child].parent;
while (parent != 0)
{
if (ht[parent].lchild == child)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--;
child = parent;
parent = ht[child].parent;
}
for (j = cd.start + 1; j < n; j++)
hc[i].bit[j] = cd.bit[j];
hc[i].start = cd.start;
hc[i].weight = cd.weight;
}
}
int main(void)
{
int w[] = { 4,2,6,8,3,1 };
int n = 7,i,j;
HaffNode *ht = new HaffNode[2 * n - 1];
HaffCode *hc = new HaffCode[n];
Haffman(w,n,ht,hc);
for (i = 0; i < n; i++)
{
cout << "weight=" << hc[i].weight << "code=";
for (j = hc[i].start + 1; j < n; j++)
cout << hc[i].bit[j];
cout << endl;
}
}
效果图：
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
