Archives: 哈夫曼树的构造算法

Advertisement

哈夫曼树的构造算法

哈夫曼树的构造算法 typedef struct { char data; double weight; int parent; int lchild; int rchild; }HTNode; void CreateHT(HTNode ht[],int n) { int i,j,k,lnode,rnode; double min1,min2; for(i=0;i<2*n-1;i++) ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2

赫夫曼树 - 数据结构和算法51

赫夫曼树 让编程改变世界 Change the world by program 赫夫曼树 在数据膨胀.信息爆炸的今天,数据压缩的意义不言而喻.谈到数据压缩,就不能不提赫夫曼(Huffman)编码,赫夫曼编码是首个实用的压缩编码方案,即使在今天的许多知名压缩算法里,依然可以见到赫夫曼编码的影子. 另外,在数据通信中,用二进制给每个字符进行编码时不得不面对的一个问题是如何使电文总长最短且不产生二义性.根据字符出现频率,利用赫夫曼编码可以构造出一种不等长的二进制,使编码后的电文长度最短,且保证不产生

哈夫曼树压缩C#算法(huffman)

算法原理:http://www.cnblogs.com/skywang12345/p/3706833.html. 上代码: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; using System.Threading; using System.IO; using System.Web.Script; using Syst

数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义 1.路径 Path 简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的分支,比如下图中的红色分支(A->C->B与C->D->E->F) 图1 2.路径长度(Path Length) 即路径中的分支个数,比如上图(a)中的路径长度为2,上图(b)中的路径长度为3 3.结点的权重(Weight of Node) 在一些特定应用中,有时候要刻意区分节点之间的重要程度(或优先程度),比如认为A

赫夫曼树、赫夫曼编码和JAVA实现

要学习赫夫曼树和赫夫曼编码,先来看一下问题的提出: 一.问题引入. 下面一段程序用来给学生考试成绩划分等级: 这段程序的判断过程如图: 图1 不过这样的判断算法效率可能有问题,因为对于一般的考卷,学生成绩在5个等级上的分布规律如下表: 分数 0 ~ 59 60 ~ 69 70 ~ 79 80 ~ 89 90 ~ 100 所占比例 5% 15% 40% 30% 10% 仔细观察,中等成绩(70 ~ 79)比例最高,其次是良好(80 ~ 89),不及格所占比例最少.80%的分数都要经过三次及以上的比

哈夫曼树构造算法的正确性证明

哈夫曼树构造 1.哈夫曼树的定义 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree). 2.哈夫曼树的构造 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1,w2,-,wn,则哈夫曼树的构造规则为: (1) 将w1,w2,-,wn看成是有n 棵树的森林(每棵树仅有一个结点): (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左.右子树,且新树的根结点权值为其左.右子

[数据结构]哈夫曼树、哈夫曼编码(转)

哈夫曼树又称最优树(二叉树),是一类带权路径最短的树.构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用. 结点之间的路径长度:从一个结点到另一个结点之间的分支数目. 树的路径长度:从树的根到树中每一个结点的路径长度之和. 结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积. 树的带权路径长度:树中所有叶子结点的带权路径长度之和,记作: WPL为最小的二叉树就称作最优二叉树或哈夫曼树. 完全二叉树不一定是最优二叉树. 哈夫曼树的构造: (1)根

[数据结构]哈夫曼树、哈夫曼编码

哈夫曼树又称最优树(二叉树),是一类带权路径最短的树.构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用. 结点之间的路径长度:从一个结点到另一个结点之间的分支数目. 树的路径长度:从树的根到树中每一个结点的路径长度之和. 结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积. 树的带权路径长度:树中所有叶子结点的带权路径长度之和,记作: WPL为最小的二叉树就称作最优二叉树或哈夫曼树. 完全二叉树不一定是最优二叉树. 哈夫曼树的构造: (1)根

什么是哈夫曼树?哈夫曼树的概念和定义

一.哈夫曼树的概念和定义 什么是哈夫曼树? 让我们先举一个例子. 判定树: 在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率.例如,编制一个程序,将百分制转换成五个等级输出.大家可能认为这个程序很简单,并且很快就可以用下列形式编写出来: if(score< 60) System.out.println("不及格"); else if(score< 70) System.out.println("及格"); els

哈夫曼树(最优二叉树)纯C实现

哈夫曼树的构造规则为: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1.w2.-.wn (1) 将w1.w2.-,wn看成是有n 棵树的森林(每棵树仅有一个结点): (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左.右子树,且新树的根结点权值为其左.右子树根结点权值之和: (3)从森林中删除选取的两棵树,并将新树加入森林: (4)重复(2).(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树. huffman_tree.c /*******

树之哈夫曼树(最优二叉树)

本文来介绍哈夫曼树.哈夫曼树又叫最优二叉树,是一种特殊的二叉树.这种二叉树最重要的特征就是:树的带权路径长度(Weighted Path Length of Tree,简记为WPL)最小.本文给出了哈弗曼算法的实现过程,代码部分已经描述的比较详细,这里就不再叙述了. 需要说明的是哈夫曼树的构造并不唯一,因为其左右子树位置交换,并不影响该二叉树的带权路径长度最小的性质.哈夫曼树有许多应用,比如说哈夫曼编码等等,哈夫曼编码将在我的下一篇博文中作简要介绍. #include<cstdio> #inc

哈夫曼树的基本概念与应用

2013-08-20 08:43:28 http://sjjg.js.zwu.edu.cn/SFXX/shu/shu4.6.2.html 1. 哈夫曼树的基本概念 哈夫曼树( Huffman )又称最优二叉树,是一类带权路径长度最短的树,有着广泛的应用. 在讨论哈夫曼树之前首先需要弄清楚关于路径和路径长度的概念.树中两个结点之间的路径由一个结点到另一结点的分支构成.两结点之间的路径长度是路径上分支的数目.树的路径长度是从根结点到每一个结点的路径长度之和. 设一棵二叉树有 n 个叶子结点,每个叶子

1020 小白鼠:哈夫曼树

1020 小白鼠 小白鼠 时间限制: 1秒 内存限制: 64M Description 有 n 个瓶子,已知其中有且仅有一个瓶子的饮料有毒.现在我们想知道哪个瓶子的饮料有毒,于是找来一些小白鼠做测试. 假设我们有足够多的小白鼠,为了加快测试速度,我们每次可以把来自若干个瓶子的测试样本混在一起,喂给小白鼠.如果小白鼠喝了有毒的饮料,即死. 现在给你每个瓶子的饮料有毒的概率(和总是 100% ),问以最优策略(测试次数尽可能少)执行,期望的测试次数是多少? Input 输入第一行为数据组数 T (

萌新学习笔记之哈夫曼树

哈夫曼树的定义: 假设有n个权值{ w1,w2 , ... , wn},构造有n个叶结点的二叉树,每个叶结点的权值是n个权值之一,这样的二叉树可以构造很多棵,其中必有一棵是带权路径长度最小的,这棵二叉树就称为最优二叉树或哈夫曼树: typedef struct TreeNode* HuffmanTree; struct TreeNode{ int Weight; HuffmanTree Left; HuffmanTree Right; }; 哈夫曼树的构造 (懒得写了,摘自百度百科,亲测很好):

hdu 1053 哈夫曼树 优先队列

此题关于哈夫曼编码. 哈夫曼树(霍夫曼树)又称为最优树. 基本术语: 1.路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1. 2.结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权.结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积. 3.树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之

哈夫曼树原理及构造

构造哈夫曼树的过程是这样的 一.构成初始集合 对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空.(为方便在计算机上实现算法,一般还要求以Ti的权值Wi的升序排列.) 二.选取左右子树 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和. 三.删除左右子树 从F中删除这两棵树,

构造哈夫曼树

1.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径长度最小 2.步骤 输入叶子结点个数n: 创建长度为2*n-1的数组并初始化: while(i<n) 循环输入n个叶子结点的权值: while(n-1次循环建立树){ 在parent==-1的元素中查找权最小的两个结点: 合并两个叶子结点,并加入新结点到数组: } 3.代码 //构造haffman树 #include <iostream> using namespace std; const int MAX = 10000; s

自己找的关于 数据结构与算法:哈夫曼树(源码)!

数据结构与算法:哈夫曼树(源码)! 这些天明白了一个道理,搞技术也是需要激情的. 也不知道为什么这段过的感觉特别的不爽,也不知道是因为快要考试了,心里没底,而带来的恐惧,还是 搞技术太久,心里想放个假,总之是过的晕晕乎乎,做事情也总是反应迟钝,思维也不快,我爸妈说我是因为睡 不够,但是我觉得我一晚上睡6个半小时,也不算短了.真不知道这样的感觉还要持续多久. 习惯了,下课就做到电脑前,习惯了,晚上一个人回宿舍,习惯了,饿了随便吃点,习惯了,一个人钻研. 当一切开始成为了定式,总觉得生活变的简单.有

构造赫夫曼树

//算法5.10构造赫夫曼树 #include <iostream> using namespace std; //-----赫夫曼树的存储表示---- typedef struct{ int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; void Select(HuffmanTree HT,int len,int &s1,int &s2) { int i,min1=0x3f3f3f3f,min2=0x3f3f3