【哈夫曼树】基本概念、构建过程及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 
*/
相关文章
|
3月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
193 0
|
29天前
|
Linux C语言 C++
vsCode远程执行c和c++代码并操控linux服务器完整教程
这篇文章提供了一个完整的教程,介绍如何在Visual Studio Code中配置和使用插件来远程执行C和C++代码,并操控Linux服务器,包括安装VSCode、安装插件、配置插件、配置编译工具、升级glibc和编写代码进行调试的步骤。
133 0
vsCode远程执行c和c++代码并操控linux服务器完整教程
|
1月前
|
程序员 C++ 开发者
C++入门教程:掌握函数重载、引用与内联函数的概念
通过上述介绍和实例,我们可以看到,函数重载提供了多态性;引用提高了函数调用的效率和便捷性;内联函数则在保证代码清晰的同时,提高了程序的运行效率。掌握这些概念,对于初学者来说是非常重要的,它们是提升C++编程技能的基石。
21 0
|
2月前
|
C++
继续更新完善:C++ 结构体代码转MASM32代码
继续更新完善:C++ 结构体代码转MASM32代码
|
2月前
|
C++ Windows
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
|
2月前
|
C++
2合1,整合C++类(Class)代码转换为MASM32代码的平台
2合1,整合C++类(Class)代码转换为MASM32代码的平台
|
2月前
|
C++
HTML+JavaScript构建一个将C/C++定义的ANSI字符串转换为MASM32定义的DWUniCode字符串的工具
HTML+JavaScript构建一个将C/C++定义的ANSI字符串转换为MASM32定义的DWUniCode字符串的工具
|
2月前
|
前端开发 C++ Windows
C++生成QML代码与QML里面集成QWidget
这篇文章介绍了如何在C++中生成QML代码,以及如何在QML中集成QWidget,包括使用Qt Widgets嵌入到QML界面中的技术示例。
|
3月前
|
C++
C++代码来计算一个点围绕另一个点旋转45度后的坐标
C++代码来计算一个点围绕另一个点旋转45度后的坐标
65 0
|
3月前
|
C++
Resharper c++ 使用Enter自动补全代码
Resharper c++ 使用Enter自动补全代码
35 0