跳转至

DS二叉树——Huffman编码与解码

时间限制: 1 Sec 内存限制: 128 MB

题目描述

1、问题描述

给定n个字符及其对应的权值,构造Huffman树,并进行huffman编码和译(解)码。

构造Huffman树时,要求左子树根的权值小于、等于右子树根的权值。

进行Huffman编码时,假定Huffman树的左分支上编码为‘0’,右分支上编码为‘1’。

2、算法

构造Huffman树算法:

⑴ 根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn},其中每棵二叉树Ti中只有一个权值为wi的根结点。

⑵ 在F中选取两棵根结点的权值最小的树,作为左、右子树构造一棵新的二叉树,且置其根结点的权值为其左、右子树权值之和。

⑶ 在F中删除这两棵树,同时将新得到的二叉树加入F中。

(4) 重复⑵, ⑶,直到F只含一棵树为止。

3、Huffman编码算法:

⑴ 从Huffman树的每一个叶子结点开始。

⑵ 依次沿结点到根的路径,判断该结点是父亲结点的左孩子还是右孩子,如果是左孩子则得到编码‘0’,否则得到编码‘1’,先得到的编码放在后面。

⑶ 直到到达根结点,编码序列即为该叶子结点对应的Huffman编码。

4、Huffman译(解)码算法:

⑴ 指针指向Huffman树的根结点,取第一个Huffman码。

⑵ 如果Huffman码为‘0’,将指针指向当前结点的左子树的根结点;如果Huffman码为‘1’,将指针指向当前结点的右子树的根结点。

⑶ 如果指针指向的当前结点为叶子结点,则输出叶子结点对应的字符;否则,取下一个Huffman码,并返回⑵。

⑷ 如果Huffman码序列未结束,则返回⑴继续译码。

输入

第一行测试次数

第2行:第一组测试数据的字符个数n,后跟n个字符

第3行:第一组测试数据的字符权重

待编码的字符串s1

编码串s2

其它组测试数据类推

输出

第一行~第n行,第一组测试数据各字符编码值

第n+1行,串s1的编码值

第n+2行,串s2的解码值,若解码不成功,输出error!

其它组测试数据类推

样例输入

2
5 A B C D E
15 4 4 3 2
ABDEC
00000101100
4 A B C D
7 5 2 4
ABAD
1110110

样例输出

A :1
B :010
C :011
D :001
E :000
1010001000011
error!
A :0
B :10
C :110
D :111
0100111
DAC

提示

解决方案

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

struct Node {
    char data;
    int freq;
    std::string pattern;
    Node *left, *right;

    Node() : data(0), freq(0), left(NULL), right(NULL) {}

    Node(const char data, const int freq) : data(data), freq(freq), left(NULL), right(NULL) {}
};

bool compare(const Node *lhs, const Node *rhs) {
    return lhs->freq < rhs->freq;
}

class Huffman {
public:
    explicit Huffman(std::vector<Node *> &elements) {
        std::vector<Node *> elements_;
        elements_.assign(elements.begin(), elements.end());
        this->elements_ = elements;
        while (elements_.size() != 1) {
            std::sort(elements_.begin(), elements_.end(), compare);
            Node *leftChild = elements_.front();
            elements_.erase(elements_.begin());
            Node *rightChild = elements_.front();
            elements_.erase(elements_.begin());
            Node *node = new Node(0, leftChild->freq + rightChild->freq);
            node->left = leftChild;
            node->right = rightChild;
            elements_.push_back(node);
        }
        root_ = elements_.front();
        std::string pattern;
        generate(root_, pattern);
        for (int i = 0; i < this->elements_.size(); ++i) {
            std::cout << this->elements_[i]->data << " :" << this->elements_[i]->pattern << std::endl;
        }
    }

    void encode(const std::string &string) {
        std::string encode;
        for (int i1 = 0; i1 < string.length(); ++i1) {
            for (int i2 = 0; i2 < elements_.size(); ++i2) {
                if (elements_[i2]->data == string[i1]) {
                    encode += elements_[i2]->pattern;
                }
            }
        }
        std::cout << encode << std::endl;
    }

    void decode(const std::string &string) {
        std::string decode;
        Node *ptr = root_;
        for (int i1 = 0; i1 < string.size(); ++i1) {
            if (string[i1] == '0') {
                ptr = ptr->left;
            } else {
                ptr = ptr->right;
            }
            if (ptr == NULL) {
                std::cout << "error!" << std::endl;
                return;
            } else if (ptr->data != 0) {
                decode.push_back(ptr->data);
                ptr = root_;
            }
        }
        if (ptr == root_) {
            std::cout << decode << std::endl;
        } else {
            std::cout << "error!" << std::endl;
        }
    }

private:
    Node *root_;
    std::vector<Node *> elements_;

    void generate(Node *node, std::string &pattern) {
        if (node) {
            if (node->data != 0) {
                node->pattern.assign(pattern);
            }
            pattern.push_back('0');
            generate(node->left, pattern);
            pattern.erase(pattern.end() - 1);
            pattern.push_back('1');
            generate(node->right, pattern);
            pattern.erase(pattern.end() - 1);
        }
    }
};

int main() {
    int ctrl;
    std::cin >> ctrl;

    while (ctrl--) {
        int size;
        std::cin >> size;
        std::vector<Node *> elements(size);
        for (int i = 0; i < size; ++i) {
            elements[i] = new Node();
            std::cin >> elements[i]->data;
        }
        for (int i = 0; i < size; ++i) {
            std::cin >> elements[i]->freq;
        }
        class Huffman huffman(elements);
        std::string string;
        std::cin >> string;
        huffman.encode(string);
        std::cin >> string;
        huffman.decode(string);
    }

    return 0;
}

评论