Huffman树及编码C++实现 By qianghaohao（Johar） Huffman树采用数组实现，编码时从叶子节点开始向上编码，所以采用deque支持前插的
容器来存放每个叶子的编码。
代码如下: #include #include #include #include #include using namespace std;typedef struct { int weight; int parent; int lchild; int rchild; bool flag;} HaffmanTree;// h:Haffman树 w:权向量void CreateHaffmanTree(vector &h, const vectorw) { int n = w.size(); //叶子个数 int condi = 2 * n - 1; //Haffman树节点总数 for (int i = 0; i < condi; i++) { if (i < n) { h[i].weight = w[i]; //Haffman前n个节点的权值为给出的数组 } else { h[i].weight = 0; // 其他权值赋值为0 } h[i].parent = -1; h[i].lchild = -1; h[i].rchild = -1; h[i].flag = false; } condi = n -1; int mini1, mini2; // mini1:最小值 mini2:次小值 int x1, x2; //记录最小值和次小值位置 for (int i = 0; i < condi; i++) { mini1 = mini2 = INT_MAX; x1 = x2 = 0; for (int j = 0; j < n + i; j++) { if (h[j].weight < mini1 && !h[j].flag) { mini2 = mini1; x2 = x1; mini1 = h[j].weight; x1 = j; } else if (h[j].weight < mini2 && !h[j].flag) { mini2 = h[j].weight; x2 = j; } } h[n + i].weight = mini1 + mini2; h[n + i].lchild = x1; h[n + i].rchild = x2; h[x1].parent = n + i; h[x2].parent = n + i; h[x1].flag = true; h[x2].flag = true; }}// h:Haffman树 n:叶子个数 c:叶子编码void HaffmanEncode(vector &h, int n, vector> &c) { int _child, _parent; for (int i = 0; i < n; i++) { _child = i; _parent = h[_child].parent; while (_parent != -1) { if (h[_parent].lchild == _child) { c[i].push_front(0); //左分支编码0 } else { c[i].push_front(1); //右分支编码1 } _child = _parent; //继续往上编码 _parent = h[_parent].parent; } }}vector weight = {7, 5, 2, 4}; //权向量vector haff(2 * weight.size() - 1); //haffman树向量vector> encode(weight.size()); // Haffman编码向量int main (){ CreateHaffmanTree(haff, weight); cout << '\n---叶子向量:vectorweight={7, 5, 2, 4};\n'; cout << '*******哈夫曼树********' << endl; cout << '节点 左孩子 右孩子' << endl; for (vector::iterator it = haff.begin(); it != haff.end(); it++) { cout << it->weight; if (it->lchild >= 0) { cout << ' ' << haff[it->lchild].weight; } else { cout << ' *'; } if (it->rchild >= 0) { cout << ' ' << haff[it->rchild].weight; } else { cout << ' *'; } cout << '\n'; } //哈夫曼编码 int n = weight.size(); HaffmanEncode(haff, n, encode); cout << '\n******哈夫曼编码:*******' << endl; for (int i = 0; i < n; i++) { cout << haff[i].weight << ':'; copy(encode[i].begin(), encode[i].end(), ostream_iterator(cout)); cout << '\n'; } return 0;}
|
