数据结构——哈夫曼树的创建

1. 算法思想

构造哈夫曼树算法思路： 1.初始化HT[1…2n-1], lch=rch=parent=0.

2.输入n个叶子结点，置于HT[1…n]的weight（权值）。

3.进行n-1次合并，依次产生n-1个结点HT[i], i = n+1…2n-1； a） 在HT[1…i-1]中选两个未被选过（从parent==0的结点中选）的weight最小的两个结点HT[s1]和HT[s2], s1,s2为两个最小结点的下标 b） 修改HT[s1]和HT[s2]的parent值：HT[s1].patent=i, HT[s2].patent=i ; c) 修改新产生的的HT[i]； 1. HT[i].weight = HT[s1].weight + HT[s2].weight; 2. HT.lch = s1; HT[i].rch = s2;

2.完整代码

#include<iostream> using namespace std; //结点类型定义（采用顺序存储结构—一维结构数组） typedef struct{ int weight; //结点的权值 int parent, lch, rch; }HTNode, *HuffmanTree; //返回哈夫曼树t的前i个结点中权值最小的树的根结点的序号 int min(HuffmanTree t, int i) { int j, m; unsigned int k = UINT_MAX; //k存最小权值，初值去取一个不小于树中可能的值（无符号整型最大值） for (j = 1; j <= i; ++j) //对于前i个结点 { if ( t[j].weight <= k && t[j].parent == 0 ) //t[i]的权值小于k,又是树的根结点 { k = t[j].weight; //t[j]的权值赋给k m = j; //序号赋给m } } t[m].parent = 1; //给选中的根结点双亲赋非0值，避免第二次查找 return m; } //在哈夫曼树t的前i个结点中选择权值最小的树的根结点的序号 void select(HuffmanTree t, int i, int &s1, int &s2) { int j; s1 = min(t, i); //权值最小的根结点的序号 s2 = min(t, i); //权值第二小的根结点的序号 if (s1 > s2) { j = s1; s1 = s2; s2 = j; } } //构造哈夫曼树算法思路： //1.初始化HT[1....2n-1], lch=rch=parent=0. //2.输入n个叶子结点，置于HT[1....n]的weight（权值）。 //3.进行n-1次合并，依次产生n-1个结点HT[i], i = n+1....2n-1； // a） 在HT[1...i-1]中选两个未被选过（从parent==0的结点中选）的weight最小的两个结点HT[s1]和HT[s2], s1,s2为两个最小结点的下标 // b） 修改HT[s1]和HT[s2]的parent值：HT[s1].patent=i, HT[s2].patent=i ; // c) 修改新产生的的HT[i]； // 1. HT[i].weight = HT[s1].weight + HT[s2].weight; // 2. HT.lch = s1; HT[i].rch = s2; void CreatHuffmanTree(HuffmanTree HT, int n) { int m, i, s1, s2; if (n <= 1 ) return; m = 2 * n - 1; //数组共有2n-1个元素 HT = new HTNode[m+1]; //0号单元未用，HT[m]表示根结点 for (i = 1; i <= m; ++i) //将2n-1个元素的lch，rch，parent置为0 { HT[i].lch = 0; HT[i].rch = 0; HT[i].parent = 0; } for (i = 1; i <= n; ++i) //输入前n个元素的weight值 { cin >> HT[i].weight; } //初始化结束，下面开始建立哈夫曼树 for (i = n+1; i <= m; i++) { select(HT, i-1, s1, s2); //在HT[k]（1<=k<=i-1）中选择两个其双亲域为0，且权值最小的结点 HT[s1].parent = i; HT[s2].parent = i; //表示删除s1,s2 HT[i].lch = s1; HT[i].rch = s2; //s1,s2分别为i的左右孩子 HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权值为左右孩子之和 } //打印哈夫曼树 cout << "下标\t" << "权重\t" << "双亲\t" << "左孩子\t" << "右孩子" << endl; for (int j = 1; j < i; j++) { cout << j << "\t" << HT[j].weight << "\t" << HT[j].parent << "\t" << HT[j].lch << "\t" << HT[j].rch << endl; } } /********************主函数**********************/ int main() { HuffmanTree HT = NULL; int n; cout << "请输入字符个数：" << endl; cin >> n; cout << "请输入权值：" << endl; CreatHuffmanTree(HT, n); return 0; }

3.测试结果