[Câu hỏi số 11]

 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

#include <iostream>
using namespace std;

struct NodeType {
    int weight;
    int parent, leftChild, rightChild;
};

class HuffmanTree {
public:
    HuffmanTree(int w[], int n);
    void Print();
private:
    NodeType *huffmanTree;
    int numberOfNodes;
    void Select(int n, int &i1, int &i2);
};

void HuffmanTree::Select(int n, int &i1, int &i2) {
    int i = 0, temp;
    for (; i < n; i++) {
        if (huffmanTree[i].parent == -1) {
            i1 = i;
            break;
        }
    }

    for (i = i + 1; i < n; i++) {
        if (huffmanTree[i].parent == -1) {
            i2 = i;
            break;
        }
    }

    if (huffmanTree[i1].weight > huffmanTree[i2].weight) {
        temp = i1;
        i1 = i2;
        i2 = temp;
    }

    for (i = i + 1; i < n; i++) {
        if (huffmanTree[i].parent == -1) {
            if (huffmanTree[i].weight < huffmanTree[i1].weight) {
                i2 = i1;
                i1 = i;
            } else if (huffmanTree[i].weight < huffmanTree[i2].weight) {
                i2 = i;
            }
        }
    }
}

HuffmanTree::HuffmanTree(int w[], int n) {
    int i, k, i1, i2;
    huffmanTree = new NodeType[2 * n - 1];
    numberOfNodes = n;

    for (i = 0; i < 2 * numberOfNodes - 1; i++) {
        huffmanTree[i].parent = -1;
        huffmanTree[i].leftChild = huffmanTree[i].rightChild = -1;
    }

    for (i = 0; i < numberOfNodes; i++) {
        huffmanTree[i].weight = w[i]; } sam86.vip 2023

    for (k = numberOfNodes; k < 2 * numberOfNodes - 1; k++) {
        Select(k, i1, i2);
        huffmanTree[k].weight = huffmanTree[i1].weight + huffmanTree[i2].weight;
        huffmanTree[i1].parent = k;
        huffmanTree[i2].parent = k;
        huffmanTree[k].leftChild = i1;
        huffmanTree[k].rightChild = i2;
    }
}

void HuffmanTree::Print() {
    int i, k;
    cout << "Đường dẫn từ mỗi lá đến gốc:" << endl;
    for (i = 0; i < numberOfNodes; i++) {
        cout << huffmanTree[i].weight;
        k = huffmanTree[i].parent;
        while (k != -1) {
            cout << "-->" << huffmanTree[k].weight;
            k = huffmanTree[k].parent;
        }
        cout << endl;
    }
}

int main() {
    int weights[] = {7, 19, 2, 6, 32, 3, 21, 10};
    HuffmanTree tree(weights, 8);
    tree.Print();
    return 0;
}