HuffMan tree

2023-12-13 13:46:00

定义

????????给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

基础知识

  • 路径:从树中的一个结点到另一个结点之间的分支构成这两点之间的路径
  • 路径长度:路径上的分支数目称作路径长度
  • 树的路径长度:从树根到每一个结点的路径长度之和
  • 权:赋予某个实体的一个量
  • 结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积
  • ?树的带权路径长度:树中所有叶子结点的带权路径长度之和

????????哈夫曼编码跟 ASCII 编码有什么区别?ASCII 编码是对照ASCII 表进行的编码,每一个字符符号都有对应的编码,其编码长度是固定的。而哈夫曼编码对于不同字符的出现频率其使用的编码是不一样的。其会对频率较高的字符使用较短的编码,频率低的字符使用较高的编码。这样保证总体使用的编码长度会更少,从而实现到了数据压缩的目的。

哈夫曼树的构造

假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:

(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);

(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

(3)从森林中删除选取的两棵树,并将新树加入森林;

(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

例如:对 2,3,4,6 这四个数进行构造

huffman存储结构就是采用二叉树存储方式中的一种静态存储(二叉链表的静态结构)

因为每次要找到序列中权值最小的进行合并,所以在创建哈夫曼树时采用优先级队列,每次取出最小值。

列表中由n个数据,构建出来的哈夫曼树就有2*n - 1个节点

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <functional>
#include <ios>
#include<iostream>
#include<vector>
#include<string.h>
#include<stack>
#include<math.h>
#include<cstring>
#include<queue>
using namespace std;

const int n = 8;
const int m = 2 * n;
typedef unsigned int WeightType;
typedef unsigned int NodeType;

typedef struct {
    WeightType weight;
    NodeType parent, leftchild, rightchild;
}HTNode;

typedef HTNode HuffManTree[m];
typedef struct {
    char ch;
    char code[n + 1];
}HuffManCode;
typedef HuffManCode Huffcode[n + 1];

void InitHuffManTree(HuffManTree &hft, WeightType w[]){
    memset(hft, 0, sizeof(HuffManTree));
    for(int i = 0; i < n; ++i){
        hft[i + 1].weight = w[i];
    }
}
void PrintHuffManTree(HuffManTree hft){
    for(int i = 1; i < m; ++i){
        printf("index :%3d weight : %3d parent: %3d leftchild %3d rightchild %3d\n" ,
        i, hft[i].weight, hft[i].parent, hft[i].leftchild, hft[i].rightchild);
    }
    printf("\n");
}
struct IndexWeight{
    int index;
    WeightType weight;
    operator WeightType() const {return  weight;}
};
void CreateHuffManTree(HuffManTree hft){
    std::priority_queue<IndexWeight, vector<IndexWeight>, std::greater<IndexWeight> > qu;
    for(int i = 0; i <=n; ++i){
        qu.push(IndexWeight{i, hft[i].weight});
    }
    int k = n + 1;
    while(!qu.empty()){
        if(qu.empty())  break;
        IndexWeight left = qu.top();qu.pop();
        if(qu.empty())  break;
        IndexWeight right = qu.top(); qu.pop();
        hft[k].weight = left.weight + right.weight;
        hft[k].leftchild = left.index;
        hft[k].rightchild = right.index;
        hft[left.index].parent = k;
        hft[right.index].parent = k;
        qu.push({k, hft[k].weight});
        k += 1;
    }
}
void InitHuffManCode(Huffcode hc, const char * ch){
    memset(hc, 0, sizeof(HuffManCode));
    for(int i =1 ;i <= n; ++i){
        hc[i].ch = ch[i -1];
        hc[i].code[0] = '\0';
    }
}

void PrintHuffCode(Huffcode hc){
    for(int i = 1; i <= n; ++i){
        printf("data : %c ->code %s\n", hc[i].ch, hc[i].code);
    }
    printf("\n");
}
void CreateHuffCode(HuffManTree hft, Huffcode hc){
    char code[n + 1] = {0};
    for(int i = 1; i <= n; ++i){
        int k = n;
        code[k] = '\0';
        int c = i;
        int pa = hft[c].parent;
        while(pa != 0){
            code[--k] = hft[pa].leftchild == c ? '0' : '1';
            c = pa;
            pa = hft[c].parent;
        }
        strncpy(hc[i].code, &code[k],  n);
        
    }
}
int main(){

    WeightType w[n] = {5,29,7,8,14,23,3,11};
    char ch[n + 1] = {'A','B', 'C', 'D', 'E', 'F', 'G', 'H'};
    HuffManTree hft = {0};
    Huffcode hc = { 0};
    InitHuffManTree(hft, w);
    InitHuffManCode(hc, ch);
    PrintHuffManTree(hft);
    PrintHuffCode(hc);
    CreateHuffManTree(hft);
    CreateHuffCode(hft, hc);
    PrintHuffManTree(hft);
    PrintHuffCode(hc);
    
    return 0;
}

参考:

https://blog.csdn.net/Initial_Mind/article/details/124354318

文章来源:https://blog.csdn.net/huaooo1/article/details/134953212
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。