什么是哈夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

关键

构建哈夫曼树的关键就是对于叶结点的关注，叶结点是怎么拼起来的？（每次权重最小的先拼起来，然后到最后就是得到权重——频率高的就越接近根节点，从而其所需要的编码就少了，进而降低整体的编码数据量）

运用优先队列来进行自动排序

代码如下：

void HuffmanTree::initialize(int n) {
    char c[MAX];
    double f[MAX];
    string line;
    getline(cin, line);
    if (n == -1) { // 需要通过给定文件去建立相应的树的出现的频率，HuffmaTree.txt文件里面是上半部分字母，下部分呢为数字
        if (root == NULL) { // 就是只有当内存里面没有建立HuffmanTree的时候才进行建树操作，跟题目要求的一样（每次执行解码、译码的时候，不需要每次都进行哈夫曼树的初始化操作）
            ifstream ifst("HuffmanTree.txt");  // 其实接下来的操作主要还是依据文件里面的内容构造来搞的
            int rows = 0;
            char temp;
            ifst.get(temp);
            while (ifst.get(temp)) {
                if (temp == '\n') rows++;
            }
            ifst.close();
            ifstream ifs("HuffmanTree.txt");
            for (int i = 0; i < rows; i++) {
                getline(ifs, line);
                if (i < rows / 2) {
                    if (!line.empty()) { c[i] = line[0]; }
                    else c[i] = ' ';
                }
                else {
                    f[i - rows / 2] = stod(line);
                }
            }
            root = createTree(c, f, rows/2);
            saveInfo(root, ""); // 用charCode进行保存
            ifs.close();
        }
    }
    else {
        cout << "请先输入要编码的字符，然后对应每个字符输入相应的频率，每个内容请用回车进行分隔：" << endl;
        string line;
        ofstream ofs("HuffmanTree.txt");
        for (int i = 0; i < n; i++) {
            getline(cin, line);
            if (!line.empty()) c[i] = line[0];
            else c[i] = ' ';
            ofs << line << endl;
        }
        for (int i = 0; i < n; i++) {
            getline(cin, line);
            f[i] = stod(line);
            ofs << line << endl;
        }
        root = createTree(c, f, n);
        saveInfo(root, "");
        ofs.close(); // 每次用完后记得关闭，避免出现后续出现打开错误的问题
    }
}

node* HuffmanTree::createTree(char c[], double f[], int n) {
    // 此处先将c,f这两个数组的数据进行合并得到charSet先
    for (int i = 0; i < n; i++) { charSet[c[i]] = f[i]; }
    // 此处通过创建优先队列priority_queue使得可以每次取频率最小的两个节点进行合并
    priority_queue<node*, vector<node*>, cmp> q;
    // 此处可以不用迭代器进行，可以直接数组，我先给出数组的写法
    /*for (int i = 0; i < n; i++) {
        newnode = node(c[i], f[i]);
    }*/
    // 但是既然用到了map，那就尝试一下用迭代器对charSet
    for (map<char, double>::iterator p = charSet.begin(); p != charSet.end(); p++) {
        q.push(new node(p->first, p->second));
    }
    while (q.size() > 1) {
        node* temp1 = q.top();
        q.pop();
        node* temp2 = q.top();
        q.pop();
        q.push(new node(0, temp1->frequence + temp2->frequence, temp1, temp2));
    }
    root = q.top();
    if (root == NULL) {  return NULL; } // 创建哈夫曼树失败
    else return root;
}



其中运用到的词典——map、pair、自定义排序对我而言都是新知识