哈夫曼树的实现-白红宇

哈夫曼树的实现

阅读量：5899 次

发布时间：2019-06-19

本文共 2720 字，大约阅读时间需要 9 分钟。

本来用之前也过的堆直接实现比较好，这里我直接重新写一了函数融入进去了

1 #pragma once  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 using namespace std;  7   8 template
         
            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
          
            24 class HuffmanTree 25 { 26 public: 27 HuffmanTree() 28 :_root(NULL) 29 { 30 31 } 32 HuffmanNode
           
             *ReturnRootNode() 33 { 34 return _root; 35 } 36 //vector
            
              HuffmanCode(T* a,size_t size) 37 //{ 38 // vector
             
               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
              
               
                 *> v; 49 for (int i = 0; i < size; ++i) 50 { 51 if (a[i] != invalid) 52 { 53 v.push_back(new HuffmanNode
                
                 (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
                 
                   *left = v[0]; 63 swap(v[0], v[v.size() - 1]); 64 v.pop_back(); 65 AdjustDown(v, 0, v.size()); 66 HuffmanNode
                  
                    *right = v[0]; 67 swap(v[0], v[v.size() - 1]); 68 v.pop_back(); 69 AdjustDown(v, 0, v.size()); 70 HuffmanNode
                   
                     *parent = new HuffmanNode
                    
                     (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
                     
                      
                        *> &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
                       
                         *_Find(HuffmanNode
                        
                          *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 else113 {114 str.push_back('0');115 HuffmanNode
                         
                           *tmp = _Find(root->_left,str, x);116 if (root->_left && tmp)117 {118 return tmp;119 }120 else121 {122 str.push_back('1');123 HuffmanNode
                          
                            *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
                           
                             *_root;136 };