C++实现哈夫曼树的方法

2024-10-03 10:25:44

序言

对于哈夫曼编码，个人的浅薄理解就是在压缩存储空间用很大用处。
用一个很简单例子，存储一篇英文文章时候，可能A出现的概率较大，Z出现的记录较小，如果正常存储，可能A与Z存储使用的空间一样。但是用哈夫曼编码方式，A经常出现，所用编码长度就短。

构造哈夫曼树，生成哈夫曼编码

一、定义节点类型

struct Node {
 char C;
 long key;
 Node *Left, *Right,*parent;
 Node() { Left = Right = NULL; }
};

二、定义树类型（节点数组）

三要素：不定长数组，元素大小，有效元素个数

struct RootA {
 Node *NodeA;
 const int Size;
 int n;
 RootA(int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; }
 ~RootA() { delete[]NodeA; }
};

三、创建哈夫曼树

1.将每一个节点都当成一棵树，初始化数组大小，并进行赋值

RootA RA(4);
 //1.在RA.NodeA中存入字母和权值
 for (RA.n = 0;RA.n < RA.Size;RA.n++) {
 cout << "字母：";
 cin >> RA.NodeA[RA.n].C;
 cout << "权值：";
 cin >> RA.NodeA[RA.n].key;
 }

2.将树按权值大小排序

void Sort(RootA *ra) {
 for (int i = 0;i < ra->n;i++) {
 bool ESC = false;
 for (int j = 0;j < ra->n - i - 1;j++) {
  if (ra->NodeA[j].key > ra->NodeA[j + 1].key) {
  Node T;T = ra->NodeA[j];ra->NodeA[j] = ra->NodeA[j + 1];ra->NodeA[j + 1] = T;
  ESC = true;
  }
 }
 if (!ESC) return;
 }
}

3.(1)遍历数组，将RA.NodeA[0]和RA.Node[1]合并，其余向前移动，重新排序
(2)将RA.NodeA[0]，RA.NodeA[1]分别放在新合并的RA.NodeA[0]的左右子结点中

while (RA.n > 1) {
 //1.将RA.NodeA[0]和RA.NodeA[1]合并，将其余向前移动
 Node *NewNode0 = new Node;
 *NewNode0 = RA.NodeA[0];
 Node *NewNode1 = new Node;
 *NewNode1 = RA.NodeA[1];
 RA.NodeA[0].C = ' ';
 RA.NodeA[0].key = RA.NodeA[0].key + RA.NodeA[1].key;
 RA.NodeA[0].Left = NewNode0;
 NewNode0->parent = &RA.NodeA[0];
 RA.NodeA[0].Right = NewNode1;
 NewNode1->parent = &RA.NodeA[0];
 for (int i = 1;i < RA.n-1;i++) {
  RA.NodeA[i] = RA.NodeA[i + 1];
 }
 RA.n = RA.n - 1;
 //2.排序
 Sort(&RA);
 }

4.输出哈夫曼编码

递归，找到叶子节点，记录路径，左记录0，右记录1，直到输出所有叶子节点

void CrateCode(Node *t,string &s) {
 //1.遍历节点，遍历左节点编码为0,右节点则为1，递归，直到输出所有叶子节
 if (t->Left != NULL && t->Right != NULL) {
 s.push_back('0'); CrateCode(t->Left, s);
 s.pop_back();
 s.push_back('1');CrateCode(t->Right, s);
 s.pop_back();
 }
 else {
 cout << "哈夫曼编码：";
 cout << t->C << ":" << s<<endl;
 }
}

以上是对构造哈夫曼树以及生成哈夫曼编码的总结，希望对你们有所帮助！

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

C++数据结构之文件压缩（哈夫曼树）实例详解

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

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

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

本文实例为大家分享了C++实现哈夫曼树的编码解码,供大家参考,具体内容如下代码: #pragma once #include<iostream> #include<stack> using namespace std; #define m 20 stack<int> s; /*哈夫曼树结点类HuffmanNode声明*/ template<class T> class HuffmanNode { private: HuffmanNode<T>
C++实现哈夫曼树算法

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

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

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

本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下准备工作: 1.定义一个结构体,表示一个节点.其中,这个结构体有4个成员变量,分别表示是这个节点的权值,父节点及左右子节点的下标 2.定义一个整形数组,用于存放各个节点的权值 3.定义一个整形数组,用于存放哈夫曼编码,当然也可以定义一个整形数组来存放哈夫曼编码构建哈夫曼树: 1.给这个哈夫曼树创建一个结构体数组,其中分配的空间是2 * n - 1,因为我们都知道哈夫曼树的性质有一个是:给定n个叶子节点,那么由这n个叶子
C++实现哈夫曼树的方法

序言对于哈夫曼编码,个人的浅薄理解就是在压缩存储空间用很大用处. 用一个很简单例子,存储一篇英文文章时候,可能A出现的概率较大,Z出现的记录较小,如果正常存储,可能A与Z存储使用的空间一样.但是用哈夫曼编码方式,A经常出现,所用编码长度就短. 构造哈夫曼树,生成哈夫曼编码一.定义节点类型 struct Node { char C; long key; Node *Left, *Right,*parent; Node() { Left = Right = NULL; } }; 二.定义树类型(
解读赫夫曼树编码的问题

定义: 结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积.树的带权路径长度为树中所有叶子结点的带权路径长度之和.假设有n个权值,试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度最小的二叉树称做最优二叉树或赫夫曼树. 构造赫夫曼树的方法: (1)根据给定的n个权值{w1,w2,w3......}构成n棵二叉树的集合F={T1,T2,T3,T4......},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空. (2)在F中选取两棵根结点的权值
Java数据结构之哈夫曼树概述及实现

一.与哈夫曼树相关的概念概念含义 1. 路径从树中一个结点到另一个结点的分支所构成的路线 2. 路径长度路径上的分支数目 3. 树的路径长度长度从根到每个结点的路径长度之和 4. 带权路径长度结点具有权值, 从该结点到根之间的路径长度乘以结点的权值, 就是该结点的带权路径长度 5. 树的带权路径长度树中所有叶子结点的带权路径长度之和二.什么是哈夫曼树定义: 给定n个权值作为n个叶子结点, 构造出的一棵带权路径长度(WPL)最短的二叉树,叫哈夫曼树(), 也被称为最最优二叉树.
java数据结构图论霍夫曼树及其编码示例详解

目录霍夫曼树一.基本介绍二.霍夫曼树几个重要概念和举例说明构成霍夫曼树的步骤霍夫曼编码一.基本介绍二.原理剖析注意: 霍夫曼编码压缩文件注意事项霍夫曼树一.基本介绍二.霍夫曼树几个重要概念和举例说明构成霍夫曼树的步骤举例:以arr = {1 3 6 7 8 13 29} public class HuffmanTree { public static void main(String[] args) { int[] arr = { 13, 7, 8
C++深入讲解哈夫曼树

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

本文实例讲述了Python数据结构之哈夫曼树定义与使用方法.分享给大家供大家参考,具体如下: HaffMan.py #coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=None class HaffTree: def __init__(self): sel
图文详解JAVA实现哈夫曼树

前言我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

C++实现哈夫曼树的方法

相关推荐

随机推荐