C++实现哈夫曼树算法

如何建立哈夫曼树的,网上搜索一堆,这里就不写了,直接给代码。

1.哈夫曼树结点类:HuffmanNode.h

#ifndef HuffmanNode_h
#define HuffmanNode_h

template <class T>
struct HuffmanNode {
 T weight; // 存储权值
 HuffmanNode<T> *leftChild, *rightChild, *parent; // 左、右孩子和父结点
};

#endif /* HuffmanNode_h */

2.哈夫曼树最小堆:HuffmanMinHeap.h

#ifndef HuffmanMinHeap_h
#define HuffmanMinHeap_h

#include "HuffmanNode.h"
#include <iostream>
using namespace std;

const int DefaultSize = 100;

template <class T>
class MinHeap {
public:
 MinHeap(); // 构造函数
 ~MinHeap(); // 析构函数
 void Insert(HuffmanNode<T> *current); // 插入
 HuffmanNode<T> *getMin(); // 获取最小结点
private:
 HuffmanNode<T> *heap; // 动态数组存储最小堆
 int CurrentSize; // 目前最小堆的结点数
 void ShiftUp(int start); // 向上调整
 void ShiftDown(int start, int m); // 下滑
};

// 构造函数
template <class T>
MinHeap<T>::MinHeap() {
 heap = new HuffmanNode<T>[DefaultSize]; // 创建堆空间
 CurrentSize = 0;
}

// 析构函数
template <class T>
MinHeap<T>::~MinHeap() {
 delete []heap; // 释放空间
}

// 插入
template <class T>
void MinHeap<T>::Insert(HuffmanNode<T> *current) {
 if(CurrentSize == DefaultSize) {
  cout << "堆已满" << endl;
  return;
 }
 // 把current的数据复制到“数组末尾”
 heap[CurrentSize] = *current;
 // 向上调整堆
 ShiftUp(CurrentSize);
 CurrentSize++;
}

// 获取最小结点并在堆中删除该结点
template <class T>
HuffmanNode<T> *MinHeap<T>::getMin() {
 if(CurrentSize == 0) {
  cout << "堆已空!" << endl;
  return NULL;
 }
 HuffmanNode<T> *newNode = new HuffmanNode<T>();
 if(newNode == NULL) {
  cerr << "存储空间分配失败!" << endl;
  exit(1);
 }
 *newNode = heap[0]; // 将最小结点的数据复制给newNode
 heap[0] = heap[CurrentSize-1]; // 用最后一个元素填补
 CurrentSize--;
 ShiftDown(0, CurrentSize-1); // 从0位置开始向下调整
 return newNode;
}

// 向上调整
template <class T>
void MinHeap<T>::ShiftUp(int start) {
 // 从start开始,直到0或者当前值大于双亲结点的值时,调整堆
 int j = start, i = (j-1)/2; // i是j的双亲

 HuffmanNode<T> temp = heap[j];
 while(j > 0) {
  if(heap[i].weight <= temp.weight)
   break;
  else {
   heap[j] = heap[i];
   j = i;
   i = (j - 1) / 2;
  }
 }
 heap[j] = temp;
}

// 向下调整
template <class T>
void MinHeap<T>::ShiftDown(int start, int m) {
 int i = start, j = 2 * i + 1; // j是i的左子女

 HuffmanNode<T> temp = heap[i];
 while(j <= m) {
  if(j < m && heap[j].weight > heap[j+1].weight)
   j++; // 选两个子女中较小者
  if(temp.weight <= heap[j].weight)
   break;
  else {
   heap[i] = heap[j];
   i = j;
   j = 2 * j + 1;
  }
 }
 heap[i] = temp;
}

#endif /* HuffmanMinHeap_h */

3.哈夫曼树实现:HuffmanTree.h

#ifndef HuffmanTree_h
#define HuffmanTree_h

#include "HuffmanMinHeap.h"
#include "HuffmanNode.h"

template <class T>
class HuffmanTree {
public:
 HuffmanTree(); // 构造函数
 ~HuffmanTree(); // 析构函数
 void Create(T w[], int n); // 创建哈夫曼树
 void Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent); // 合并
 void PreOrder(); // 前序遍历Huffman树
private:
 HuffmanNode<T> *root; // 根结点
 void Destroy(HuffmanNode<T> *current); // 销毁哈夫曼树
 void PreOrder(HuffmanNode<T> *current); // 前序遍历Huffman树
};

// 构造函数
template <class T>
HuffmanTree<T>::HuffmanTree() {
 root = NULL;
}

// 析构函数
template <class T>
HuffmanTree<T>::~HuffmanTree() {
 Destroy(root); // 销毁哈夫曼树
}

// 销毁哈夫曼树
template <class T>
void HuffmanTree<T>::Destroy(HuffmanNode<T> *current) {
 if(current != NULL) { // 不为空
  Destroy(current->leftChild); // 递归销毁左子树
  Destroy(current->rightChild); // 递归销毁右子树
  delete current; // 释放空间
  current = NULL;
 }
}

// 创建哈夫曼树
template <class T>
void HuffmanTree<T>::Create(T w[], int n) {
 int i;
 MinHeap<T> hp; // 使用最小堆存放森林
 HuffmanNode<T> *first, *second, *parent = NULL;
 HuffmanNode<T>*work = new HuffmanNode<T>();

 if(work == NULL) {
  cerr << "存储空间分配失败!" << endl;
  exit(1);
 }
 for(i = 0; i < n; i++) {
  work->weight = w[i];
  work->leftChild = work->rightChild = work->parent = NULL;
  hp.Insert(work); // 插入到最小堆中
 }
 for(i=0; i < n-1; i++) { // 做n-1趟,形成Huffman树
  first = hp.getMin(); // 获取权值最小的树
  second = hp.getMin(); // 获取权值次小的树
  parent = new HuffmanNode<T>();
  if(parent == NULL) {
   cerr << "存储空间分配失败!" << endl;
   exit(1);
  }
  Merge(first, second, parent); // 合并
  hp.Insert(parent); // 重新插入到最小堆中
 }
 root = parent; // 根结点
}
// 合并
template <class T>
void HuffmanTree<T>::Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent) {
 parent->leftChild = first; // 左子树
 parent->rightChild = second; // 右子树
 parent->weight = first->weight + second->weight; // 父结点权值
 first->parent = second->parent = parent; // 父指针
}

// 前序遍历Huffman树
template <class T>
void HuffmanTree<T>::PreOrder() {
 PreOrder(root);
}

// 前序遍历Huffman树
template <class T>
void HuffmanTree<T>::PreOrder(HuffmanNode<T> *current) {
 if(current != NULL) {
  cout << current->weight << " "; // 访问当前结点数据
  PreOrder(current->leftChild); // 递归遍历左子树
  PreOrder(current->rightChild); // 递归遍历右子树
 }
}
#endif /* HuffmanTree_h */

4.测试:main.cpp

#include "HuffmanTree.h"

int main(int argc, const char * argv[]) {
 int arr[] = {7, 5, 2, 4};
 int len = sizeof(arr) / sizeof(arr[0]); // 数组长度
 HuffmanTree<int> tree; // Huffman树的对象

 tree.Create(arr, len); // 创建Huffman树
 tree.PreOrder(); // 前序遍历Huffman树
 return 0;
}

测试结果:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C++数据结构之文件压缩(哈夫曼树)实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • C++实现哈夫曼树简单创建与遍历的方法

    本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法. 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小. 据此构造出最优树算法如下: 哈夫曼算法: 1. 将n个权值分别为w1,w2,w3,....wn-1,wn的节点按权值递增排序,将每个权值作为一棵二叉树.构成n棵二叉树森林F={T1,T2,T3,T4,...Tn},其中每个二叉树都只有一个权值,其左右字数为空 2. 在森林F中选取根节点权值最小二叉树,

  • C++ 哈夫曼树对文件压缩、加密实现代码

    在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼.哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割.比如用lzw编码abc,就是1,2,3.但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性.而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110

  • C++数据结构与算法之哈夫曼树的实现方法

    本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法.分享给大家供大家参考,具体如下: 哈夫曼树又称最优二叉树,是一类带权路径长度最短的树. 对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的结点越远离树的根结点. 前面一篇图文详解JAVA实现哈夫曼树对哈夫曼树的原理与java实现方法做了较为详尽的描述,这里再来看看C++实现方法. 具体代码如下: #include <iostream> using namespace std; #if !defined(_HUFFMANTREE_H

  • 解析C++哈夫曼树编码和译码的实现

    一.背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 二.实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子:假如由n个字符来构造一棵哈夫曼树,则共有结点2n-1个:在构造前,先初始化

  • C++实现哈夫曼树算法

    如何建立哈夫曼树的,网上搜索一堆,这里就不写了,直接给代码. 1.哈夫曼树结点类:HuffmanNode.h #ifndef HuffmanNode_h #define HuffmanNode_h template <class T> struct HuffmanNode { T weight; // 存储权值 HuffmanNode<T> *leftChild, *rightChild, *parent; // 左.右孩子和父结点 }; #endif /* HuffmanNode

  • java实现哈夫曼压缩与解压缩的方法

    一哈夫曼树以及文件压缩原理: 1.哈夫曼树 : 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树.哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近(频率越高的结点离根越进). 以 下数组为例,构建哈夫曼树 int a[] = {0,1,2,3,4,5,6,7,8} 我们可以发现以下规律 1:9个数构成的哈夫曼树一共有17个结点,也就是可以n个数可以生产2*n-1个结点 2:数字越大的数离根节点越近,越小的数离根节点越近.

  • C++深入讲解哈夫曼树

    目录 哈夫曼树的基本概念 1)路径 2)路径长度 3)权 4)结点的带权路径长度 5)树的带权路径长度 6)哈夫曼树 哈夫曼树的构造算法 哈夫曼树的构造过程 哈夫曼树算法的实现 1)结点的存储结构 2)构建哈夫曼树 哈夫曼树的基本概念 Q:什么是哈夫曼树 A:哈夫曼树又称最优树,是一类带权路径长度最短的树.在正式了解哈夫曼树之前,我们需要了解一些概念. 1)路径 Q:什么是路径 A:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径. 2)路径长度 Q:什么是路径长度 A:路径上的分支

  • 漫谈C++哈夫曼树的原理及实现

    目录 1. 前言 2. 设计思路 3. 构建思路 4. 编码实现 4.1 使用优先队列 4.2 使用一维数组 5. 总结 1. 前言 什么是哈夫曼树? 把权值不同的n个结点构造成一棵二叉树,如果此树满足以下几个条件: 此 n 个结点为二叉树的叶结点 . 权值较大的结点离根结点较近,权值较小的结点离根结点较远. 该树的带权路径长度是所有可能构建的二叉树中最小的. 则称符合上述条件的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree). 构建哈夫曼树的目的是什么? 用来解决在通信系统中如何

  • 如何用Java实现啥夫曼编码

    大家可能会想,程序和第三方提供了很多压缩方式,何必自己写压缩代码呢?不错,如GZIP这样的压缩工具很多,可是在某些情况下(如文本内容小且字符不重复),GZIP压缩后会比原始文本还要大.所以在某些特殊情况下用自己的压缩方式可以更优. 大家可能早已忘记了在学校学习的哈夫曼知识,可以先在百度百科了解一下哈夫曼知识:http://baike.baidu.com/view/127820.htm 哈夫曼思想:统计文本字符重复率,求出各字符权值,再构造出一颗最优二叉树(又称哈夫曼树),然后给每个叶子结点生成一

  • java实现哈夫曼压缩的实例

    哈夫曼压缩的原理: 通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码. 其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短; 出现频率越低的字节其路径长度越长.从而达到压缩的目的. 如何构造哈夫曼树? 一.  定义字节类  我的字节类定义了一下属性 public int data;//节点数据 public int weight;//该节点的权值 public int point;//该节点所在的左右位置 0-左 1-右 privat

  • 使用C语言详解霍夫曼树数据结构

    1.基本概念 a.路径和路径长度 若在一棵树中存在着一个结点序列 k1,k2,--,kj, 使得 ki是ki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径. 从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1. b.结点的权和带权路径长度 在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权) 结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘

  • 哈夫曼的c语言实现代码

    我们设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息.根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有 2n-1 个结点,所以数组 HuffNode 的大小设置为 2n-1 .HuffNode 结构中有 weight, lchild, rchild 和 parent 域.其中,weight 域保存结点的权值, lchild 和 rchild 分别保存该结点的左.右孩子的结点在数组 HuffNode 中的序号,从而建立起结点之间的关系.为了判定一个结点是否已加入到要建立的哈夫曼树

随机推荐