本來用之前也過的堆直接實現比較好，這裡我直接重新寫一了函數融入進去了
1 #pragma once
2 #include<iostream>
3 #include<vector>
4 #include<stack>
5 #include<string>
6 using namespace std;
7
8 template<class T>
9 struct HuffmanNode
10 {
11 T _value;
12 HuffmanNode* _left;
13 HuffmanNode* _right;
14 HuffmanNode(T x)
15 :_value(x)
16 , _left(NULL)
17 , _right(NULL)
18 {
19
20 }
21 };
22
23 template<class T>
24 class HuffmanTree
25 {
26 public:
27 HuffmanTree()
28 :_root(NULL)
29 {
30
31 }
32 HuffmanNode<T> *ReturnRootNode()
33 {
34 return _root;
35 }
36 //vector<string> HuffmanCode(T* a,size_t size)
37 //{
38 // vector<string> test;
39 // test.resize(size);
40 // for (int i = 0; i < size; ++i)
41 // {
42 // _Find(_root, test[i], a[i]);
43 // }
44 // return test;
45 //}
46 void CreateHuffmanTree(T *a, size_t size,T& invalid)
47 {
48 vector<HuffmanNode<T> *> v;
49 for (int i = 0; i < size; ++i)
50 {
51 if (a[i] != invalid)
52 {
53 v.push_back(new HuffmanNode<T>(a[i]));
54 }
55 }
56 for (int i = (v.size() - 2) / 2; i >= 0; --i)
57 {
58 AdjustDown(v, i, v.size());
59 }
60 while (v.size() > 1)
61 {
62 HuffmanNode<T> *left = v[0];
63 swap(v[0], v[v.size() - 1]);
64 v.pop_back();
65 AdjustDown(v, 0, v.size());
66 HuffmanNode<T> *right = v[0];
67 swap(v[0], v[v.size() - 1]);
68 v.pop_back();
69 AdjustDown(v, 0, v.size());
70 HuffmanNode<T> *parent = new HuffmanNode<T>(left->_value + right->_value);
71 parent->_left = left;
72 parent->_right = right;
73 v.push_back(parent);
74 AdjustDown(v, 0, v.size());
75 }
76 _root = v[0];
77 v.pop_back();
78 }
79 protected:
80 void AdjustDown(vector<HuffmanNode<T> *> &a, int root, size_t size)
81 {
82 int child = root * 2 + 1;
83 while (child < size)
84 {
85 if (child + 1 < size && a[child + 1]->_value < a[child]->_value)
86 {
87 child++;
88 }
89 if (a[child]->_value < a[root]->_value)
90 {
91 swap(a[child], a[root]);
92 root = child;
93 child = root * 2 + 1;
94 }
95 else
96 {
97 break;
98 }
99 }
100 }
101 /*HuffmanNode<T> *_Find(HuffmanNode<T> *root,string &str, const T &x)
102 {
103 if (root == NULL)
104 {
105 str.pop_back();
106 return NULL;
107 }
108 if (root->_value == x && root->_left==NULL && root->_right==NULL)
109 {
110 return root;
111 }
112 else
113 {
114 str.push_back('0');
115 HuffmanNode<T> *tmp = _Find(root->_left,str, x);
116 if (root->_left && tmp)
117 {
118 return tmp;
119 }
120 else
121 {
122 str.push_back('1');
123 HuffmanNode<T> *tmp2 = _Find(root->_right, str, x);
124 if (tmp == NULL && tmp2 == NULL)
125 {
126 str.pop_back();
127 }
128 return tmp2;
129 }
130 }
131 return NULL;
132 }*/
133
134 protected:
135 HuffmanNode<T> *_root;
136 };
注釋部分的代碼，是用來進行哈夫曼編碼的，這種編碼方式就不需要使用三叉鏈的樹了（帶有parent指針的三叉樹）
