哈夫曼樹的實現

本來用之前也過的堆直接實現比較好，這裡我直接重新寫一了函數融入進去了

  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指針的三叉樹）