文档介绍：c++数据结构实验哈夫曼树
北京邮电大学信息与通信工程学院
第2页
北京邮电大学电信工程学院
第1页
数据结构实验报告
1．实验要求
实验目的:
掌握二叉树基本操作的实现方法
掌握二叉树基本操作的实现方法
了解哈count[k].num << endl;
}
}
}
将初始化的数据用于建立哈夫曼树：
void Huffman::createht()
{
no = 0;
htree = new hnode[2 * n - 1];//含有n种字符的哈夫曼树需要2*n-1个结点
for (int i = 0; i<n; i++)
北京邮电大学信息与通信工程学院
第8页
北京邮电大学电信工程学院
第1页
{
while (count[no].num == 0) //该字符没有出现，跳过，继续找出现过的字符
{
no++;
}
htree[i].weight = count[no].num; //将count里统计的次数传入哈夫曼树的节点中，作为字符权重
htree[i].lchild = -1;
htree[i].rchild = -1;
htree[i].parent = -1; //将左右孩子结点和父节点都置空
htree[i].data = count[no].data; //将字符传入哈夫曼树的结点
no++;
}
int x = -1, y = -1;
for (int i = n; i < 2 * n - 1; i++)
{
SelectMin(x, y, i);
北京邮电大学信息与通信工程学院
第9页
北京邮电大学电信工程学院
第1页
//挑选三者中的权重较小的两个
htree[x].parent = htree[y].parent = i; //令较小的x、y为孩子节点，该两个结点的父节点是i
htree[i].weight = htree[x].weight + htree[y].weight;//i结点字符的权重赋为是左右孩子字符权重之和
htree[i].lchild = x; //左孩子为x
htree[i].rchild = y; //右孩子为y
htree[i].parent = -1; //父节点置空
x = -1;
y = -1;
}
}
注意select函数的编写十分重要，必须成功选出每次权值最小的两个数据才能正确的建立哈夫曼树
void Huffman::SelectMin(int &x, int &y, int k) //选出权值较小的两个字符结点
北京邮电大学信息与通信工程学院
第10页
北京邮电大学电信工程学院
第1页
{
int i = 0;
while (i < k)
{
while (i < k&&htree[i].parent == -1) //当前结点不具有父结点且满足i<k则进行循环
{
if (x == -1) //左孩子
x = i;
else if (y == -1)
y = i;
else
if (htree[x].weight <= htree[y].weight)
{
if (htree[y].weight <= htree[i].weight)
{
y = y; x = x;
}
else
北京邮电大学信息与通信工程学院
第11页
北京邮电大学电信工程学院
第1页
y = i;
}
else
if (htree[x].weight > htree[y].weight)
{
if (htree[i].weight >= htree[x].weight)
{
x = x; y = y;
}
else
x = i;
}
i++;
}
i++;
}
}
北京邮电大学信息与通信工程学院
第12页
北京邮电大学电信工程学院
第1页
B）create table建立编码表：
利用初始化得到的结果将