【哈夫曼树】基本概念、构建过程及C++代码

简介: 【哈夫曼树】基本概念、构建过程及C++代码


关于哈夫曼树的基本概念

1.在一棵树中,从一个结点往下可以达到的结点之间的通路,称为路径

2.某一路径所经过的“边”的数量,称为该路径的路径长度
3.若将树中结点赋给一个带有某种含义的数值,则该数值称为该结点的

4.从根结点到该结点之间的路径长度与该结点的权的乘积,称为该结点的带权路径长度

5.树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL

6.给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,则称该二叉树为哈夫曼树,也被称为最优二叉树


根据树的带权路径长度的计算规则,我们应该尽可能地让权值大的叶子结点靠近根结点,让权值小的叶子结点远离根结点,这样便能使得这棵二叉树的带权路径长度达到最小。


哈夫曼树的构建过程

给定n个权值分别为w1,w2,…wn的结点,哈夫曼树的构造过程如下:

  1. 将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F。
  2. 构造一个新结点,从F中选取两棵根结点权值最小的树作为新结点的左、右子树,新结点的权值为左、右子树上的权值之和。
  3. 从F中删除刚刚选择的两棵树,同时将新得到的树加入到F中。
  4. 重复步骤2、3,直到F中只剩下一棵树为止。

哈夫曼树的特点

  1. 每个初始结点最后都变成了叶结点,且权值越小的叶结点的路径长度越大。
  2. 构建过程中共构建了n-1个结点,因此哈夫曼树的总结点数为2n-1.
  3. 每次构造都选择两个结点,因此哈夫曼树不存在度为1的结点。

代码展示

由于普通的C语言实现的代码在大多数地方都能找到,这里就只展示C++改进的代码

#include<iostream>
#include<string>
#include<string.h>
#include<vector> 
using namespace std;
typedef int ElemType;
typedef vector<string> HuffmanCode; //哈夫曼编码 
vector<int> w;            //输入的权值
int n;                //结点总数 
/*哈夫曼树结点类*/ 
class HTNode{
  public:
    ElemType weight;  //权值
    int parent;     //父节点
    int lChild, rChild; //左右孩子 
    //构造函数 
    HTNode(){
      weight = parent = lChild = rChild = 0;
    }
    HTNode(int weight){
      this->weight = weight;
      parent = lChild = rChild = 0;
    }
    //输出运算符重载
    friend std::ostream &operator << (std::ostream &output, HTNode &h){
      output << h.weight;
      return output;
    } 
};
/*哈夫曼树操作类*/ 
class Huff{
  private:
    vector<HTNode> T; //内部维护一棵哈夫曼树 
    int m;        //哈夫曼树结点总数    
    void Select(int n, int &s1, int &s2){
      int min;
      for(int i = 1; i <= n; i++){  //找到第一个还没有双亲的叶子结点 
        if(T[i].parent == 0){
          min = i;
          break;
        }
      }
      for(int i = min+1; i <= n; i++){//向后迭代找到最小的 
        if(T[i].parent == 0 && T[i].weight < T[min].weight)
          min = i;
      }
      s1 = min; //第一个最小值给s1
      for(int i = 1; i <= n; i++){  //同上,找到第二小的 
        if(T[i].parent == 0 && i != s1){
          min = i;
          break;
        }
      } 
      for(int i = min+1; i <= n; i++){
        if(T[i].parent == 0 && T[i].weight < T[min].weight && i != s1)
          min = i;
      }
      s2 = min; //第二个最小值给s2 
    }
  public:
    //构造函数 
    Huff(){
      m = 2*n-1;
      T.resize(m+1);//初始化数组长度
      for(int i = 0; i < m; i++) T[i] = 0;
    }
    /*构建哈夫曼树*/
    void CreateHuff(){
      for(int i = 1; i <= n; i++){
        HTNode ht(w[i-1]);
        T[i] = ht;    //赋权值给n个叶子结点 
      } 
      for(int i = n+1; i <= m; i++){
        //每次选择权值最小的结点s1,s2
        int s1, s2; 
        Select(i-1, s1, s2);
        T[i].weight = T[s1].weight+T[s2].weight;
        T[s1].parent = i;
        T[s2].parent = i;
        T[i].lChild = s1;
        T[i].rChild = s2;
//        cout << s1 << " " << s2 << "\t" << T[s1].parent << " " << T[s2].parent << endl;       
//        HTNode ht = T[i];
//        cout << ht << endl;
      }       
    }
    /*生成哈夫曼编码*/
    void HuffCoding(HuffmanCode &HC){
      string code;
      for(int i = 1; i <= n; i++){
        int c = i;          //正在进行的第i个数据的编码
        int p = T[c].parent;  //找到该数据的父结点
        while(p){       //直到父结点为0,即父结点为根结点时,停止
          //如果该结点是其父结点的左孩子,则编码为0,否则为1
          if(T[p].lChild == c) code = '0'+code;
          else code = '1'+code;
          c = p;        //继续往上进行编码
          p = T[c].parent;  //c的父结点
        }
        HC.push_back(code);   //将编码插入到数组中 
        code.clear();
      }
      for(int i = 1; i <= n; i++){
        cout << "数据" << T[i].weight << "的编码为:" << HC[i-1] << endl;
      } 
    }
    void disp(){
      cout << "哈夫曼树为:" << endl;
      cout << "下标   权值     父结点   左孩子   右孩子" << endl;
      cout << "0                                  " << endl;
      for (int i = 1; i <= m; i++){
        cout << i << '\t' << T[i].weight << '\t' << T[i].parent << '\t' << T[i].lChild << '\t' << T[i].rChild << endl;
      }
      cout << endl;
    }
}; 
int main(){
  int x;
  cout << "请输入数据的个数:";
  cin >> n;
  cout << "请输入数据:";
  for(int i = 0; i < n; i++) {
    cin >> x;
    w.push_back(x);
  }
  Huff h;
  h.CreateHuff();
  h.disp();
  HuffmanCode HC;
  h.HuffCoding(HC); 
  return 0;
}
/*
测试集 
5
23 4 5 51 16
运行效果:
请输入数据的个数:5
请输入数据:23 4 5 51 16
哈夫曼树为:
下标   权值     父结点   左孩子   右孩子
0
1       23      8       0       0
2       4       6       0       0
3       5       6       0       0
4       51      9       0       0
5       16      7       0       0
6       9       7       2       3
7       25      8       6       5
8       48      9       1       7
9       99      0       8       4
数据23的编码为:00
数据4的编码为:0100
数据5的编码为:0101
数据51的编码为:1
数据16的编码为:011 
*/
相关文章
|
2天前
|
编译器 C++
C++ 一种在编译阶段就能解决代码的技术
C++ 一种在编译阶段就能解决代码的技术
13 3
|
3天前
|
存储 关系型数据库 MySQL
C语言/C++雷霆战机代码(终极版)
C语言/C++雷霆战机代码(终极版)
C语言/C++雷霆战机代码(终极版)
|
3天前
|
存储 关系型数据库 MySQL
C语言/C++实战项目雷霆飞机(代码改进)
C语言/C++实战项目雷霆飞机(代码改进)
|
20天前
|
存储 算法 C语言
【编程陷阱】编写出色C++代码:遵循的注意事项和最佳实践
【编程陷阱】编写出色C++代码:遵循的注意事项和最佳实践
6 0
|
27天前
|
存储 机器学习/深度学习 算法
使用 OpenCV4 和 C++ 构建计算机视觉项目:1~5
使用 OpenCV4 和 C++ 构建计算机视觉项目:1~5
36 0
|
28天前
|
传感器 C++ 计算机视觉
【opencv3】详述PnP测距完整流程(附C++代码)
【opencv3】详述PnP测距完整流程(附C++代码)
|
1月前
|
C++
C++多态之虚函数表详解及代码示例
C++多态之虚函数表详解及代码示例
|
1月前
|
C++
C++多态详解及代码示例
C++多态详解及代码示例
|
1月前
|
编译器 C++
C++模板之——类模板详解及代码示例
C++模板之——类模板详解及代码示例
C++模板之——类模板详解及代码示例
|
1月前
|
C++
C++模板之——函数模板详解及代码示例
C++模板之——函数模板详解及代码示例
C++模板之——函数模板详解及代码示例

热门文章

最新文章

相关产品

  • 云迁移中心