1 #ifndef __HFTREE_H__
 2 #include <string>
 3 template<class Type>
 4 class HFTree
 5 {
 6 private:
 7     struct Node
 8     {
 9         Type data;
10         int weight;
11         int parent, left, right;
12     };
13     Node* elem;
14     int length;
15 public:
16     struct HFCode
17     {
18         Type data;
19         std::string code;
20     };
21     HFTree(const Type* v, const int* w, int size);
22     void getCode(HFCode result[]);
23     ~HFTree() { delete[]elem; }
24 };
25 
26 template<class Type>
27 HFTree<Type>::HFTree(const Type* v, const int* w, int size)
28 {
29     const int MAX_INT = 32767;
30     int min1, min2;
31     int x, y;
32 
33     length = 2 * size;
34     elem = new Node[length];
35     for (int i = 0; i < length; ++i)
36     {
37         elem[i].weight = w[i - size];
38         elem[i].data = v[i - size];
39         elem[i].parent = elem[i].left = elem[i].right = 0;
40     }
41 
42     for (int i = size - 1; i > 0; --i)
43     {
44         min1 = min2 = MAX_INT;
45         x = y = 0;
46         for (int j = i + 1; j < length; ++j)
47         {
48             if (elem[j].parent == 0)
49             {
50                 if (elem[j].weight < min1)
51                 {
52                     min2 = min1;
53                     min1 = elem[j].weight;
54                     x = y;
55                     y = j;
56                 }
57             }
58             else if (elem[j].weight < min2)
59             {
60                 min2 = elem[j].weight;
61                 x = j;
62             }
63             elem[i].weight = min1 + min2;
64             elem[i].left = x;
65             elem[i].right = y;
66             elem[i].parent = 0;
67             elem[x].parent = i;
68             elem[y].parent = i;
69         }
70     }
71 }
72 
73 template<class Type>
74 void HFTree<Type>::getCode(HFCode result[])
75 {
76     int size = length / 2;
77     int p, s;
78     for (int i = size; i < length; ++i)
79     {
80         result[i - size].data = elem[i].data;
81         result[i - size].code = "";
82         p = elem[i].parent;
83         s = i;
84         while (p)
85         {
86             if (elem[p].left == s)
87             {
88                 result[i - size].code = '0' + result[i - size].code;
89             }
90             else
91             {
92                 result[i - size].code = '1' + result[i - size].code;
93             }
94             s = p;
95             p = elem[p].parent;
96         }
97     }
98 }
99 #endif // !__HFTREE_H__

 1 #include "HFTree.hpp"
 2 #include <iostream>
 3 int main(int argc, char* argv[])
 4 {
 5     char ch[] = { "seistdn" };
 6     int w[] = { 10,15,12,3,4,13,1 };
 7     HFTree<char>tree(ch, w, 7);
 8     HFTree<char>::HFCode result[7];
 9     tree.getCode(result);
10     for (int i = 0; i < 7; ++i)
11     {
12         std::cout << result[i].data << ' ' << result[i].code << std::endl;
13     }
14     return 0;
15 }