跳转至

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!

其它组测试数据类推

样例输入

1
2
3
4
5
6
7
8
9
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

样例输出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
A :1
B :010
C :011
D :001
E :000
1010001000011
error!
A :0
B :10
C :110
D :111
0100111
DAC

提示

解决方案

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#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;
}

评论