`

Huffman树

阅读更多
Huffman树,又称最优二叉树,是一类加权路径长度最短的二叉树

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

路径长度:路径上分支条数
#ifndef HUFFMAN_H
#define HUFFMAN_H

#include"MinHeap.h"

class HuffmanNode{
public:
    float data;
    HuffmanNode *leftChild,*rightChild,*parent;
    HuffmanNode():leftChild(NULL),rightChild(NULL),parent(NULL){}
    HuffmanNode(float elem,HuffmanNode* left=NULL,
                HuffmanNode* right=NULL,HuffmanNode* pr=NULL)
        :data(elem),leftChild(left),rightChild(right),parent(pr){}
    bool operator<=(HuffmanNode& R){
        return data<=R.data;
    }
    bool operator>(HuffmanNode& R){
        return data>R.data;
    }
};

class HuffmanTree{
public:
    HuffmanTree(float w[],int n);
    ~HuffmanTree(){
        delete root;
    }
protected:
    HuffmanNode* root;
    void deleteTree(HuffmanNode* t);
    void mergeTree(HuffmanNode& ht1,HuffmanNode& ht2,HuffmanNode*& parent);
};

HuffmanTree::HuffmanTree(float w[], int n)
{
    MinHeap<HuffmanNode> hp;
    HuffmanNode* parent,first,second,work;
    for(int i=0;i<n;++i){
        work.data=w[i];
        work.leftChild=NULL;
        work.rightChild=NULL;
        work.parent=NULL;
        hp.Insert(work);
    }
    for(int i=0;i<n-1;++i){
        hp.RemoveMin(first);
        hp.RemoveMin(second);
        mergeTree(first,second,parent);
        hp.Insert(*parent);
    }
    root = parent;
}

void HuffmanTree::mergeTree(HuffmanNode &bt1, HuffmanNode &bt2, HuffmanNode *&parent)
{
    parent = new HuffmanNode;
    parent->leftChild = &bt1;
    parent->rightChild = &bt2;
    parent->data = bt1.data+bt2.data;
    bt1.parent = bt2.parent = parent;
}

#endif // HUFFMAN_H

分享到:
评论

相关推荐

    C语言实现Huffman树,Huffman编码

    构建Huffman树的基本思想是:将频率最低的两个节点合并成一个新的节点,新节点的频率是这两个子节点的频率之和,然后将新节点插入到当前的节点集合中,重复此过程直到只剩下一个节点,即为Huffman树。 在C语言中...

    Huffman树 及 Huffman编码 演示程序

    Huffman树,也被称为哈夫曼树或霍夫曼树,是一种特殊的二叉树,用于在数据压缩领域实现高效的编码方法——Huffman编码。这种编码技术是基于频率的,能够为出现频率高的字符分配较短的编码,而为出现频率低的字符分配...

    Huffman 树 编码解码

    Huffman编码是一种高效的数据压缩方法,它基于字符出现频率构建一棵特殊的二叉树——Huffman树,以此来为每个字符分配唯一的二进制编码。在信息传输或存储时,使用这种编码可以显著减少数据量,因为频繁出现的字符...

    【实验三】Huffman树及Huffman编码的算法实现1

    Huffman树,又称最优二叉树,是一种带权路径长度最短的二叉树,由美国麻省理工学院的David A. Huffman在1952年提出,主要用于数据压缩。Huffman编码是一种可变长度的前缀编码,它是建立在Huffman树基础上的一种编码...

    Huffman树图形界面小程序

    《Huffman树图形界面小程序详解》 在计算机科学领域,数据结构的学习至关重要,而压缩算法则是其中的一个重要分支。Huffman编码,又称霍夫曼编码,是一种无损数据压缩算法,利用了字符出现频率的不同来构造一棵特殊...

    数据结构有关数和二叉树,树的遍历以及线索化,Huffman树及其应用课件

    ### 数据结构有关数和二叉树,树的遍历以及线索化,Huffman树及其应用 #### 一、树的基本概念 **树的定义与基本术语:** 树是一种非线性的数据结构,由一系列节点组成,这些节点之间通过边相连形成层次结构。一个...

    huffman树的构建

    哈夫曼树(Huffman Tree),也称为最优二叉树,是数据压缩中的一种关键数据结构,由哈夫曼在1952年提出。它是一种带权路径长度最短的二叉树,用于实现哈夫曼编码,这是一种高效的无损数据压缩方法。在哈夫曼编码中,...

    Huffman树的创建和Huffman编码的生成

    C语言实现的Huffman树和Huffman编码生成的程序

    HUFFMAN树的C++实现

    用C++语言实现huffman树的源代码

    Huffman树及Huffman编码的算法实现.zip

    本实验报告中,"【实验三】Huffman树及Huffman编码的算法实现"可能包含了详细的代码实现,展示了如何使用编程语言(如C++、Java或Python)来实现上述步骤。实验可能会包括测试不同频率分布的字符集,以及对比不同...

    huffman树的编码与解码

    程序用于实现建立huffman树,以及实现其编码和解码的功能

    Huffman树的生成

    Huffman树的生成和解码,二叉树形式

    Huffman树的表示及Huffman编码

    《Huffman树的表示及Huffman编码》 在数据压缩领域,Huffman编码是一种非常重要的无损数据压缩方法,由美国计算机科学家David A. Huffman在1952年提出。其核心思想是通过构建一棵特殊的二叉树——Huffman树(也称为...

    Huffman树编码问题

    关于Huffman树的编码问题,适合基础薄弱的学生转载

    实验报告七:Huffman树与Huffman树编码算法实验.pdf

    实验报告七:Huffman树与Huffman编码算法 Huffman编码是一种高效的无损数据压缩算法,由美国计算机科学家David A. Huffman在1952年提出。它利用字符出现频率来构建一棵特殊的二叉树——Huffman树,进而为每个字符...

    实验报告七:Huffman树与Huffman树编码算法实验.docx

    **实验报告:Huffman树与Huffman编码算法** 在信息技术领域,数据压缩是至关重要的,尤其是在互联网通信中,为了高效地传输大量数据,压缩技术必不可少。Huffman编码是一种基于频率的无损数据压缩方法,由David A. ...

    利用huffman树实现对文件的无损压缩与解压

    利用Huffman树实现对文件的无损压缩与解压,并且对Huffman树的创建也做了详细的说明与讲解,C语言实现的.....值得一看....

    Huffman树实验报告1

    【Huffman树与Huffman编码】实验报告详细解析 实验标题:Huffman树与Huffman编码的算法实现 实验目标: 1. 理解Huffman树的构造原理及其编码应用。 2. 掌握Huffman树在数据压缩和通信中的实际操作过程。 实验要求...

Global site tag (gtag.js) - Google Analytics