第12讲-哈夫曼树.ppt

5.4二叉树的应用一、Huffman树的定义路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数；树的路径长度：从树根到每一个结点的路径长度之和.树的带权路径长度步骤:根据给定的n个权值{w1,w2,……,wn}，构造n棵只有根结点的二叉树，令其权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树*哈夫曼树(Huffman)哈夫曼树编码几个与路径相关的定义1484642233设有n个权值{w1,w2,…,wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则wpl称为树的带权路径长度。例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35则wpl最小的二叉树叫Huffman树。设有n个权值{w1,w2,…,wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，Huffman树的定义例构造Huffman树a7b5c2d4a7b5c2d46a7b5c2d46114a7b5c2d61118二、构造Huffman树的方法Huffman算法例w={5,29,7,8,14,23,3,11}51429782331114297823115388715142923538111429238715538191129231487152953819112914871529234253819112914871529581002342538191129148715295823425381911三、Huffman算法实现Ch5_8.cHuffman树没有度为1的结点，一棵有n个叶子结点的Huffman树有2n-1个结点typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;采用顺序存储结构——一维结构数组结点类型定义lcdatarcpa12345670000000752400000000000000000(1)kx1=3,x2=4m1=2,m2=4lcdatarcpa12345670000300752460000004000055000(2)klcdatarcpa123456700003207524611000004500655600x1=2,x2=5m1=5,m2=6(3)lcdatarcpax1=1,x2=6m1=7,m2=111234567000032175246111800004567655670k(4)//构造huffman树#defineMAX100typedefstruct{intdata;intpa,lc,rc;}JD;voidhuffman(intn,intw[],JDt[]){inti,j,k,x1,x2,m1,m2;//初始化,置0for(i=1;i(2*n);i++){t[i].pa=t[i].lc=t[i].rc=0;if(i=n)t[i].data=w[i