树和二叉树(5哈夫曼树及其应用)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.6,哈夫曼树及其应用,1.,相关概念,路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。,如结点,A,到结点,F,的路径为：,A-B-E-F,A,B,C,D,E,F,G,6.6.1,最优二叉树,路径长度：路径上面的分支个数。,如,A-F,的路径长度为,3,。,A,B,C,D,E,F,G,树的路径长度：从树根到每一个结点的路径长度之和。,如左边树的路径长度为：,Len(A-B)+ Len(A-C)+ Len(A-D)+ Len(A-E)+ Len(A-F)+ Len(A-G),=1+1+2+2+3+3=12,A,B,C,D,E,F,G,结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。,如左图。,A,B,C,D,E,F,G,4,1,2,5,3,7,结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。,如结点,E,的带权路径长度为,:Len(E-A)*3=2*3=6,A,B,C,D,E,F,G,4,1,2,5,3,7,树的带权路径长度：,树中所有叶子结点的带权路径长度之和。,记作：,WPL=w1*L1+w2*L2+,wn,*,Ln,A,B,C,D,E,F,G,w1,w2,w3,w4,最优二叉树（哈夫曼树）：给定,n,个权值,w1,w2,wn,，,试构造一棵有,n,个叶子结点的二叉树，每个叶子结点带权为,wi,。,构造出来的二叉树的形态可以有多个，我们把其中带权路径长度,WPL,最小的二叉树称作最优二叉树或者哈夫曼树。,A,B,C,D,E,F,G,w1,w2,w3,w4,2.,哈夫曼算法,（,1,）,如何构造一棵哈夫曼树。,我们首先通过一个例子来演示一下构造过程。,当权值为,7,，,5,，,2,，,4,时，构造哈夫曼树。,7,5,2,4,当权值为,7,，,5,，,2,，,4,时，构造哈夫曼树。,7,5,2,4,6,当权值为,7,，,5,，,2,，,4,时，构造哈夫曼树。,7,2,4,6,5,当权值为,7,，,5,，,2,，,4,时，构造哈夫曼树。,7,2,4,6,5,11,当权值为,7,，,5,，,2,，,4,时，构造哈夫曼树。,7,2,4,6,5,11,当权值为,7,，,5,，,2,，,4,时，构造哈夫曼树。,7,2,4,6,5,11,18,（,2,）哈夫曼算法的语言描述,根据给定的,n,个权值,w1,w2,wn,构成,n,棵二叉树的集合,F=T1,T2,Tn,其中每棵二叉树,Ti,中只有一个带权为,wi,的根结点，其左右子树为空。,在,F,中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。,在,F,中删除这两棵树，同时将新得到的二叉树加入,F,中。,重复,和,，直到,F,只含一棵树为止。这棵树便是哈夫曼树。,6.6.2,哈夫曼编码,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别为,3,、,1,、,2,、,1,。,现在要对字符串进行,0,、,1,编码，有哪些方法？哪一种编码的长度最短？,1.,各种编码方式,（,1,）定长编码,-,根据出现的字符种数进行编码,字符串“,ABACCDA”,中共出现,4,种字符，那么可以用,2,位表示。,A,B,C,D,00,01,10,11,那么字符串“,ABACCDA”,的编码将为“,00010010101100”,，总长度为,7*2=14,位,1.,各种编码方式,（,1,）定长编码,-,根据出现的字符种数进行编码,这种编码方式可以对应到二叉树，如右图所式,A,B,C,D,00,01,10,11,A,B,C,D,0,0,0,1,1,1,1.,各种编码方式,（,2,）变长编码,当,A,、,B,、,C,、,D,按照如下形式进行编码时。,A,B,C,D,0,110,10,111,那么字符串“,ABACCDA”,的编码将为“,0110010101110”,，总长度为,13,位，比第二种方式又要短。,采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。,1.,各种编码方式,（,2,）变长编码,这种编码方式也可以对应到二叉树，如右图所式,A,B,C,D,0,110,10,111,A,B,C,0,0,1,1,D,0,1,1.,各种编码方式,（,2,）变长编码,如当,A,、,B,、,C,、,D,按照如下形式进行编码时。,A,B,C,D,0,11,01,111,请将,“,0111”,翻译成字符串。试一试，有哪些翻译方式。,之所以会出现二义性，是因为出现了,A,的编码是,C,的编码的前缀；,B,的编码是,D,的编码的前缀,.,1.,各种编码方式,（,2,）变长编码,这样,这些编码恢复成二叉树的形式时,不会形成,A,B,C,D,恰好为二叉树的叶子结点,如右图,A,B,C,D,0,11,01,111,A,C,B,0,1,1,1,D,1,1.,各种编码方式,从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。,也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。,1.,各种编码方式,（,3,）哈夫曼编码,假设编码过程中有以下对应关系：,字符,A,B,C,D,权重,（字符出现次数）,w1,w2,w3,w4,编码长度,L1,L2,L3,L4,那么总的编码长度为：,WPL=w1*L1+w2*L2+w3*L3+w4*L4,那么如何选择,L1,、,L2,、,L3,、,L4,的值，使得,WPL,最小呢？,1.,各种编码方式,（,3,）哈夫曼编码,可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别为,3,、,1,、,2,、,1,。根据权值,3,，,1,，,2,，,1,构造哈夫曼树,1,2,3,1,A,B,C,D,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别为,3,、,1,、,2,、,1,。根据权值,3,，,1,，,2,，,1,构造哈夫曼树,3,2,1,1,B,D,C,A,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别为,3,、,1,、,2,、,1,。根据权值,3,，,1,，,2,，,1,构造哈夫曼树,3,2,1,1,B,D,C,A,2,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别,为,3,、,1,、,2,、,1,。根据权值,3,，,1,，,2,，,1,构造哈夫曼树,3,2,1,1,B,D,C,A,2,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别为,3,、,1,、,2,、,1,。根据权,值,3,，,1,，,2,，,1,构造哈夫曼树,3,2,1,1,B,D,C,A,2,4,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别为,3,、,1,、,2,、,1,。根据权值,3,，,1,，,2,，,1,构造哈夫曼树,3,2,1,1,B,D,C,A,2,4,对于字符串“,ABACCDA”,，,共有,7,个字符，,4,种字符。其中,A,、,B,、,C,、,D,出现的次数分别为,3,、,1,、,2,、,1,。根据权值,3,，,1,，,2,，,1,构造哈夫曼树,3,2,1,1,B,D,C,A,2,4,7,下面对哈夫曼树进行编码，每一个结点的左分支上面,标,0,，右分支上面标,1,。,3,2,1,1,B,D,C,A,2,4,7,下面对哈夫曼树进行编码，每一个结点的左分支上面标,1,，右分支上面标,0,。,3,2,1,1,B,D,C,A,2,4,7,0,下面对哈夫曼树进行编码，每一个结点的左分支上面标,1,，右分支上面标,0,。,3,2,1,1,B,D,C,A,2,4,7,0,1,下面对哈夫曼树进行编码，每一个结点的左分支上面标,1,，右分支上面标,0,。,3,2,1,1,B,D,C,A,2,4,7,0,1,0,下面对哈夫曼树进行编码，每一个结点的左分支上面标,1,，右分支上面标,0,。,3,2,1,1,B,D,C,A,2,4,7,0,1,0,1,下面对哈夫曼树进行编码，每一个结点的左分支上面标,1,，右分支上面标,0,。,3,2,1,1,B,D,C,A,2,4,7,0,1,0,1,0,下面对哈夫曼树进行编码，每一个结点的左分支上面标,1,，右分支上面标,0,。,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,A：0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,A：0,B：1,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,A：0,B：11,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,A：0,B：110,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,A：0,B：110,C：1,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,A：0,B：110,C：10,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,A：0,B：110,C：10,D：1,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,A：0,B：110,C：10,D：11,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,从根结点到各个叶子结点，所经分支上面的,0,、,1,序列，就是该叶子结点所代表字符的编码。,A：1,B：110,C：10,D：111,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,思考,N,个权值构造的哈夫曼树，树中结点总数是多少？,哈夫曼树中，权值越大的结点越靠近根结点。该论断是否正确？,2.,哈夫曼编码的具体实现,输入字符及其权重,根据权重构造哈夫曼树,根据哈夫曼树编码,算法,6.12,的动态演示,（,1,）存储结构的选择,权值分别如下：,A,B,C,D,E,F,G,H,5,29,7,8,14,23,3,11,这八个权值作为叶子结点，最终形成的哈夫曼树应共有,2*8-1=15,个结点。采用双亲孩子表示法来存储哈夫曼树。,（,2,）初始化,weight,parent,lchild,rchild,1,5,0,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,0,0,0,8,11,0,0,0,9,-,0,0,0,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,(3),建树过程,weight,parent,lchild,rchild,1,5,0,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,0,0,0,8,11,0,0,0,9,-,0,0,0,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,第一步,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,0,0,0,8,11,0,0,0,9,-,0,0,0,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,-,0,0,0,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,0,0,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,0,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,0,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,第 二 步,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,0,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,-,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,15,0,0,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,15,0,3,0,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,15,0,3,4,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,0,0,0,9,8,0,1,7,10,15,0,3,4,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,第 三 步,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,0,1,7,10,15,0,3,4,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,0,3,4,11,-,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,0,3,4,11,19,0,0,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,0,3,4,11,19,0,8,0,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,0,3,4,11,19,0,8,9,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,0,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,0,3,4,11,19,0,8,9,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,第 四 步,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,0,3,4,11,19,0,8,9,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,0,8,9,12,-,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,0,8,9,12,29,0,0,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,0,8,9,12,29,0,5,0,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,0,8,9,12,29,0,5,10,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,0,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,0,8,9,12,29,0,5,10,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,第 五 步,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,0,8,9,12,29,0,5,10,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,0,5,10,13,-,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,0,5,10,13,42,0,0,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,0,5,10,13,42,0,6,0,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,0,5,10,13,42,0,6,11,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,0,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,0,5,10,13,42,0,6,11,14,-,0,0,0,15,-,0,0,0,第 六 步,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,0,5,10,13,42,0,6,11,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,0,6,11,14,-,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,0,6,11,14,58,0,0,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,0,6,11,14,58,0,2,0,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,0,6,11,14,58,0,2,12,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,0,6,11,14,58,0,2,12,15,-,0,0,0,第 七 步,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,15,6,11,14,58,0,2,12,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,15,6,11,14,58,15,2,12,15,-,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,15,6,11,14,58,15,2,12,15,100,0,0,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,15,6,11,14,58,15,2,12,15,100,0,13,0,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,15,6,11,14,58,15,2,12,15,100,0,13,14,（,4,）编码过程,从叶子结点开始，向根回溯，来对叶子结点所代表的字符进行编码。,weight,parent,lchild,rchild,1,5,9,0,0,2,29,14,0,0,3,7,10,0,0,4,8,10,0,0,5,14,12,0,0,6,23,13,0,0,7,3,9,0,0,8,11,11,0,0,9,8,11,1,7,10,15,12,3,4,11,19,13,8,9,12,29,14,5,10,13,42,15,6,11,14,58,15,2,12,15,100,0,13,14,以第一个叶子结点为例：,1,的双亲结点为,9,，且,1,是,9,的左孩子，故分支应该标“,0”,，所以编码“,0”,入栈。,以第一个叶子结点为例：,0,以第一个叶子结点为例：,9,的双亲结点为,11,，且,9,是,11,的右孩子，故分支应该标“,1”,，所以编码“,1”,入栈。,0,以第一个叶子结点为例：,0,1,以第一个叶子结点为例：,11,的双亲结点为,13,，且,11,是,13,的右孩子，故分支应该标“,1”,，所以编码“,1”,入栈。,0,1,以第一个叶子结点为例：,0,1,1,以第一个叶子结点为例：,13,的双亲结点为,15,，且,13,是,15,的左孩子，故分支应该标“,0”,，所以编码“,0”,入栈。,0,1,1,以第一个叶子结点为例：,0,1,1,0,以第一个叶子结点为例：,15,的双亲结点为,0,，所以可以判断,15,就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“,0110”,。,0,1,1,0,同理可以写出其他叶子结点的编码。,思考：,1.,写出字符串“,abbccccdddddddeee,”,的最短编码。,2.,当选择二叉链表来作为哈夫曼树的存储结构时，算法过程该如何描述。,