`

最小堆应用---用最小堆实现huffman树

 
阅读更多
最小堆应用---用最小堆实现huffman树,huffman是形成huffman编码的基础.
#include"MinHeap.h"

template<class T> class HuffmanTree;
template<class T> 
class TreeNode{
 friend class HuffmanTree<T>;
 private:
  T data;
  TreeNode<T> *left,*right;
 public:
  TreeNode(T value){
   data = value;
   left = right = NULL;
  }
  TreeNode(){
   left = right = NULL;
  }
  bool operator > (const TreeNode &node){
    return data > node.data;
  }
  bool operator < (const TreeNode &node){
    return data < node.data;
  }
  bool operator == (const TreeNode &node){
    return data == node.data;
  }
     bool operator >= (const TreeNode &node){
    return data >= node.data;
  }
};

template <class T>
class HuffmanTree{
 public:
  HuffmanTree();
  HuffmanTree(T value[],int n);
 protected:
  TreeNode<T> *JoinTree(TreeNode<T> &node1,TreeNode<T> &node2);
  TreeNode<T> *root;
};

template<class T>
HuffmanTree<T>::HuffmanTree():root(NULL){
}

template<class T>
HuffmanTree<T>::HuffmanTree(T value[],int n):root(NULL){
  TreeNode<T> *nodes = new TreeNode<T>[n];
  TreeNode<T> leftNode,rightNode;
  int i = 0;
  for(i = 0; i < n; i++){
    nodes[i] = TreeNode<T>(value[i]);
  }
  MinHeap< TreeNode<T> > *m_heap = new MinHeap< TreeNode<T> >(nodes,n);
  
  for(i = 0; i < n-1; i++){
   m_heap->RemoveMin(leftNode);
   m_heap->RemoveMin(rightNode);
   root = JoinTree(leftNode,rightNode);
   m_heap->Insert(*root);
  }
}

template<class T>
TreeNode<T> *HuffmanTree<T>::JoinTree(TreeNode<T> &node1,TreeNode<T> &node2){
  TreeNode<T> *r = new TreeNode<T>;
  r->left = &node1;
  r->right = &node2;
  r->data = node1.data + node2.data;
  return r;
}

分享到:
评论

相关推荐

    Huffman-Coding-Using-Java:这是使用 JAVA 中实现的优先队列(使用最小堆)、二叉搜索树和链表等数据结构的霍夫曼编码的实现。 该项目可以对任何类型的文本文件进行无损数据压缩。 应用程序也可以解码取回原始文件

    Huffman-Coding-Using-... 这是使用 JAVA 中实现的优先队列(使用最小堆)、二叉搜索树和链表等数据结构的霍夫曼编码的实现。 该项目可以对任何类型的文本文件进行无损数据压缩。 应用程序还可以解码以取回原始文件。

    Huffman编码(MFC版本)

    1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.熟练掌握二叉树的应用;具体要求如下: 最小冗余码/哈夫曼码

    Huffuman编码

    1、将信源发出的N个消息符号按其概率的递减次序依次排列。 2、取概率最小的两个符号分别配以0和1两个码元,并将这两个符号的概率相加作为一个新概率,与未分配码元的符号重新按...本程序可实现以上过程的Huffuman编码

    Huffman编码(c++版本)_数据结构与算法分析课程设计报告

    具体要求如下:最小冗余码/哈夫曼码、ASCII码/定长码、哈夫曼码/不定长码、统计、构造Huffman树、在左分枝标0,右分枝标1、确定Huffman编码  3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个...

    zcmu OJ 1810: Huffuman树

    Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下: 1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi...

    搜索树 优先队列 应用 源代码

    对BST树的方法进行扩充,实现如下功能: 1)给定一个节点,寻找并...对Huffman树的方法进行扩充,实现如下功能: 1)键盘输入一个字符串或者读入一个文本文件,统计每个字符出现的频率; 2)输出每个字符的Huffman编码

    数据结构与算法分析第二版 ---C语言描述(附加答案)

    树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 表达式树4.3 查找树ADT——二叉查找树4.3.1 MakeEmpty4.3.2 Find4.3.3 FindMin和FindMax4.3.4 Insert4.3.5 Delete4.3.6 平均情形分析...

    简单迷宫程序和树的实现程序

    八方向迷宫的实现 内附详细的程序说说明 还有树的相关程序 哈夫曼树(Huffman树)——设有n个权值{w1,w2,……wn},构造一棵有n个叶子结点的二叉树,每个叶子的权值为wi,则wpl最小的二叉树叫~,也称最优二叉树

    山东大学大二数据结构实验堆及其应用实验报告(含源码)

    最小堆的存储结构使用数组。提供操作:插入、删除、初始化。题目第一个操作是建堆操作,接下来是对堆的插入和删除操作,插入和删除都在建好的堆上操作。 输入一串小写字母组成的字符串(不超过1000000)。输出这个字符...

    哈夫曼编码/译码器 完整版课程数据结构设计

    为了提高存储和处理文本的效率,在一些计算机应用场合,如数据通信,常采用不等长的编码,对常用的字符用较少的码位编码,不常出现的字符用较多的码位编码,从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等...

    哈夫曼树应用STL栈的C++语言构建

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

    数据结构与算法知识点.doc

    堆的初始化、堆的插入、删除算法 5.8 Huffman树;Huffman编码 6. 树的概念,树的周游,森林的周游;树、森林与二叉树之间的转换 7. 图的性质 1. 图的性质、图的存储、图的遍历(DFS,BFS) 2. 最小生成树概念,Prim...

    Huffman编码

    1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.熟练掌握二叉树的应用;具体要求如下: 最小冗余码/哈夫曼码

    Java数据结构和算法中文第二版(2)

    红-黑树的实现 其他平衡树 小结 问题 实验 第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程...

    数据结构算法实现(严蔚敏版配套实现程序)

    范例1-106 最小生成树 355 ∷相关函数:MiniSpanTree_PRIM函数 1.7.6 关节点和重连通分量 359 范例1-107 关节点和重连通分量 359 ∷相关函数:FindArticul函数 1.7.7 拓扑排序 366 范例1-108 拓扑排序 366 ∷相关...

    Java数据结构和算法中文第二版(1)

    红-黑树的实现 其他平衡树 小结 问题 实验 第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程...

    ACM算法竞赛常用代码

    数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,二斜堆,二项堆,二叉查找树,红黑树,AVL平衡树,Treap,Splay,静态二叉查找树,2-d树,...

    数据结构算法实现(严蔚敏版配套实现程序)

    数据结构算法实现(严蔚敏版配套实现程序) 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 范例1-2 一维数组应用 3 1.1.3 一维数组的高级应用 5 ...

    数据结构实践

    最小生成树 Minitree 关节点 FindArtgraph 图的应用 拓扑排序 TSort 关键路径 CritPath Dijkstra算法 DIJ Floyd算法 FLOYD 10 查找 静态查找 顺序查找、折半查找 SSearch 动态查找 二叉排序树 BSTSearch ...

Global site tag (gtag.js) - Google Analytics