C++深入讲解哈夫曼树

目录
  • 哈夫曼树的基本概念
    • 1）路径
    • 2）路径长度
    • 3）权
    • 4）结点的带权路径长度
    • 5）树的带权路径长度
    • 6）哈夫曼树
  • 哈夫曼树的构造算法
    • 哈夫曼树的构造过程
    • 哈夫曼树算法的实现
      • 1）结点的存储结构
      • 2）构建哈夫曼树

哈夫曼树的基本概念

Q：什么是哈夫曼树

A：哈夫曼树又称最优树，是一类带权路径长度最短的树。在正式了解哈夫曼树之前，我们需要了解一些概念。

1）路径

Q：什么是路径

A：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

2）路径长度

Q：什么是路径长度

A：路径上的分支数目称作路径长度。如图根结点到结点B的路径长度为2

3）权

Q：什么是权

A：若将树中结点赋给一个带有某种含义的数值，则该数值称为该结点的权。如图A的权是7

4）结点的带权路径长度

Q：什么是结点的带权路径长度

A：从该结点到树根之间的路径长度与结点上权的乘积

5）树的带权路径长度

Q：什么是树的带权路径长度

A：树中所有叶子结点的带权路径长度之和，通常记作 WPL。如图WPL=7*1+5*2+2*3+4*3=35

6）哈夫曼树

Q：什么是树的带权路径长度

A：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称该二叉树为哈夫曼树，也被称为最优二叉树。

Q：哈夫曼树中具有不同权值的叶子结点的分布有什么特点呢？

A：从上面的例子中，可以直观的发现，在哈夫曼树中，权值越大的结点离根结点越近。根据这个特点，哈夫曼最早给出了一个构造哈夫曼树的方法，称为哈夫曼算法。

哈夫曼树的构造算法

哈夫曼树的构造过程

Q：假设有4个叶子结点，权重依次是7，5，2，4，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？

第一步：将这4个结点分别作为4棵仅含有一个结点的二叉树，形成一个森林

第二步：选择当前权值最小的两个结点C和D，根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和

第三步：选择当前权值最小的两个结点，再次根据这两个结点生成一个新的父结点。现在剩下的结点有7，6，5，我们根据6和5生成新的父节点。

第四步：选择当前权值最小的两个结点，再次根据这两个结点生成一个新的父结点。现在剩下的结点有7，11，我们根据7和11生成新的父节点。

就这样，我们得到了最终的二叉树

哈夫曼树算法的实现

1）结点的存储结构

哈夫曼树是一种二叉树，树中每个结点要包含其双亲信息和孩子结点的信息，由此，每个结点的存储结构如图：

typedef struct{
	int weight;		 			//结点的权值
	int parent,lchild,rchild; 	//结点的双亲、左孩子、右孩子的下标
) HTNode,*HuffmanTree; 			//动态分配数组存储哈夫曼树

2）构建哈夫曼树

构建哈夫曼树主要分为两大部步

第一步为森林结点的初始化，第二步为哈夫曼树的建立。

代码演示

void CreateHuffmanTree(HuffmanTree &HT,int n)
{//构造哈夫曼树 HT
	if(n<=1) return;
	m=2*n-1;
	HT=new HTNode[m+1]; 		//0 号单元未用，所以需要动态分配 m+l 个单元， HT[m)表示根结点
	for(i=1;i<=m;++i) 			//将l~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
	{
		HT[i].parent=O;
		HT[i].lchild=O;
		HT[i].rchild=O;
	}
	for(i=1;i<=n;++i)			//输人前 n 个单元中叶子结点的权值
		cin>>HT[i].weight;
	for(i=n+1;i<=m;++i)
	{//通过 n-1 次的选择、删除 、 合并来创建哈夫曼树
		Select (HT,i-1,s1,s2);
		//在 HT[k] 中选择两个其双亲域为 0 且权值最小的结点，并返回它们在 HT 中的序号 s1和 s2
		HT[s1].parent=i;
		HT[s2].parent=i;
		//得到新结点 i, 从森林中删除sl, s2, 将sl和s2 的双亲域由 0改为l.
		HT[i].lchild=s1;
		HT[i].rchild=s2; 		//sl, s2分别作为 i 的左右孩子
		HT[i].weight=HT[s1].weight+HT[s2].weight; // i 的权值为左右孩子权值之和
	}
}

到此这篇关于C++深入讲解哈夫曼树的文章就介绍到这了,更多相关C++哈夫曼树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 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++ 哈夫曼树对文件压缩、加密实现代码

    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++实现哈夫曼树算法

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

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

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

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

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

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

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

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

  • C++详解哈夫曼树的概念与实现步骤

    C++详解哈夫曼树的概念与实现步骤

    目录 一. 基本概念 二.构造哈夫曼树 三.哈夫曼树的基本性质 四.哈夫曼编码 五.哈夫曼解码 六.文件的压缩和解压缩 一. 基本概念 结点的权: 有某种现实含义的数值 结点的带权路径长度: 从结点的根到该结点的路径长度与该结点权值的乘积 树的带权路径长度: 树上所有叶结点的带权路径长度之和 哈夫曼树: 在含有 n n n个带权叶结点的二叉树中, w p l wpl wpl 最小 的二叉树称为哈夫曼树,也称最优二叉树(给定叶子结点,哈夫曼树不唯一). 二.构造哈夫曼树 比较简单,此处不赘述步骤

  • 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++深入讲解哈夫曼树

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

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

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

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

  • 图文详解JAVA实现哈夫曼树

    图文详解JAVA实现哈夫曼树

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

  • 解读赫夫曼树编码的问题

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

  • java哈夫曼树实例代码

    本文实例为大家分享了哈夫曼树java代码,供大家参考,具体内容如下 package boom; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; class Node<T> implements Comparable<Node<T>>{ private T

随机推荐