Huffman树及编码C++实现

By qianghaohao（Johar）

Huffman树采用数组实现，编码时从叶子节点开始向上编码，所以采用deque支持前插的
容器来存放每个叶子的编码。
代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <deque>
using namespace std;

typedef struct {
   int weight;
   int parent;
   int lchild;
   int rchild;
   bool flag;
} HaffmanTree;

//  h:Haffman树   w:权向量
void CreateHaffmanTree(vector<HaffmanTree> &h, const vector<int>w) {
    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<HaffmanTree> &h, int n, vector<deque<bool>> &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<int> weight = {7, 5, 2, 4};  //权向量
vector<HaffmanTree> haff(2 * weight.size() - 1);  //haffman树向量
vector<deque<bool>> encode(weight.size());  //  Haffman编码向量

int main ()
{
  CreateHaffmanTree(haff, weight);
  cout << "\n---叶子向量:vector<int>weight={7, 5, 2, 4};\n";
  cout << "*******哈夫曼树********" << endl;
  cout << "节点 左孩子 右孩子" << endl;
  for (vector<HaffmanTree>::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<bool>(cout));
    cout << "\n";
  }

  return 0;
}
Huffman树及编码C++实现

Huffman树及编码C++实现

By qianghaohao（Johar）

推荐阅读
