安阳一中oi7月24日夫曼树

1、树一、树的含义：树是一种带权路径长度最短的树。所谓路径长度就是某个端结点到树的根结点的距离，等于该端结点的祖先数，或该结点所在层数减 1，用 lk 表示。二叉树中每个端结点对应的一个实数称为该结点的权，用Wk 表示。定义各端结点的权Wk 与相应的路径长度lk 乘积的代数和为该二叉树的带权路径长度，用 WPL 表示，即：可以证明，树是最优二叉树。如给定权值5，4，7，2，3，可以生成很多棵二叉树，其中的（A（B（7，5），C（4，D（3，2）是树。注意： 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。 最优二叉树中，大的叶子离根越近。 最优二叉树的形态不唯一

2、，WPL 最小二、树的构造算法：1、（1）根据给定的n 个权值W1，W2，Wnn 棵二叉树的森林：FT1，T2，Tn。其中每棵二叉树Ti 只有一个带权为Wi 的根结点，其左右为空。（2）在F 中选取两棵结点的权值最小的树作为左右一棵新的二叉树，且置新的二叉树的根结点的权值为其左右上根结点的权值之和。在F 中删除这两棵树，同时，将新得到的二叉树加入F 中。重复（2）、（3），直到F 只含一棵树为止。最后的这棵树便是曼树。思考题 1：假如权值为5，4，7，2，5，试据此画出构造树的过程。2、算法描述为了上述算法，选用数组型的链表作为结构，其类型设计如下：Type tnode=RECORD weig

3、ht：real；Lc，Rc： END；eger；tree=ARRAY1.2*n-1 of tnode; node=RECORDweight：real；adr： END；eger；A=ARRAY1.n of node;下面是在这个结构上实现的构造树的算法：Procedure Huffmantree（VAR W：ARRAY1.nOF real;VAR TR:tree）；VAR AT:A; BENGINFOR i:=1 TO n DO实现第(1)步BEGINTRi.weight:=Wi;将权值放在树叶中 TRi.Lc：=0；TRi.Rc：=0；ATi.weight:=TRi.weight;用 AT

4、存放当前森林的根 ATi.adr:=i;END;num:=n;森林中结点个数K:=num+1;形成的新结点在TR 数组中的位置 WHILE (num=2) DO 重复实现第(2)、(3)步 BEGINSORTING(AT,num);按根值大小对森林中的树进行升序排列TRk.weight:=AT1.weigh2.weight;选择两棵结点权值最小的树构造新二叉树 TRk.Lc:=AT1.adr; 树：权值最小的树TRk.Rc:=AT2.adr; 右：权值次小的树AT1.weight:=TRk.weight; 新树赋予第一AT1.adr:=k;新树结点标号AT2.weight:=ATnum.wei

5、ght;原最后树赋予第二AT2.adr:=ATnum.adr;跟进结点标号num:=num-1; k:=k+1;END; END;删除原最后树增加结点标号思考题 2：假如以权值5，4，7，2，5执行上述算法，试写出构造树时其结构的变化情况。三、应用：编码利用树构造的用于通信的二进制编码，称为编码。在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经编码后得到的编码，其长度是因符号出现的概率而不同，所以说编码是变长的编码。）例一段电文CASTA SA，统计电文中字母的频度，f(C)=1,f(S)=2,f(T)=3,f( )=3,f(A)=4，可用其频度1，2，3，3，4为权值生成 Huffman 树，并在每个叶子上注明对应的字符。树中从根到每个叶子都有一条路径，若对路径上的各分支进行约定，指向树根的分支用“0”码表