1. Toy模板网首页
  2. > Toy博客

哈夫曼树详解及其应用(哈夫曼编码）

10月前 作者：any_ways 分类：Toy博客 阅读(49) 违法举报

这篇具有很好参考价值的文章主要介绍了哈夫曼树详解及其应用(哈夫曼编码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一，哈夫曼树的基本概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

结点的路径长度：两结点之间路径上的分支数

树的路径长度：从树根到每一个结点的路径长度之和．记作：ＴＬ

权（weight)：将树中结点赋给一个有着某种含义的数值，则这个数值秒针为该结点的权

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积．

树的带权路径长度：树中所有叶子结点的带权路径长度之和．记作:WPL(Weighted Path Length)

哈夫曼树：最优树（带权路径长度（ＷＰＬ）最短的树）

注：＂带权路径长度最短＂是在＂度相同＂的树中比较而得的结果，因此有最优二叉树，最优三叉树之称等等．

哈夫曼树：最优二叉树（带权路径长度最短的二叉树）

特点：

１满二叉树不一定是哈夫曼树．

２哈夫曼树中权越大的叶子离根越近．

３具有相同带权结点的哈夫曼树不惟一．

二，哈夫曼树的构造算法

因为哈夫曼树权越大的叶子离根越近的特点，所以，构造哈夫曼树时首先选择权值小的叶子结点．

哈夫曼算法（构造哈夫曼树的方法）

（１）根据n个给定的权值构成n棵二叉树的森林，森林中每一棵树只有一个带权的根结点（构造森林全是根）

（２）在森林中，选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和．（选用两小造新树）

（３）在森林中删除这两棵树，同时将新得到的二叉树加入到森林中．（删除两小添新人）

（４）重复（２）和（３），直到森林中只有一棵树为止，这棵树即为哈夫曼树．（重复２，３剩单根）

例：有４个结点a,b,c,d，权值分别人8,6,3,5,构造哈夫曼树

１，构造森林全是根

哈夫曼树详解及其应用(哈夫曼编码）

 ２，选用两小造新树

哈夫曼树详解及其应用(哈夫曼编码）

 ３，删除两小添新人

哈夫曼树详解及其应用(哈夫曼编码）

 ４，重复２，３剩单根

哈夫曼树详解及其应用(哈夫曼编码）

 当最后森林只剩下一个根时，这棵树就是哈夫曼树

哈夫曼树当中：

１，只有度为0或２的结点，没有度为１的结点

２，包含n个叶子结点的哈夫曼树中共有2n-1个结点

三，哈夫曼树构造算法的实现

这里采用顺序存储结构－－－一维结构数组

结点类型定义：(包含４个成员的结构体）

typedef struct{

        int weight;//权重

        int parent,lch,rch;//双亲，左孩子，右孩子

}HTNode,*HuffmanTree;

哈夫曼树中结点下标i weight parent lch rch
1
2
3
4
......
......
2n-1

 有n个叶子结点的哈夫曼树中共有2n-1个结点，这里为了方便，不使用0下标，数组大小为2n

先定义一个数组ＨuffmanTree H(H是一个指针，也可以是一个数组）

具体的实现如下：

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
typedef struct{
    int weight;//权重
    int parent,lch,rch;//双亲，左孩子，右孩子
}HTNode,*HuffmanTree;

int j = 0;
int k = 0;//设置两个全局变量j,k，用来接收两个最小权重在数组中的下标

int cmp(void* e1, void* e2)//配合qsort()函数的比较函数
{
    if(*(int*)e1 - *(int*)e2 > 0)return 1;
    else if(*(int*)e1 - *(int*)e2 < 0)return -1;
    else return 0;

}

int Select(HuffmanTree HT, int n)//找出权重最小的二个根结点在ＨＴ数组中的位置
{
    int i = 0;
    int p = 0;//用于控制数组arr，按顺序存储数据
    int arr[MAX_SIZE] = {0};//用于存储根结点的权重值，以便排序
    int count = 0;//用来记录arr数组中，有几个值需要排序
    for(i = 1; i <= n; i++)
    {
        if(HT[i].parent == 0&&HT[i].weight != 0)//必须是有权重值的根结点，才会被加入到arr数组当中
        {
            arr[++p-1] = HT[i].weight;
            count++;//arr有效元素个数+１，arr数组中初始化的0，不算有效元素
        }
    }
    qsort(arr, count, sizeof(int), cmp);//对arr数组中的权重值排序，而且只对有效元素排序，
    for(i = 1; i <= n; i++)
    {
        if(HT[i].weight == arr[0])//arr[0]是最小元素
        {
            j = i;
            break;
        }
    }
    for(i = 1; i <= n; i++)
    {
        if(HT[i].weight == arr[1] && i != j)//arr[1]是第二小的元素，且要保证arr[0]=arr[1]时,选取的两个下标不相同
        {
            k = i;
            break;
        }
    }
    return 0;
}
void CreatHuffmanTree(HuffmanTree HT, int n)
{
    int i = 0;
    int m = 0;
    if(n <= 1)return;
    m = 2*n - 1;
    HT = malloc(sizeof(HTNode)*(m+1));//有n个叶子，树就有2n-1个结点，0号位置不用，所以需要2n个结点大小
    for(i = 1; i <= m+1; i++)//将2n-1个元素初始化，lch,rch,parent设置为0
    {
        HT[i].lch = 0;
        HT[i].rch = 0;
        HT[i].parent = 0;
        HT[i].weight = 0;
    }
    for(i = 1; i <= n; i++)//设置叶子结点weight值（权重）
    {
        int input = 0;
        printf("请输入每个元素的权重:>");
        scanf("%d",&input);
        HT[i].weight = input;
    }
    //开始创建哈夫曼树
    for(i = 1; i < n; i++)//初始有n个根结点，就要新产生n-1个结点，循环一次产生一个
    {
        Select(HT, m+1);//得到权重最小的两个根结点在ＨＴ数组中的下标j,k
        HT[n+i].lch = j;//ＨＴ数组中有n个根结点，那么新生成的根结点下标从n+1开始
        HT[n+i].rch = k;//设置新根结点的孩子值
        HT[n+i].weight = HT[j].weight + HT[k].weight;//设置新根结点的权重值为两孩子权重值之和
        HT[j].parent = n+i;//新根结点的下标值为最小权值的两个结点的双亲
        HT[k].parent = n+i;
    }
}
int main()
{
    HuffmanTree HT = 0;
    CreatHuffmanTree(HT, MAX_SIZE);
    return 0;
}

四，哈夫曼树的应用（哈夫曼编码）

前缀编码：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀

什么样的前缀码能使得电文总长最短？－－－－－哈夫曼编码

１,统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）．

２,利用哈夫曼树的特点：权越大的叶子离根越近;将每个字符的概率值作为权值，构造哈夫曼树．则概率越大的结点，路径越短．

３,在哈夫曼树的每个分支上标上0或１：结点的左分支标0，右分支标１．把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码．

例：要传输的字符集Ｓ＝｛Ｄ，Ｉ，Ｃ，Ｔ，；｝

        字符出现频率　Ｗ＝｛２，４，２，３，３｝

那么构造出来的哈夫曼树就是：

哈夫曼树详解及其应用(哈夫曼编码）

 然后在哈夫曼树的每个分支上标上0或１，结点的左分支标0，右分支标１

哈夫曼树详解及其应用(哈夫曼编码）

 把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码．

那么Ｔ的编码为：00，；的编码为01，Ｉ的编码为10，Ｄ的编码为110，Ｃ的编码为111

如果这个字符集中有一段电文是｛ＤＩＴ；ＤＩＣ；ＴＤＩ；｝那么它的编码就可以写成：

1101000011101011101001101001

相反，如果收到的编码是100011001，那么翻译过来就是ＩＴＤ；

哈夫曼编码能够保证是前缀码，即每个编码都不是另一个编码的前缀

哈夫曼编码能够保证字符编码总长最短

所以，哈夫曼编码的性质有：

１，哈夫曼编码是前缀码

２，哈夫曼编码是最优前缀码

五，哈夫曼编码的算法实现

1,字符串翻译成哈夫曼编码

（１）首先以字符集对应的字符权重，创建哈夫曼树

（２）依次从每个叶子结点，往上回溯，如果有双亲，判断该叶子结点是双亲的左孩子还是右孩子，如果是左孩子，记录0，如果是右孩子，记录１，直到回溯到根结点，这些组合起来的0和１就是哈夫曼的编码，我们用一个指针数组存储每个叶子结点的哈夫曼编码

例：已知｛a,b,o,u,t}对应的出现频率为{3,4,5,6,7}

        那么a,b,o,u,t分别对应的哈夫曼编码是多少？

        ＂aoutbabtoutbaotubatobatu"对应的哈夫曼编码是多少？

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 5
typedef struct{
    int weight;//权重
    int parent,lch,rch;//双亲，左孩子，右孩子
}HTNode,*HuffmanTree;

int j = 0;
int k = 0;//设置两个全局变量j,k，用来接收两个最小权重在数组中的下标

int cmp(void* e1, void* e2)//配合qsort()函数的比较函数
{
    if(*(int*)e1 - *(int*)e2 > 0)return 1;
    else if(*(int*)e1 - *(int*)e2 < 0)return -1;
    else return 0;

}

int Select(HuffmanTree* HT, int n)//找出权重最小的二个根结点在ＨＴ数组中的位置
{
    int i = 0;
    int p = 0;//用于控制数组arr，按顺序存储数据
    int arr[MAX_SIZE] = {0};//用于存储根结点的权重值，以便排序
    int count = 0;//用来记录arr数组中，有几个值需要排序
    for(i = 1; i <= n; i++)
    {
        if((*HT)[i].parent == 0&&(*HT)[i].weight != 0)//必须是有权重值的根结点，才会被加入到arr数组当中
        {
            arr[++p-1] = (*HT)[i].weight;
            count++;//arr有效元素个数+１，arr数组中初始化的0，不算有效元素
        }
    }
    qsort(arr, count, sizeof(int), cmp);//对arr数组中的权重值排序，而且只对有效元素排序，
    for(i = 1; i <= n; i++)
    {
        if((*HT)[i].weight == arr[0])//arr[0]是最小元素
        {
            j = i;
            break;
        }
    }
    for(i = 1; i <= n; i++)
    {
        if((*HT)[i].weight == arr[1] && i != j)//arr[1]是第二小的元素，且要保证arr[0]=arr[1]时,选取的两个下标不相同
        {
            k = i;
            break;
        }
    }
    return 0;
}
void CreatHuffmanTree(HuffmanTree* HT, int n, int*arr)
{
    int i = 0;
    int m = 0;
    if(n <= 1)return;
    m = 2*n - 1;
    *HT = malloc(sizeof(HTNode)*(m+1));//有n个叶子，树就有2n-1个结点，0号位置不用，所以需要2n个结点大小
    for(i = 1; i <= m; i++)//将2n-1个元素初始化，lch,rch,parent设置为0
    {
        (*HT)[i].lch = 0;
        (*HT)[i].rch = 0;
        (*HT)[i].parent = 0;
        (*HT)[i].weight = 0;
    }
    for(i = 1; i <= n; i++)//设置叶子结点weight值（权重）
    {

        (*HT)[i].weight = arr[i-1];
    }
    //开始创建哈夫曼树
    for(i = 1; i < n; i++)//初始有n个根结点，就要新产生n-1个结点，循环一次产生一个
    {
        Select(HT, m+1);//得到权重最小的两个根在数组中的下标j,k
        (*HT)[n+i].lch = j;//ＨＴ数组中有n个根结点，那么新生成的根结点下标从n+1开始
        (*HT)[n+i].rch = k;//设置新根结点的孩子值
        (*HT)[n+i].weight = (*HT)[j].weight + (*HT)[k].weight;//设置新根结点的权重值为两孩子权重值之和
        (*HT)[j].parent = n+i;//新根结点的下标值为最小权值的两个结点的双亲
        (*HT)[k].parent = n+i;
    }
}

void GetHC(HuffmanTree HT, int n, char** HC[])//获取每个叶子节点的哈夫曼编码
{
    char* TempArr = (char*)malloc(n);//创建一个临时数组，来存放一个叶子节点的哈夫曼编码
    TempArr[n-1] = '\0';//把临时数组最后一位设置为'\0'
    *HC = malloc(sizeof(char*)*n);//给传进来的二维数组申请空间，并把这个空间的地址赋给ＨＣ
    int i = 0;
    for(i = 1; i <= n; i++)//从１到５循环，为了方便下标0不用，也为了对应上面的哈夫曼树
    {
        int m = 1;//m是用来记录临时数组中，放进了几个字符．后面就知道用多大的空间来接收了．还可以控制临时数组存放第一个字符的起始位置
        int a = i;//a用来控制当前循环的结点
        while(HT[a].parent)//如果该结点有双亲就执行
        {
            if(HT[HT[a].parent].lch == a)//如果该结点是其双亲的左孩子
                TempArr[n-1-m++] = '0';//记录字符0
            if(HT[HT[a].parent].rch == a)//如果该结点是其双亲的右孩子
                TempArr[n-1-m++] = '1';//记录字符１
            a = HT[a].parent;//再定位在该结点的双亲，用于下次循环
        }
        (*HC)[i] = malloc(m);//根据m的值，可以知道临时数组中有几个字符，然后准确的申请相应的空间
        strcpy((*HC)[i], &TempArr[n-m]);//MAX_SIZE-m,为该数组第一个字符的位置，把临时数组中的字符串，复制到目标数组
    }
    free(TempArr);//释放临时空间
}
int main()
{
    HuffmanTree HT;
    char** HC;//创建一个指针数组
    int arr1[5] = {3,4,5,6,7};
    char arr2[5] = {'a','b','o','u','t'};
    char* arr3 = "aoutbabtoutbaotubatobatu";
    int len_arr3 = strlen(arr3);
    int nums = sizeof(arr1)/sizeof(arr1[0]);//字符集个数
    CreatHuffmanTree(&HT, nums, arr1);//根据权值创建哈夫曼树
    GetHC(HT, nums, &HC);//Get Huffman Code 获取哈夫曼编码
    int i = 1;
    for(i = 1; i<=nums; i++)
    {
        printf("%c的哈夫曼编码为%s\n",arr2[i-1],HC[i]);
    }
     printf("aoutbabtoutbaotubatobatu字符串的编码为:\n");
    for(i = 0; i < len_arr3; i++)
    {
        if(arr3[i] == 'a')printf("%s",HC[1]);
        else if(arr3[i] == 'b')printf("%s",HC[2]);
        else if(arr3[i] == 'o')printf("%s",HC[3]);
        else if(arr3[i] == 'u')printf("%s",HC[4]);
        else if(arr3[i] == 't')printf("%s",HC[5]);
        else return;
    }
    return 0;
}

２,哈夫曼编码翻译成字符串

  （１）首先以字符集对应的字符权重，创建哈夫曼树

（２）从根结点开始，对应着编码，如果编码是0，则指向根结点的左孩子，如果编码是１，则指向根结点的右孩子，然后把左孩子或右孩子当成根结点，根据提供的哈夫曼编码继续向下推，直到找到的结点没有左右孩子，为叶子的时候，就可以得到该结点的权值和字符．

注意：哈夫曼树对应的数组ＨＴ中，叶子结点是在数组最前面下标１开始，依次排列．根结点在数组的最后也就是下标为２n（n个叶子结点，下标从１开始）

例：以上面例子，继续

已知｛a,b,o,u,t}对应的出现频率为{3,4,5,6,7}

        那么110000110111000110111110001001111110对应的字符串是什么？文章来源地址https://www.toymoban.com/news/detail-444267.html

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 5
typedef struct{
    int weight;//权重
    int parent,lch,rch;//双亲，左孩子，右孩子
}HTNode,*HuffmanTree;

int j = 0;
int k = 0;//设置两个全局变量j,k，用来接收两个最小权重在数组中的下标

int cmp(void* e1, void* e2)//配合qsort()函数的比较函数
{
    if(*(int*)e1 - *(int*)e2 > 0)return 1;
    else if(*(int*)e1 - *(int*)e2 < 0)return -1;
    else return 0;

}

int Select(HuffmanTree* HT, int n)//找出权重最小的二个根结点在ＨＴ数组中的位置
{
    int i = 0;
    int p = 0;//用于控制数组arr，按顺序存储数据
    int arr[MAX_SIZE] = {0};//用于存储根结点的权重值，以便排序
    int count = 0;//用来记录arr数组中，有几个值需要排序
    for(i = 1; i <= n; i++)
    {
        if((*HT)[i].parent == 0&&(*HT)[i].weight != 0)//必须是有权重值的根结点，才会被加入到arr数组当中
        {
            arr[++p-1] = (*HT)[i].weight;
            count++;//arr有效元素个数+１，arr数组中初始化的0，不算有效元素
        }
    }
    qsort(arr, count, sizeof(int), cmp);//对arr数组中的权重值排序，而且只对有效元素排序，
    for(i = 1; i <= n; i++)
    {
        if((*HT)[i].weight == arr[0])//arr[0]是最小元素
        {
            j = i;
            break;
        }
    }
    for(i = 1; i <= n; i++)
    {
        if((*HT)[i].weight == arr[1] && i != j)//arr[1]是第二小的元素，且要保证arr[0]=arr[1]时,选取的两个下标不相同
        {
            k = i;
            break;
        }
    }
    return 0;
}
void CreatHuffmanTree(HuffmanTree* HT, int n, int*arr)
{
    int i = 0;
    int m = 0;
    if(n <= 1)return;
    m = 2*n - 1;
    *HT = malloc(sizeof(HTNode)*(m+1));//有n个叶子，树就有2n-1个结点，0号位置不用，所以需要2n个结点大小
    for(i = 1; i <= m; i++)//将2n-1个元素初始化，lch,rch,parent设置为0
    {
        (*HT)[i].lch = 0;
        (*HT)[i].rch = 0;
        (*HT)[i].parent = 0;
        (*HT)[i].weight = 0;
    }
    for(i = 1; i <= n; i++)//设置叶子结点weight值（权重）
    {

        (*HT)[i].weight = arr[i-1];
    }
    //开始创建哈夫曼树
    for(i = 1; i < n; i++)//初始有n个根结点，就要新产生n-1个结点，循环一次产生一个
    {
        Select(HT, m+1);//得到权重最小的两个根在数组中的下标j,k
        (*HT)[n+i].lch = j;//ＨＴ数组中有n个根结点，那么新生成的根结点下标从n+1开始
        (*HT)[n+i].rch = k;//设置新根结点的孩子值
        (*HT)[n+i].weight = (*HT)[j].weight + (*HT)[k].weight;//设置新根结点的权重值为两孩子权重值之和
        (*HT)[j].parent = n+i;//新根结点的下标值为最小权值的两个结点的双亲
        (*HT)[k].parent = n+i;
    }
}

void GetHC(HuffmanTree HT, int n, char** HC[])//获取每个叶子节点的哈夫曼编码
{
    char* TempArr = (char*)malloc(n);//创建一个临时数组，来存放一个叶子节点的哈夫曼编码
    TempArr[n-1] = '\0';//把临时数组最后一位设置为'\0'
    *HC = malloc(sizeof(char*)*n);//给传进来的二维数组申请空间，并把这个空间的地址赋给ＨＣ
    int i = 0;
    for(i = 1; i <= n; i++)//从１到５循环，为了方便下标0不用，也为了对应上面的哈夫曼树
    {
        int m = 1;//m是用来记录临时数组中，放进了几个字符．后面就知道用多大的空间来接收了．还可以控制临时数组存放第一个字符的起始位置
        int a = i;//a用来控制当前循环的结点
        while(HT[a].parent)//如果该结点有双亲就执行
        {
            if(HT[HT[a].parent].lch == a)//如果该结点是其双亲的左孩子
                TempArr[n-1-m++] = '0';//记录字符0
            if(HT[HT[a].parent].rch == a)//如果该结点是其双亲的右孩子
                TempArr[n-1-m++] = '1';//记录字符１
            a = HT[a].parent;//再定位在该结点的双亲，用于下次循环
        }
        (*HC)[i] = malloc(m);//根据m的值，可以知道临时数组中有几个字符，然后准确的申请相应的空间
        strcpy((*HC)[i], &TempArr[n-m]);//MAX_SIZE-m,为该数组第一个字符的位置，把临时数组中的字符串，复制到目标数组
    }
    free(TempArr);//释放临时空间
}

void GetStr(HuffmanTree HT, int nums, char* arr2, char* arr3)
{
    int i = 0;
    int n = 2*nums-1;//nums个叶子，就有2*nums-1个结点，根结点在ＨＴ数组中的下标为2*nums-1
    int len = strlen(arr3);
    for(i=0; i < len; i++)//循环依次读入整个arr3字符串
    {
        if(arr3[i] == '1')n = HT[n].rch;//读入的数据为１时，指向该结点的右孩子
        else if(arr3[i] == '0')n = HT[n].lch;//读入的数据为１时，指向该结点的左孩子
        else return;
        switch(n)//判断此时，有没有到达叶子结点，当n=1,2,3,4,5时就到达了叶子结点，输出对应的值
        {
            case 1:
                {
                    n = 2*nums -1;
                    printf("%c", arr2[0]);
                    break;
                }
            case 2:
                {
                    n = 2*nums -1;
                    printf("%c", arr2[1]);
                    break;
                }
            case 3:
            {
                n = 2*nums -1;
                printf("%c", arr2[2]);
                break;
            }
            case 4:
            {
                n = 2*nums -1;
                printf("%c", arr2[3]);
                break;
            }
            case 5:
            {
                n = 2*nums -1;
                printf("%c", arr2[4]);
                break;
            }
        }

    }

}
int main()
{
    HuffmanTree HT;
    char** HC;//创建一个指针数组
    int arr1[5] = {3,4,5,6,7};
    char arr2[5] = {'a','b','o','u','t'};
    char* arr3 = "110000110111000110111110001001111110";
    int nums = sizeof(arr1)/sizeof(arr1[0]);//字符集个数
    CreatHuffmanTree(&HT, nums, arr1);//根据权值创建哈夫曼树
    GetHC(HT, nums, &HC);//Get Huffman Code 获取哈夫曼编码
    GetStr(HT, nums, arr2, arr3);//把哈夫曼编码翻译成字符串

    return 0;
}

到了这里，关于哈夫曼树详解及其应用(哈夫曼编码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 哈夫曼树、哈夫曼编码/解码

    哈夫曼树、哈夫曼编码/解码

    哈夫曼树的基本介绍 哈夫曼树构建步骤图解 创建哈夫曼树代码实现 基本介绍 哈夫曼编码原理剖析 哈夫曼编码的实例 思路分析 代码实现 使用哈夫曼编码压缩文件的注意事项（代码胜省略）

    2024年02月08日
    浏览(41)
  • 15哈夫曼树/哈夫曼编码

    15哈夫曼树/哈夫曼编码

    哈夫曼树又称为 最优树 ，作用是找到一种效率最高的判断树。 路径 ：从树中一个结点到另一个结点之间的 分支 构成这两个结点之间的路径。 结点的路径长度 ：两结点间路径上的分支树 如图 a ：从 A - D 的路径长度就是是 2。从 A 到 B C D E F G F I 的路径长度分别为 1 1 2 2 3

    2024年02月05日
    浏览(44)
  • 哈夫曼树与哈夫曼编码

    哈夫曼树与哈夫曼编码

    哈夫曼树：结点中赋予一个某种意义的值，称为结点的权值，从根结点开始，到目标结点经过的边数，称为路径长度，路径长度乘以权值，称为带权路径长度； 例如：根结点代表着快递集散点，一个叶子结点权值是5，在业务逻辑中代表着重量是5斤的货物📦，路径长度是3，

    2024年02月05日
    浏览(49)
  • 哈夫曼树、哈夫曼编码和字典树

    哈夫曼树、哈夫曼编码和字典树

    目录 哈夫曼树 树的带权路径长度(wpl) 哈夫曼编码 代码实现哈夫曼树 封装哈夫曼树的节点 构建哈夫曼树 字典树 执行流程 代码实现字典树 封装字典树的节点 构建字典树         哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树。哈夫曼树常常用于数据压缩，其压

    2023年04月09日
    浏览(51)
  • 数据结构——哈夫曼树与哈夫曼编码

    数据结构——哈夫曼树与哈夫曼编码

    1.1 基本概念 路径 ：指从根结点到该结点的分支序列。 路径长度 ：指根结点到该结点所经过的分支数目。 结点的带权路径长度 ：从树根到某一结点的路径长度与该结点的权的乘积。 树的带权路径长度(WPL) ：树中从根到所有叶子结点的各个带权路径长度之和。 哈夫曼树 是由

    2024年02月05日
    浏览(46)
  • 数据结构之哈夫曼树和哈夫曼编码

    数据结构之哈夫曼树和哈夫曼编码

    切入正题之前，我们先了解几个概念： 路径：从树的一个结点到另一个结点分支所构成的路线 路径长度：路径上的分支数目 树的路径长度：从根结点出发到每个结点的路径长度之和 带权路径长度：该结点到根结点的路径长度乘以该结点的权值 树的带权路径长度：树中所有

    2024年02月11日
    浏览(46)
  • 数据结构之哈夫曼树与哈夫曼编码

    数据结构之哈夫曼树与哈夫曼编码

    编码是信息处理的基础（重新表示信息）。 普通的编码是等长编码，例如7位的ASCIL编码，对出现频率不同的字符都使用相同的编码长度。 但其在传输和存储等情况下编码效率不高 。 可使用不等长编码，来压缩编码：高频字符编码长度更短，低频字符编码长度更长。   [例

    2023年04月15日
    浏览(64)
  • 哈夫曼树及哈夫曼编码(考试常考版)

    哈夫曼树及哈夫曼编码(考试常考版)

    哈夫曼树的基本概念 哈夫曼树的定义是对一组具有确定权值的叶子节点，选出最小带权路径长度的二叉树为哈夫曼树(WPL最小)，也称最优二叉树 哈夫曼算法的实现 注意：哈夫曼树在构造时选择两个最小的权值点，默认小的在左边大的在右边，但实际上并没有硬性规定，可以

    2024年02月11日
    浏览(58)

  • 数据结构课程实验五：哈夫曼树与哈夫曼编码

    实验日期：2022-12-20   目录 一、实验目的 1、掌握哈夫曼树的建立 2、掌握哈夫曼编码方式 二、实验内容

    2024年02月05日
    浏览(50)
  • 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    超详细讲解哈夫曼树(Huffman Tree)以及哈夫曼编码的构造原理、方法，并用代码实现。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 :两结点间路径上的 分支数 。 树的路径长度： 从树根到每一个结点的路径长度之和。记作: TL  权

    2024年02月06日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包