哈夫曼树与哈夫曼编码详解及C++模板实现 - c++编程基础

TOP

哈夫曼树与哈夫曼编码详解及C++模板实现(一)

2016-12-06 20:24:36 【大中小】浏览:543次

哈夫曼树又称最优二叉树，是带权路径长度最短的树，可用来构造最优编码，用于信息传输、数据压缩等方面，是一种应用广泛的二叉树。
这里写图片描述

几个相关的基本概念：

1.路径：从树中一个结点到另一个结点之间的分支序列构成两个节点间的路径
2.路径长度：路径上的分支的条数称为路径长度
3.树的路径长度：从树根到每个结点的路径长度之和称为树的路径长度
4.结点的权：给树中结点赋予一个数值，该数值称为结点的权
5.带权路径长度：结点到树根间的路径长度与结点的权的乘积，称为该结点的带权路径长度
6.树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记为WPL
7.最优二叉树：在叶子个数n以及各叶子的权值确定的条件下，树的带权路径长度WPL值最下的二叉树称为最优二叉树。

哈夫曼树的建立

由哈夫曼最早给出的建立最优二叉树的带有一般规律的算法，俗称哈夫曼算法。描述如下：
1):初始化：根据给定的n个权值(Ｗ1,Ｗ2,…，Ｗn)，构造n棵二叉树的森林集合F={Ｔ1,Ｔ2,…,Ｔn}，其中每棵二叉树Ｔi只有一个权值为Ｗi的根节点，左右子树均为空。

2):找最小树并构造新树：在森林集合F中选取两棵根的权值最小的树做为左右子树构造一棵新的二叉树，新的二叉树的根结点为新增加的结点，其权值为左右子树的权值之和。

3):删除与插入：在森林集合F中删除已选取的两棵根的权值最小的树，同时将新构造的二叉树加入到森林集合F中。

4):重复2)和3)步骤，直至森林集合F中只含一棵树为止，这颗树便是哈夫曼树，即最优二叉树。由于2)和3)步骤每重复一次，删除掉两棵树，增加一棵树，所以2)和3)步骤重复n-1次即可获得哈夫曼树。

下图展示了有4个叶子且权值分别为{9,6,3,1}的一棵最优二叉树的建立过程。

这里写图片描述

C++类模板构造哈夫曼树

哈夫曼树的节点结构

/*哈夫曼树的节点定义*/
template 
  
   
struct HuffmanNode
{
    //初始化
    HuffmanNode(T k,HuffmanNode
   
    * l,HuffmanNode
    
     * r):key(k),lchild(l),rchild(r),flag(0) {} T key; //节点权值 HuffmanNode
     
      * lchild; //节点左孩 HuffmanNode
      
       * rchild; //节点右孩 int flag; //标志　判断是否从森林中删除 };

哈夫曼树的抽象数据类型

template 
  
   
class Huffman
{
public:
    void preOrder();        //前序遍历哈夫曼树
    void inOrder();         //中序遍历哈夫曼树
    void postOrder();       //后序遍历哈夫曼树

    void creat(T a[],int size); //创建哈夫曼树
    void destory();             //销毁哈夫曼树
    void print();               //打印哈夫曼树

    void my_sort(int size);
    Huffman():root(NULL) {}
    ~Huffman(){
        destory(root);
    }
private:
    void preOrder(HuffmanNode
   
    * pnode); //前序遍历二叉树 void inOrder(HuffmanNode
    
     * pnode); //中序遍历二叉树 void postOrder(HuffmanNode
     
      * pnode); //后序遍历二叉树 void print(HuffmanNode
      
       * pnode); //打印二叉树 void destory(HuffmanNode
       
        * pnode); //销毁二叉树 HuffmanNode
        
         * root; 　//哈夫曼树根节点 HuffmanNode
         
          * forest[MAXSIZE];　//用数组来存储森林中树的根节点 };

具体实现

/*自写排序*/
template 
  
   
void Huffman
   
    ::my_sort(int size) { for(int i=0;i
    
     key > forest[j]->key) { swap(forest[i],forest[j]); } else continue; } } }; /*创建哈夫曼树*/ template 
     
       void Huffman
      
       ::creat(T a[],int size) { int j,k=0; /*每个节点都作为一个森林*/ for(int i=0; i
       
        * ptr = new HuffmanNode
        
         (a[i],NULL,NULL); forest[i] = ptr; //双向队列尾部加入一个元素 } for(int i=0; i
         
          flag!=1 && forest[j+1]->flag != 1) { /*构建新节点*/ HuffmanNode
          
           * node = new HuffmanNode
           
            (forest[j]->key + forest[j+1]->key,forest[j],forest[j+1]); /*新节点加入森林中*/ forest[size+k] = node; k++; /*删除两棵权值最小的树*/ forest[j]->flag = 1; forest[j+1]->flag = 1; break; } else continue; } } root = forest[size+k-1]; }; /*前序遍历哈夫曼树*/ template 
            
              void Huffman
             
              ::preOrder(HuffmanNode
              
               * pnode) { if(pnode != NULL) { cout << pnode -> key; preOrder(pnode->lchild); preOrder(pnode->rchild); } }; template 
               
                 void Huffman
                
                 ::preOrder() { preOrder(root); }; /*中序遍历哈夫曼树*/ template 
                 
                   void Huffman
                  
                   ::inOrder(HuffmanNode
                   
                    * pnode) { if(pnode != NULL) { inOrder(pnode->lchild); cout << pnode -> key; inOrder(pnode->rchild); } }; template 
                    
                      void Huffman
                     
                      ::inOrder() { inOrder(root); }; /*后序遍历哈夫曼树*/ template 
                      
                        void Huffman
                       
                        ::postOrder(HuffmanNode
                        
                         * pnode) { if(pnode != NULL) { postOrder(pnode->lchild); postOrder(pnode->rchild); cout << pnode -> key; } }; template 
                         
                           void Huffman
                          
                           ::postOrder() { postOrder(root); }; /*打印哈夫曼树*/ template 
                           
                             void Huffman
                            
                             ::print(HuffmanNode
                             
                              * pnode) { if(pnode != NULL) { cout << "当前结点：" << pnode -> key << "."; if(pnode -> lchild != NULL) cout << "它的左孩子结点为：" << pnode->lchild->key << "."; else cout << "它没有左孩子."; if(pnode -> rchild != NULL) cout << "它的右孩子结点为：" << pnode->rchild->key << "."; else cout << "它没有右孩子."; cout << endl; print(pnode->lchild); print(pnode->rchild); } }; template 
                              
                                void Huffman
                               
                                ::print() { print(root); }; /*销毁哈夫曼树*/ template 
                                
                                  vo

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：C++11的模板类型判断：std::is_sa..	下一篇：c++中的参数传递方式