精华内容
下载资源
问答
  • 哈夫曼树算法实现

    千次阅读 2017-05-01 16:07:15
    哈夫曼树(Huffman Tree),即最优二叉树(optimium binary tree),是一类带权路径长度最短的二叉树。 1、哈夫曼树的构造方法 1)根据n个权值w1,w2,w3......wn构造n棵二叉树的森林F={T1,T2,T3......Tn}Ti含带权为...

    哈夫曼树(Huffman Tree),即最优二叉树(optimium binary tree),是一类带权路径长度最短的二叉树。

    1、哈夫曼树的构造方法

    1)根据n个权值w1,w2,w3......wn构造n棵二叉树的森林F={T1,T2,T3......Tn}Ti含带权为wi的根节点,无左右子树;

    2)在森林F中选择两可根节点权值最小的二叉树作为左右子树,合并为新的二叉树,并删除这两棵二叉树;

    3)重复2)步,直到只剩一颗二叉树,即为哈夫曼树

    2、哈夫曼树的应用

    1)改善判定树。利用哈夫曼树得到最优判定算法。

    2)哈夫曼编码

    3、哈夫曼树编码算法

    类声明:

    const int N=30;//叶节点的最大数
    const int M=2*N-1;//总结点的最大数
    const int MAX=9999;//最大常量
    const int L=20;//编码最大长度
    struct element
    {
          int weight;
          int lchild,rchild,parent;
    };//结构类型说明
    typedef struct
    {
          char bits[N];//用于存放位串
          int start;//用于存放编码在位串中的起始位置
          char ch;//编码存储的结构类型说明
    }codetype;

    1)建立哈夫曼树的算法

    void HuffmanTree(elemrnt hT[],int w[],int n)
    {
          int i,k,,i1,i2;
          for(i=0;i<2*n-1;i++)  hT[i].parent=hT[i].lchild=hT[i].rchild=-1;
          for(i=0;i<n;i++)  hT[i].weight=w[i];
          for(k=n;k<2*n-1;k++){
                Select(hT,i1,i2,k);
                hT[i1].parent=hT[i2].parent=k;
                hT[k].weight=hT[i1].weight+hT[i2].weight;
                hT[k].lchild=i1;
                hT[k].rchild=i2;
          }
    }

    选取最小两棵二叉树的函数Select():

    void Select(element hT[],int &i1,int &i2,int k)
    {
        int min1=MAX,min2=MAX;//MAX为较大常数,如9999
        i1=0;i2=0;//分别记录最小和次小所在的下标值
        for(int i=0;i<k;i++)//找出min1<=min2 两个最小
            if(hT[i].parent==-1)//一定在双亲为空的结点中找
                  if(hT[i].weight<min1){
                      min2=min1;i2=i1;min1=hT[i].weight;i1=i;
                  }else if(hT[i].weight<min2){
                      min2=hT[i].weight;i2=i;
                  }
    }

    2)建立哈夫曼编码的算法:

     

    void HuffmanCode(element hT[],codetype code[],int n)
    {
        int i,c,;codetype cd;
        for(i=0;i<n;i++){
            cd.start=n;c=i;p=hT[[c].parent;//i的双亲p
            while(p!=-1){
                cd.start--;
                if(hT[p].lchild==c)
                    cd.bits[cd.start]='0';
                else
                    cd.bits[cd.start]='1';
                c=p;
                p=hT[c].parent;
            }
            code[i]=cd;
        }
    }

     

     

     

     

    展开全文
  • HT[i].rch=s2 Select函数具体的实现方法和本片完整的代码,如下文章: c语言构造哈夫曼树-哈夫曼编码_快乐的孙悟空的博客-CSDN博客_c语言哈夫曼树 void Select(HuffmanTree &HT,int x){//选出无父结点,并且权值最小...

    先考虑如何存储:既可以链式也可以顺序,但顺序存储结构(数组)简单点

    这里用一维结构数组,结构数组是因为我们要保存的结点的值比较多,先看结点的类型定义

    那几个值?每一个都要知道他的权值weight是多少,双亲parent是谁,左右孩子lch,rch是谁,所以4个值,定义成一个结构类型

    数组如图:它有多大?它有2n-1个元素(n个结点进行n-1次合并......)为了简单,我们不使用0下标,所以数组的大小为2n,从1到2n-1,我们不用0就可以了

    每一个元素有4个成员,我们用指针类型--哈夫曼树*Huffman来定义一个H:Huffman H,h就可以表示一个指针,或者数组

    让第一个结点的权值为5,同理继续......

    例子:7+8=15,就可以定义一个16的数组(0-15),只用1到15

    首先,所有元素的双亲和孩子都为0(构造森林全是根),用0来表示没有,然后输入权值

    生成n-1个结点,用循环,因为我们这里有n个叶子,所以我们从n+1开始:i=n+1,我们共有2n-1,直到2n-1结束

    选两小造新树:2,3,生成的5在9号结点,删掉2,3......

    剩下parent为0,只有一个根,结束

    先初始化:1.左右孩子,parent设置为0;2.输入权值

    定义数组m=2n-1个元素

    2n-1在加1就是2m,这里0号不用,所以m+1

    weighr要一个一个输入

    再n-1次合并,放在n+1到2n-1:

    找到了,他们两个的双亲就是新产生的结点i:HT[s1].parent=i,HT[s2].parent=i

    新产生节点的权重就是两个最小的权重的和:HT[i].weight=HT[s1].weight+HT[s2].weight

    左孩子为s1,右孩子为s2:HT[i].lch=s1;HT[i].rch=s2

    Select函数具体的实现方法和本片完整的代码,如下文章:

    c语言构造哈夫曼树-哈夫曼编码_快乐的孙悟空的博客-CSDN博客_c语言哈夫曼树

    void Select(HuffmanTree &HT,int x){//选出无父结点,并且权值最小的两个结点,赋值给s1,s2 
        int i,min1=inf,min2=inf;
        for(i=1;i<=x;i++){//找最小 
            if(HT[i].weight<min1&&HT[i].parent==0){min1=HT[i].weight;s1=i;}
        }
        for(i=1;i<=x;i++){//找次小 
            if(HT[i].weight<min2&&i!=s1&&HT[i].parent==0){
                min2=HT[i].weight;s2=i;
            }
        }
    }
     

    展开全文
  • 哈夫曼树:是一种带权路径长度最短的二叉树,也称为最优二叉树。 一般可以按下面步骤构建: 将所有左,右子树都为空的作为根节点。 在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的附加...

    哈夫曼树:是一种带权路径长度最短的二叉树,也称为最优二叉树。

    一般可以按下面步骤构建:

    1. 将所有左,右子树都为空的作为根节点。
    2. 在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的附加根节点的权值为其左,右子树上根节点的权值之和。注意,左子树的权值应小于右子树的权值。
    3. 从森林中删除这两棵树,同时把新树加入到森林中。
    4. 重复2,3步骤,直到森林中只有一棵树为止,此树便是哈夫曼树。

    大家可能更多听说的是哈夫曼编码,其实就是哈夫曼树的应用。即如何让电文中出现较多的字符采用尽可能短的编码且保证在译码时不出现歧义。

    在这里插入图片描述

    展开全文
  • 哈夫曼树算法思想

    千次阅读 2020-11-25 22:48:14
    利用哈夫曼树算法思想设计内线电话号码,使得接线员拨号次数尽可能少。要求: (1)依据使用外线电话的频率构造二叉树; (2)输出设计出的各部门内线电话号码。 //6.4 Huffman树 package huffmanTree; public ...

    一个单位有12个部门,每个部门都有一部电话,但是整个单位只有一根外线,当有电话打过来的时候,由转接员转到内线电话,已知各部门使用外线电话的频率为(次/天):5 20 10 12 8 43 5 6 9 15 19 32。
    利用哈夫曼树算法思想设计内线电话号码,使得接线员拨号次数尽可能少。要求:
    (1)依据使用外线电话的频率构造二叉树;
    (2)输出设计出的各部门内线电话号码。

    
    //6.4  Huffman树
    package huffmanTree;
    
    public class TriElement {// 二叉树的静态三叉链表结点类
    	int data; // 数据域
    	int parent, left, right; // 父母结点和左、右孩子结点下标
    
    	// 构造结点,各参数依次指定元素、父母结点下标、左/右孩子结点下标
    	public TriElement(int data, int parent, int left, int right) {
    		this.data = data;
    
    		this.parent = parent;
    
    		this.left = left;
    
    		this.right = right;
    	}
    
    	public TriElement(int data) {// 构造元素值为data、无父母的叶子结点
    		this(data, -1, -1, -1);
    	}
    
    	public String toString() { // 返回结点的描述字符串
    		return "(" + this.data + "," + this.parent + "," + this.left + "," + this.right + ")";
    	}
    
    	public boolean isLeaf() {// 判断是否叶子结点
    		return this.left == -1 && this.right == -1;
    	}
    }
    
    
    package huffmanTree;
    
    public class HuffmanTree1 {
    
    	private int leftNum;
    
    	private TriElement[] hufftree;
    
    	public HuffmanTree1(int[] weight) {
    
    		int n = weight.length;
    
    		this.leftNum = n;
    
    		this.hufftree = new TriElement[2 * n - 1];
    
    		for (int i = 0; i < n; i++)
    
    			this.hufftree[i] = new TriElement(weight[i]);
    
    		for (int i = 0; i < n - 1; i++) {
    
    			int min1 = Integer.MAX_VALUE, min2 = min1;
    
    			int x1 = -1, x2 = -1;
    
    			for (int j = 0; j < n + i; j++)
    
    				if (hufftree[j].data < min1 && hufftree[j].parent == -1) {
    
    					min2 = min1;
    
    					x2 = x1;
    
    					min1 = hufftree[j].data;
    
    					x1 = j;
    
    				} else if (hufftree[j].data < min2 && hufftree[j].parent == -1) {
    
    					min2 = hufftree[j].data;
    
    					x2 = j;
    
    				}
    
    			hufftree[x1].parent = n + i;
    
    			hufftree[x2].parent = n + i;
    
    			this.hufftree[n + i] = new TriElement(hufftree[x1].data + hufftree[x2].data, -1, x1, x2);
    
    		}
    
    	}
    
    	public String[] huffmanCodes() {
    
    		String[] hufcodes = new String[this.leftNum];
    
    		for (int i = 0; i < this.leftNum; i++) {
    
    			hufcodes[i] = " ";
    
    			int child = i;
    
    			int parent = hufftree[child].parent;
    
    			while (parent != -1) {
    
    				if (hufftree[parent].left == child)
    
    					hufcodes[i] = "0" + hufcodes[i];
    
    				else
    
    					hufcodes[i] = "1" + hufcodes[i];
    
    				child = parent;
    
    				parent = hufftree[child].parent;
    
    			}
    		}
    		return hufcodes;
    	}
    
    }
    
    
    package huffmanTree;
    
    public class HuffmanTree_example {
    
    	public static void main(String[] args) {
    
    		int[] weight = { 5, 20, 10, 12, 8, 43, 5, 6, 9, 15, 19, 32 };
    
    		HuffmanTree1 htree = new HuffmanTree1(weight);
    
    		String[] code = htree.huffmanCodes();
    
    		System.out.println("Huffman 的编码是:");
    
    		for (int i = 0; i < code.length; i++)
    
    			System.out.println((char) ('A' + i) + ":" + code[i] + " ");
    
    	}
    
    }
    
    

    结果如下:

    在这里插入图片描述

    展开全文
  • 构造哈夫曼树算法C/C++

    千次阅读 2016-10-30 10:24:57
    一、哈夫曼树的基本概念 最优二叉树也称哈夫曼树,是指对于一组带有确定权值的叶节点,构造的具有最小带权路径长度的二叉树。二、哈夫曼树的结构 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别...
  • Python描述数据结构之哈夫曼树

    千次阅读 多人点赞 2020-09-06 20:35:21
    本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。
  • 本文实例讲述了C++数据结构与算法哈夫曼树的实现方法。分享给大家供大家参考,具体如下: 哈夫曼树又称最优二叉树,是一类带权路径长度最短的树。 对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的...
  • 一、哈夫曼树的基本概念在一棵二叉树中,定义从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径。从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度从二叉树的根结点到二叉树中所有叶结点的路径...
  • 先构建以这个n个结点为叶子结点的哈夫曼树,然后由哈夫曼树产生各叶子结点对应字符的哈夫曼编码。 (0)哈夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树...
  • 主要为大家详细介绍了C语言实现哈夫曼树的构建,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 哈夫曼树建立.cpp

    2020-01-04 17:30:41
    自己码的C语言哈弗曼的建立,代码格式整齐,清晰易懂,能正确运行,包含文件的编码解码和压缩功能,很不错的代码,很容易用其他语言复现
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过...
  • 哈夫曼树建立算法

    千次阅读 2018-11-25 13:01:01
    哈夫曼树的建立  Problem Description 由若干个值无重复的结点及其权值,建立相应的哈夫曼树。在合并过程中,若出现权值相同的情况,则优先选取编号小的进行合并;要求哈夫曼树中所有左孩子编号小于右孩子编号...
  • 哈夫曼树的构造算法代码

    千次阅读 2020-05-05 21:24:19
    代码: #include<stdio.h> #define ERROR 0 #define OK 1 typedef int Status; //采用顺序存储结构,一维结构数组 //定义结点类型 typedef struct { int weight; int parent,lch,rch;...//哈夫曼树...
  • 哈夫曼树和哈夫曼编码 二叉树及二叉树的遍历 二叉树,从名字上就能理解,两个叉的树,每个父节点只有左子节点和右子节点。 ![这是一棵二叉树](/home/pidan/图片/2018-12-06 15-29-08 的屏幕截图.png) 关于...
  • 哈夫曼树算法如下 (1)根据给定的n个权值,使对应节点构成n棵二叉树的森林,其中每棵二叉树都只有一个根节点,其左右子树均为空。 (2)在森林中选取两棵节点权值最小的子树分别作为左右子树构造一棵新的二叉树,且...
  • 基于哈夫曼树的数据压缩算法 描述 假设I和O分别代表入栈和出栈操作。栈的始态和终态均为空。入栈和出栈的操作序列可以表示为仅由I和O组成的序列,称可操作的序列为合法序列,否则称为非法序列。请设计一个算法,判断...
  • 哈夫曼树1.1 基本概念算法思想贪心算法(以局部最优,谋求全局最优)适用范围1 【(约束)可行】:它必须满足问题的约束2 【局部最优】它是当前步骤中所有可行选择中最佳的局部选择3 【不可取消】选择一旦做出,在...
  • C例子:哈夫曼树

    2015-08-24 09:06:17
    该程序是我写的博客“一起talk C栗子吧(第四十一回:C语言实例--哈夫曼树)”的配套程序,共享给大家使用
  • 学校数据结构实验(c语言描述)布置了写求哈夫曼编码的作业,书上采用的是从叶子到根逆向求编码的方式(清华版数据结构c语言描述),我这里给出先序遍历,即“根左右”进行哈夫曼编码的代码#includ...
  • 数据结构,一门数据处理的艺术,精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美,在为信息技术打下坚实地基的同时,也令无数开发者和探索者为之着迷。 也因如此,它作为博主大二上学期最重要的...
  • 哈夫曼树 对于哈夫曼树,凡是学过离散数学的同学肯定不会陌生,这里我们简略它的介绍。 哈夫曼树就是最优二叉树,即叶子个数和各个叶子的权值确定的情况下,树的带权路径长度(树中所有叶子结点的带权路径(带权路径...
  • 什么是贪心算法 顾名思义,贪心算法是通过判断当前状态下看起来最好的结果,作为最好的结果。 一般来说,我们使用贪心算法的情况为需要一步步解决的问题,其中的每一个步骤都有一系列的选择, 比如01背包问题,我们...
  • 哈夫曼树算法(数据结构C++描述

    千次阅读 2011-11-26 22:28:35
    //哈夫曼树算法 #include using namespace std; const int n=5; const int m=2*n-1; const int float_max=20; typedef int datatype; typedef struct { float weight; //定义权重 int parent; //定义双亲在...
  • 哈夫曼树 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码。 首先介绍什么是...
  • 1.逻辑上哈夫曼树是树结构,但程序的物理结构是数组。 2.树构建好后,规定一下左右是0还是1,然后遍历树的每条路径,即可得到每个数据的编码结果。 代码如下: //哈夫曼编码 typedef struct mesage//在优先级队列...
  • 给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。使用数组构建哈夫曼...
  • 数据结构与算法之构建哈夫曼树

    千次阅读 2020-03-07 11:25:13
    哈夫曼树的介绍 Huffman Tree,中文名是哈夫曼树或霍夫曼树或者赫夫曼树,它是最优二叉树。 定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树。 (01) 路径和...
  • 《数据结构与算法》 ...实验名称哈夫曼树实现 学院信息与通信工程学院 年级专业20级智能科学与技术 姓名孙成 学号20203101694 指导教师冯思玲 开课时间2020至2021学年第二学期 实验报告正文 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,089
精华内容 2,035
关键字:

哈夫曼树算法描述