Huffman树的实现

POJ 给定字符串，编码效率对比

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int main() {
    string s;
    priority_queue<int, vector<int>, greater<int> > Q;
    puts("ACSII coding and Huffman coding efficiency comparison\n");
    while (printf("Input string:\n"), getline(cin, s) && s != "END") {
        sort(s.begin(), s.end());
        int t = 1;
        for (int i = 1; i < s.length(); ++i)
            if (s[i] != s[i - 1])
                Q.push(t), t = 1;
            else
                ++t;
        Q.push(t);
        int ans = 0, a, b;
        if (Q.size() == 1) ans = Q.top();
        while (Q.size() > 1) {
            a = Q.top(), Q.pop();
            b = Q.top(), Q.pop();
            Q.push(a + b);
            ans += a + b;
        }
        Q.pop();
        printf(
            "\nASCII Coding\t\t%lu byte\nHuffman Coding\t\t%d byte\nCompression ratio\t%.2f\n\n",
            s.size() * 8, ans, (s.size() * 8.0) / ans);
    }
    return 0;
}

哈夫曼树实现

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
class HuffmanTree {
    struct node {
        int weight;
        struct node *Lchild, *Rchild;
        bool operator<(const node &x) const { return weight < x.weight; }
        bool operator>(const node &x) const { return weight > x.weight; }
    };

    typedef priority_queue<node, vector<node>, greater<node> > HuffQueue;

    HuffQueue GetWeight() {
        cout << "Input nodes&#39; power, end with -1" << endl;
        HuffQueue q;
        int temp;
        while (cin >> temp, temp != -1) q.push({temp, NULL, NULL});
        return q;
    }

    node *CreatHuffmanTree(HuffQueue q) {
        node *root = new node;
        if (q.size() == 1) {
            *root = q.top();
            return root;
        }
        while (q.size() > 1) {
            node *Lch = new node, *Rch = new node, *P = new node;
            *Lch = q.top(), q.pop();
            *Rch = q.top(), q.pop();
            P->Lchild = Lch, P->Rchild = Rch,
            P->weight = Lch->weight + Rch->weight;
            q.push(*P);
        }
        *root = q.top();
        return root;
    }

    void PreOrderVisit(node *root) {
        if (root == NULL) return;
        if (root->Lchild == NULL && root->Rchild == NULL) printf("LeafNode");
        printf("%d\n", root->weight);
        PreOrderVisit(root->Lchild);
        PreOrderVisit(root->Rchild);
    }

    void DestoryHuffmanTree(node *root) {
        if (root == NULL) return;
        DestoryHuffmanTree(root->Lchild);
        DestoryHuffmanTree(root->Rchild);
        delete root;
    }

   public:
    void show() {
        HuffQueue q = GetWeight();
        node *root = CreatHuffmanTree(q);
        PreOrderVisit(root);
        DestoryHuffmanTree(root);
    }
};

int main() {
    HuffmanTree test;
    test.show();
    return 0;
}