构造哈夫曼树的过程是这样的
一、构成初始集合
对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算法,一般还要求以Ti的权值Wi的升序排列。)
二、选取左右子树
在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、删除左右子树
从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步,
重复二和三两步,直到集合F中只有一棵二叉树为止。
举个例子
有个序列是(7,9,2,6,32,3,21,10)
叫你求哈夫曼树
步骤一:把这些点都看成是一个只有根结点的树的集合F
步骤二,选2个值最小的树
步骤三:在这些树的集合F中删除这2棵树
然后把构成一颗二叉树
变成了(5=2+3)
然后把这个树加入到集合F
5代表这棵树的权值
然后继续上述步骤
肯定是选5和6
把这2个构成二叉树
在F中删除56加入11这棵树
变成了
继续上述步骤
选7和9
在F中删除7和9
加入16这棵树
变成了
继续上述步骤
选10和11
在F中删除10和11加入21这棵树
继续上述步骤
选16和21(有2个21,随便选哪个)
我选那个只有一个根结点的21好了
16和21构成二叉树
在F中删除这16和21这两棵树
加入37这棵树
继续上述步骤
选21和32
构成二叉树
在F中删除21和32这2两棵树
加入53这棵树
还是继续上面步骤
把F中的两棵树合并成一棵树
分享到:
相关推荐
哈夫曼树构造
哈夫曼树的构造以及应用。其应用主要是信息编码。
哈弗曼树的构造与编码,对txt文件内的文件进行编码、解码
数据结构哈夫曼树PPT学习教案.pptx
构建哈夫曼树,对其进行编码,实现译码功能,数据结构的实验报告。。
哈夫曼树构造 输出
数据结构基于C++的书实验的代码,有需要的可以下载参考
讲解构造哈夫曼树的过程,超详细。 对于不理解哈夫曼树的过程构造的新人来讲,十分有用!
给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短...使用数组构建哈夫曼树,并可用该树构造哈夫曼编码。
构造哈夫曼树,并生成编码 构造哈夫曼树,并生成编码
哈夫曼树与哈夫曼编码 建立哈夫曼树并计算哈夫曼编码
//哈夫曼树构造的基本思想,从list中取出最小的两个节点,构造出他们的父节点, //然后将这两个节点从list中删除,将他们的父节点插入list中,左孩子code设置为0,右孩子code设置为1, //直到list为空。 //接下来...
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2.利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入...
如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树
用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树
哈夫曼树是最优二叉树的另一种说法。本程序测试已通过。而且还有范例。供广大学子学习非常棒哦。
此程序可以实现构造哈夫曼树,并对其进行编码和二进制文的译码
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
头歌数据结构构建哈夫曼树及编码 第1关构建哈夫曼树 第2关根据哈夫曼树构建哈夫曼编码 通过哈夫曼树的构造,深刻理解二叉树的构造。...第二关:根据构建好的哈夫曼树构造字符的前缀编码(哈夫曼编码)。
数据结构 堆结构的完整源码与哈夫曼树的构造