简单介绍哈夫曼树

《简单介绍哈夫曼树》由会员分享，可在线阅读，更多相关《简单介绍哈夫曼树（15页珍藏版）》请在金锄头文库上搜索。

1、简单介绍哈夫曼树本篇文章给大家带来的内容是哈夫曼树，简单介绍一下哈夫曼树，以及解析，希望对大家的学习有所 帮助。废话不多说，马上进入正题。给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最 优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较 近。哈夫曼树是二叉树的一个典型应用，利用哈夫曼树，我们可以形成哈夫曼编码，进而实现对数据的压 缩与解压处理。哈夫曼树，指的是对于一组具有确定权值的叶子结点的具有最小带权路径长度的二叉树。哈夫曼树当中的几个概念我们不得不说一下:(1) 路劲(Path):从树中的一个

2、结点到另一个结点之间的分支构成两个结点间的路径。(2) 路径长度(Path Length):路径上的分支树。(3) 树的路径长度(Path Length of Tree):从树的根结点到每个结点的路径长度之和。在结点数目相同 的二叉树中，完全二叉树的路径长度最短。(4) 结点的权(Weight of Node):在一些应用中，赋予树中结点的一个有实际意义的树。(5) 结点的带权路径长度(Weight Path Length of Node):从该结点到树的根结点的路径长度与该结点 的权的乘积。(6) 树的带权路径长度(WPL):树中所有叶子结点的带权路径长度之和在下图所示的四棵二叉树，都有4个

3、叶子结点，其权值分别1、2、3、4,他们的带权路径长度分别为:(a) WPL =1x2+2x2+3x2+4X2=20(b) WPL =1x1+2x2+3x3+4x3=28(c) WPL =1x3+2x3+3x2+4x1=19(d) WPL = 2 x 1 + 1 x 2 + 3 x 3 + 4 x 3 = 29242InniriBLnl其中，（c）图所示的二叉树的带权路径长度最小，这棵树就是哈夫曼树。可以验证，哈夫曼树的带权路 径长度最小。那么我们应该如何构建一个哈夫曼树呢?其实并不复杂：1）首先构建一个叶子节点集合，这里我用链表来表示，每个节点在插入到链表中时是按照权值由小到 大顺序插入的。

4、2）首先判断当前集合节点的个数是否大于1，如果不大于，则程序结束，集合里的节点即为创建好的 哈夫曼树的根节点，如果大于 1，则转至 33）取出集合中前两个节点（取出后集合中已经删除掉这两个节点）,由这两个节点构建一颗新树，新树的 权值为这两个节点之和。权值较小的节点为新树的左孩子，较大的节点为新树的右孩子。4）将新树按权值由小到大的顺序插入到集合中，转至 2。实现代码如下:mytypes.h3 # ifndef#def me# def meMYTYPES HMVTVPES 丑typedef3structwe j.ghts ;char Ch；: huf fitian_t typedef stru

5、ct b itree t 3(huffman_t data;bitree tbitree tstructstruct*rchild-kiit.ree_t.;typeflef toitree t +datatyp已$typedef struct _node_t3(dat at yp e dat a:曰匸匚uct _node_t *next；node_t:typedef node t 1inklist 匸：#endifbitree.hndef#defineEITREE_H_ EITREE Hextern extern extern extarn extern extern#inc lude ,Fm

6、ytypes . hrt toitrEe_t *create_node(int data)ibitree t *crea七亡 comp bitreef int data); toitree_t *creat.e_fcitre亡()void praorder(toitree_t * Jo 1 tree) void inorder(b itree t *h itree;void postorder(fciitree_t *oitre亡)extern void print_toitree(toitree_t *oitree) endifbitree.c廣include# include# inclu

7、deSJ-stdio. lir chi Id = HlfLL kit-data = data;return tot;to itree _t eat.e_comp_bit.rEe( int. data H -bitree t *rt = create node(dat曰Fi( data*3 lch.ild = u匸亡ate _comp_tiitree( data* )；11 ( data* + ：1 r ch.i Id = create .coit?p bitree( data* 斗 )return root ；.bitree_t *create_tiitree()bitree t *rooti

8、nt lchild, 匚child;char data;if (sean( rr%d ;eGlehild tdata Srehild != 3return HULL,root. = (toituee_t *)malloc( siseufftoit.ree_r); root-data = data;roo七=4丄chi丄已=root-tchiId = HULLi(lchild =rootlchild = create bitree() if(rchild =roQtyfrchi Id = create bitree( Jreturn rootyoid pue口匚deu(tit匚巴巴_匸 * bi

9、ttee)iffbitree = ITULL)return:printf ( %d , loitree-：data)preorderf tiitree-lchild);preorder(b itree-rchildj;ret mm 二紘丿中序遍历void inorder (Jo it re e_t *bit.ree) lch.ild) ; pr in 七壬(d f bit ree-data; inorder( ittee-?-rchild);return;.Jjg序遇历void postorder(toitree t *bitree)_if(toitree = HULL) return:.po

10、storder( ittee-S-lchild); postorder(13itree-rchild) ; pr int ( rr d ri f b itre&-dat.a);return;void pr in七 bi七uee(hitree tit匕亡已)LinR:qi-iei-ie_t *linkqueue ;if(bitree = KULL)return;Uniqueue = create_l inJcqueue ();en linkqueue(linkgueue, to itree)J whiJ.e ( I empty linkqueue(linkqueuetoitree = de li

11、nkqueue( 1 inkqu.eu.e).;prxntf (嗨u ,f f bitree-da：if(bitree-lcliild != miHL)en_linkqueue ( 1 inicqueueto itre&-lehild) if (bi 七匕已已一 ArchJ.丄且 1= HULL en_linKqueue ( 1 inqueue s to ittes-r-rchild)pntchar ( LL ) jret m?rV：linklist.hRifndef _LINKLIST_H_ define LINKLIST_ H_ include rrniytypes. hrr创建头结点、乳

12、头结点的皿泣=NULL7兀返回头结点的肯地址extern linklist t *create linklis七f)；判断琏表是否为空extern int enipty_linkli5t iinkl ist _t +1 inlcl ist)插入到linklistT个元素extern int. irisert liiiklist. 1 ink 1 ist t + 1 ink 1 ist f datatype data; /Wlmklist的下一个元乗extern int delete_liiiklsit( iinkl ist t +1 inkl ist);?涓空依次释敞数据节点/7头站点.的口巳

13、x匸=NULLewtetrn int clear linklist Iinkl i3t t +1 inkl i3t)销毀I 清空2.釋放头结点.extern int display linklist Iinkl is七 七 * 1 inkl ist.;指定index进行插入曲怕extern int extetrn int extern int extern intinsert_lirLkli5t_irLdeD ( 1 inkl ist_t * 1 inkl ist delete linklist irides ( 1 inkl ist t +1 inkl ist, length linklist iinkl ist. t + 1 ink 1 ist.;print_linklist Iinkl ist_t * 1 int 1 ist);.datatype data int index):intind.亡x):endiflinklist.cinclude stdio.h：.j.nclude -include mytypeshI.创夢头站点./畑头络点的皿肚=NULL厂返回头站戌的首地址linlrlist t *ereate linfelist(1( - -