数据结构第6章2

1、6.6.1 树的存储树的存储6.6.2 树、森林与二叉树的转换树、森林与二叉树的转换6.6.3 树和森林的遍历树和森林的遍历6.6 6.6 树和森林树和森林6.6.1 6.6.1 树的存储树的存储树的主要存储方法有：树的主要存储方法有：一、双亲表示法一、双亲表示法二、孩子表示法二、孩子表示法三、孩子兄弟表示法三、孩子兄弟表示法一、一、 双亲表示法：双亲表示法： 用一组连续的空间来存储树中的结点，每个结点用一组连续的空间来存储树中的结点，每个结点附设一个指示器指示其双亲结点在表中的位置，其结附设一个指示器指示其双亲结点在表中的位置，其结点的结构如下：点的结构如下： 数据数据 双亲双亲DataPa

2、rent1245637树的双亲表示法如下图：树的双亲表示法如下图：1615140302-11ParentData543210结点结点序号序号673双亲表示法的优点：双亲表示法的优点： 利用了树中每个结点（根结点除外）利用了树中每个结点（根结点除外）只有一个双亲结点的性质，使得查找某只有一个双亲结点的性质，使得查找某个结点的双亲结点非常容易。个结点的双亲结点非常容易。 双亲表示法的缺点：双亲表示法的缺点： 求某个结点的孩子时，需要遍历整求某个结点的孩子时，需要遍历整个表。个表。 #define MAX 100typedef struct TNode DataType data; int pare

3、nt; TNode; 一棵树可以定义为：一棵树可以定义为：typedef struct TNode treeMAX; int root； int num; /*结点数结点数*/ PTree; 双亲表示法的结点结构定义：双亲表示法的结点结构定义：二、二、 孩子表示法：孩子表示法： 通常是把每个结点的孩子结点排列通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。起来，构成一个单链表，称为孩子链表。n n个结点共有个结点共有n n个孩子链表（叶结点的孩个孩子链表（叶结点的孩子链表为空表）。子链表为空表）。 n n个结点的数据和个结点的数据和n n个孩子链表的头个孩子链表的头指针又组成

4、一个顺序表。指针又组成一个顺序表。 树的孩子链表表示法见树的孩子链表表示法见p142的图的图6.21孩子表示法示意图孩子表示法示意图:ABCDEFG1 A 2 B 3 C 4 D 5 E 6 F 7 Groot=1num=7 data fch75 6 2 3 4 0111335par带双亲的孩子表示法带双亲的孩子表示法:孩子表示法的结构定义：孩子表示法的结构定义：typedef struct ChildNode /* 孩子链表结点的定义孩子链表结点的定义 */int Child; struct ChildNode * next; ChildNode; typedef struct /* 树的定

5、义树的定义 */ DataNode nodesMAX; /* 顺序表顺序表 */ int root； int num; /* 根结点指示及结点个数根结点指示及结点个数 */ CTree; CTree; typedef struct /* 顺序表结点的结构定义顺序表结点的结构定义 */DataType data; ChildNode * FirstChild ; DataNode;三、三、 孩子兄弟表示法孩子兄弟表示法 孩子兄弟表示法孩子兄弟表示法又称又称二叉链表表示法二叉链表表示法，表，表中每个结点设有两个链域，分别指向该结点的中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟

6、（右兄弟）结点。第一个孩子结点和下一个兄弟（右兄弟）结点。 fch data nsib第一孩子第一孩子 下一兄弟下一兄弟结点结构结点结构:孩子兄弟表示法的结点结构定义：孩子兄弟表示法的结点结构定义：typedef struct CSNode DataType data; Struct CSNode *FirstChild； Struct CSNode *NextSibling; CSNode, CSNode, * *CSTree;CSTree; 孩子兄弟表示法示意图：孩子兄弟表示法示意图：ABCDEFGroot AB C E D F G优点：优点：便于实现树的各种操作；便于实现树的各种操作；

7、可实现树可实现树( (森林森林) )与二叉树的相互转换。与二叉树的相互转换。ABCDEFGABCDEFG无兄弟无兄弟无右孩子无右孩子森林中森林中兄弟树兄弟树将转为将转为右子树右子树对应的关系：对应的关系： 树树 二叉树二叉树 根根 根根 第一孩子第一孩子 左孩子左孩子 下一兄弟下一兄弟 右孩子右孩子一、一、 树转换为二叉树树转换为二叉树 约定树中每一个结点的孩子结点按从左到约定树中每一个结点的孩子结点按从左到右的次序顺序编号，即把树看作为有序树。右的次序顺序编号，即把树看作为有序树。 6.6.2 6.6.2 树、森林与二叉树的转换树、森林与二叉树的转换将一棵树转换为二叉树的方法：将一棵树转换为

8、二叉树的方法： 加线：加线：树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。 删线：删线：对树中的每个结点，只保留其与第一对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点个孩子结点之间的连线，删去其与其它孩子结点之间的连线。之间的连线。 旋转调整旋转调整：以树的根结点为轴心，将整棵树：以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。顺时针旋转一定的角度，使之结构层次分明。 树转换为二叉树示意图树转换为二叉树示意图ABECDFGHABECDFGHABECDFGHABECDFGH森林转换为二叉树的方法为：森林转换为二叉树的方法为：（1

9、1）转换：）转换：将森林中的每棵树转换成相应的二叉树。将森林中的每棵树转换成相应的二叉树。（2 2）加线：）加线：将相邻的二叉树的根结点之间加线将相邻的二叉树的根结点之间加线（3 3）旋转调整：）旋转调整：以第一棵二叉树的根为轴心，以第一棵二叉树的根为轴心，将整个树顺时钟旋转到一定角度，使之层次结构将整个树顺时钟旋转到一定角度，使之层次结构清晰，左右子树分明。依次把后一棵二叉树调整清晰，左右子树分明。依次把后一棵二叉树调整为前一棵二叉树根节点的右孩子。为前一棵二叉树根节点的右孩子。二、森林转换为二叉树二、森林转换为二叉树森林转换为二叉树示意图森林转换为二叉树示意图 B E CH D I F J

10、 G B C D E F GH I J森林转换为二叉树的实例另见森林转换为二叉树的实例另见p145的图的图6.27二叉树转换为树或森林的方法为：二叉树转换为树或森林的方法为：（1 1）加线：）加线：若某结点是其双亲的左孩子，则若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、把该结点的右孩子、右孩子的右孩子、都与该结点的双亲结点用线连起来。都与该结点的双亲结点用线连起来。 （2 2）删线：）删线：删掉原二叉树中所有双亲结点与删掉原二叉树中所有双亲结点与右孩子结点的连线。右孩子结点的连线。 （3 3）旋转调整：）旋转调整：整理由（整理由（1 1）、（）、（2 2）两步所）两步所得到的

11、树或森林，使之结构层次分明。得到的树或森林，使之结构层次分明。 三、二叉树转换为树或森林三、二叉树转换为树或森林 二叉树转换为森林的示意图二叉树转换为森林的示意图DABCEFGHIJDABCEFGHIJHIJGDABCEF四、递归方法描述森林转换为二叉树四、递归方法描述森林转换为二叉树: : 将森林将森林F F看作树的有序集看作树的有序集F=TF=T1 1，T T2 2，,T,TN N ，它对应的二叉树为它对应的二叉树为B B（F F）：）： （1 1）若）若N N0 0，则，则B B（F F）为空。）为空。 （2 2）若）若N0N0，则：，则： 二叉树二叉树B B（F F）的根为森林中第一棵

12、树）的根为森林中第一棵树T T1 1的根；的根； B B（F F）的左子树为）的左子树为B B（TT1111，T T1m1m ），其），其中中TT1111，T T1m1m 是是T T1 1的子树森林；的子树森林； B B（F F）的右子树是）的右子树是B B（T2T2，T TN N ）。）。 若若B B是一棵二叉树，是一棵二叉树，T T是是B B的根结点，的根结点，L L是是B B的的左子树，左子树，R R为为B B的右子树，设的右子树，设B B对应的森林对应的森林F F（B B）中含有的中含有的n n棵树为棵树为T T1 1,T,T2 2, ,T, ,Tn n，则有：，则有： （1 1）B

13、B为空，则：为空，则：F F（B B）为空的森林（）为空的森林（n n0 0）。）。 （2 2）B B非空，则：非空，则： F F（B B）中第一棵树）中第一棵树T T1 1的根为二叉树的根为二叉树B B的根的根T T； T T1 1中根结点的子树森林由中根结点的子树森林由B B的左子树的左子树L L转换而转换而成，即成，即F F（L L）=T=T1111,T,T1m1m ； B B的右子树的右子树R R转换为转换为F F（B B）中其余树组成的森）中其余树组成的森林，即林，即F(R)F(R) T T2 2, T, T3 3, ,T, ,Tn n 。 五、用递归的方法描述其转换五、用递归的方法

14、描述其转换6.6.3 6.6.3 树和森林的遍历树和森林的遍历一、一、 树的遍历树的遍历树的遍历主要有以下两种：树的遍历主要有以下两种： 先根遍历先根遍历 后根遍历后根遍历1 1、先根遍历、先根遍历若树非空，则遍历过程为：若树非空，则遍历过程为：（1）访问根结点。）访问根结点。（2）从左到右，依次）从左到右，依次先根遍历根结点的每一棵子树。先根遍历根结点的每一棵子树。 ABECDFGH如图中树的先根遍历序列为：如图中树的先根遍历序列为：ABECFHGD。若树非空，则遍历过程为：若树非空，则遍历过程为：（1 1）从左到右，依次后根遍历根结点的每一）从左到右，依次后根遍历根结点的每一棵子树。棵子树

15、。（2 2）访问根结点。）访问根结点。ABECDFGH如图树的后根遍历序列为：如图树的后根遍历序列为： EBHFGCDA。2 2、后根遍历、后根遍历 A B E CH D I F J G A B C D E F GH I J树的后根遍历：树的后根遍历：H I J E B C F G D A树的先根遍历：树的先根遍历：A B E H I J C D F G对应二叉树的先序遍历对应二叉树的先序遍历 对应二叉树的中序遍历对应二叉树的中序遍历 二、树的遍历算法二、树的遍历算法 先根遍历方法一先根遍历方法一void RootFirst(CSTree root) if (root!=NULL) Visit

16、(root -data); /* 访问根结点访问根结点 */ p= root- FirstChild; while (p!=NULL) RootFirst( p ); /* 访问以访问以p为根的子树为根的子树 */ p = p - NextSibling; 先根遍历方法二先根遍历方法二 void RootFirst(CSTree root) if (root!=NULL) Visit (root -data); /*访问根结点访问根结点*/ RootFirst (root- FirstChild); /*先根遍历首子树先根遍历首子树*/ RootFirst (root- NextSibling

17、); /*先根遍历兄弟先根遍历兄弟树树*/ 三、森林的遍历三、森林的遍历森林的遍历方法主要有以下三种：森林的遍历方法主要有以下三种：先序遍历先序遍历 中序遍历中序遍历 * *后序遍历后序遍历1 1、先序遍历、先序遍历若森林非空，则遍历方法为：若森林非空，则遍历方法为：（1 1）访问森林中第一棵树的根结点。）访问森林中第一棵树的根结点。（2 2）先序遍历第一棵树的根结点的子树森林。）先序遍历第一棵树的根结点的子树森林。 （3 3）先序遍历除去第一棵树之后剩余的树构成）先序遍历除去第一棵树之后剩余的树构成的森林。的森林。 即：依次从左至右对森林中的每一棵树进即：依次从左至右对森林中的每一棵树进 行

18、行先根遍历先根遍历。若森林非空，则遍历方法为：若森林非空，则遍历方法为：（1 1）中序遍历森林中第一棵树的根结点的）中序遍历森林中第一棵树的根结点的 子树森林。子树森林。 （2 2）访问第一棵树的根结点。）访问第一棵树的根结点。 （3 3）中序遍历除去第一棵树之后剩余的树）中序遍历除去第一棵树之后剩余的树 构成的森林。构成的森林。 2 2、中序遍历、中序遍历即：依次从左至右对森林中的每一棵树进行即：依次从左至右对森林中的每一棵树进行 后根遍历后根遍历。 先序遍历先序遍历森林时顶点时顶点的访问次序：的访问次序：A B C D E F G H I J 中序遍历中序遍历森林时顶点时顶点的访问次序：的

19、访问次序：B C D A F E I H J G A E GB C D F H J I AB E C F G D H I J 树和森林的遍历和二叉树和森林的遍历和二叉树遍历的对应关系树遍历的对应关系 ？先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历3 3、森林的后序遍历、森林的后序遍历* *若森林非空，则遍历方法为：若森林非空，则遍历方法为：（1 1）后序遍历森林中第一棵树的根结点的子）后序遍历森林中第一棵树的根结点的子树森林。树森林。 （2 2）后序遍历除去第一棵树之后剩余的树构）后序遍历除去第一棵树之后剩余的树构成的

20、森林。成的森林。 （3 3）访问第一棵树的根结点。）访问第一棵树的根结点。 6.7 6.7 哈夫曼树及其应用哈夫曼树及其应用6.7.1 6.7.1 哈夫曼树哈夫曼树 哈夫曼树最典型、最广泛的应用是在哈夫曼树最典型、最广泛的应用是在编码技术上，利用哈夫曼树，可以得到编码技术上，利用哈夫曼树，可以得到平均长度最短的编码。这在通讯领域是平均长度最短的编码。这在通讯领域是极其有价值的。极其有价值的。 计算机程序操作码的优化也可以利用计算机程序操作码的优化也可以利用哈夫曼树实现。哈夫曼树实现。路径：路径：从一个结点到另一个结点之间的分支从一个结点到另一个结点之间的分支 序列。序列。路径长度：路径长度：从

21、一个结点到另一个结点所经过从一个结点到另一个结点所经过 的分支条数。的分支条数。树的路径长度：树的路径长度：树中每个结点与根之间的路径树中每个结点与根之间的路径 长度之和长度之和（PL）。a例：例：PL(a)=1+1+2+2+2+2=10 bPL(b)=1+1+2+2+3+3=12一、基本概念：一、基本概念：带权路径长度：带权路径长度：在树形结构中，我们把从树根在树形结构中，我们把从树根到某一结点的路径长度与该结点权的乘积，称到某一结点的路径长度与该结点权的乘积，称做该结点的带权路径长度。做该结点的带权路径长度。树的带权路径长度：树的带权路径长度：树中所有叶子结点的带权树中所有叶子结点的带权路

22、径长度之和，称为树的带权路径长度，通常路径长度之和，称为树的带权路径长度，通常记为记为WPL：WPL= wilii=1n其中：其中：n n为叶子结点的个数；为叶子结点的个数；w wi i为第为第i i个叶子的权值；个叶子的权值； l li i为第为第i i个叶子结点的路径长度。个叶子结点的路径长度。结点的权：结点的权：给树中每个结点赋予一个具有某种给树中每个结点赋予一个具有某种 实际意义的数值，我们称该数值为这个结点的权。实际意义的数值，我们称该数值为这个结点的权。例如下图所示的三棵二叉树例如下图所示的三棵二叉树WPL(a)=7252224236其带权路径长度分别为：其带权路径长度分别为：24

23、57a75 4b25 42c7WPL(b)=4273532146WPL(c)=7152234335 问题问题1 1：什么样的二叉树的路径长度什么样的二叉树的路径长度PLPL最小？最小？分析：分析：二叉树中路径长度为二叉树中路径长度为0 0的结点只有的结点只有1 1个；个； 路径长度路径长度 0 0 ，1 1，1 1，2 2，2 2，2 2，2 2，3 3，3 3，33，4 4，4 4，. .结点数结点数n n=1 n=2,3 n=4, 5 ,6 , 7 n=8. n=15 n=16可知：结点可知：结点n对应的路径长度为对应的路径长度为 log2n 路径长度为路径长度为1 1的结点至多只有的结点

24、至多只有2 2个；个；路径长度为路径长度为2 2的结点至多只有的结点至多只有4 4个；个；路径长度为路径长度为K K的结点至多只有的结点至多只有2 2k k个个; ; 所以所以n n个结点的二叉树其路径长度至少等于个结点的二叉树其路径长度至少等于如下序列的前如下序列的前n n项之和。项之和。nk=1 log2k 所以所以n个结点二叉树的个结点二叉树的PL至少为至少为前前n项之和项之和:因为深度为因为深度为h h的完全二叉树的路径长度为：的完全二叉树的路径长度为：200+21 1+22 2+ 2h h = hk=1 log2k 所以所以完全二叉树完全二叉树具有树的路径长度为最小具有树的路径长度为

25、最小的性质，但不具有唯一性。的性质，但不具有唯一性。例如：下列不同形状的二叉树均具有最小的路径长度例如：下列不同形状的二叉树均具有最小的路径长度ABCDEPL=0+1+1+2+2=6ABDCEPL=0+1+1+2+2=6ABCDEPL=0+1+1+2+2=6 故：故：深度为深度为h h的二叉树若前的二叉树若前h-1h-1层为满二叉树，层为满二叉树， 则则具有最小的路径长度。具有最小的路径长度。什么样的树的带权路径长度什么样的树的带权路径长度WPL最小？最小？ 例如：给定一个权值序列例如：给定一个权值序列2, 4, 5, 7，可构造，可构造多种二叉树的形态多种二叉树的形态:问题问题2 2：245

26、7a75 4b25 42c7 WPL(a) 36 WPL(b) 46 WPL(c)35 其带权路径长度分别为：其带权路径长度分别为： 在各种形态的含有在各种形态的含有 n个叶子结点的个叶子结点的 二二 叉树中叉树中, 必存在一棵必存在一棵(几棵几棵)其其带权路径长度带权路径长度值值WPL 最小最小的树，被称为的树，被称为“最优二叉最优二叉树树” 。 特征：特征：在最优二叉树中没有度数为在最优二叉树中没有度数为 1 的结的结点点(可用反证法证明可用反证法证明); 含含 n个叶子结点的最优二个叶子结点的最优二叉树的总结点数为叉树的总结点数为 2* *n- -1 (依据二叉树性质三依据二叉树性质三)

27、。 最优二叉树的构造方法最早由哈夫曼最优二叉树的构造方法最早由哈夫曼研究，所以又称为研究，所以又称为“哈夫曼树哈夫曼树”。二、哈夫曼树的构造二、哈夫曼树的构造 (1) 初始化：初始化：根据给定的根据给定的 n 个权值个权值 w1, w2, , wn ,构造构造 n 棵二叉树的集合棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值为其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树；的根结点，其左、右子树为空树；构造哈夫曼树的方法：构造哈夫曼树的方法： 找最小树并构造新树：在找最小树并构造新树：在 F 中选取其根结中选取其根结点的权值为最小的

28、两棵二叉树点的权值为最小的两棵二叉树, 分别作为左、分别作为左、右子树构造一棵新的二叉树右子树构造一棵新的二叉树, 并置这棵新的二并置这棵新的二叉树根结点的权值为其左、右子树根结点的叉树根结点的权值为其左、右子树根结点的权值之和；权值之和；(2)删除与插入：从删除与插入：从F中删去这两棵树中删去这两棵树,并加入刚并加入刚生成的新树；生成的新树； 重复重复 (2) 和和 (3) ,直至直至 F 中只含一棵树为止。中只含一棵树为止。(3)(4) 由此得到二叉树就是由此得到二叉树就是“最优二叉树最优二叉树” ” 即即“哈夫曼树哈夫曼树” ” 。 例如例如: : 已知权值已知权值 W= 5, 6, 2

29、, 9, 7 9562752769767139527构造哈夫曼树如下：构造哈夫曼树如下：952716671329三、哈夫曼算法的实现三、哈夫曼算法的实现 n个叶子结点个叶子结点的哈夫曼树共有的哈夫曼树共有2n-1个结点个结点,因此可用有因此可用有2n-1个元素的个元素的数组数组来存储哈夫曼树来存储哈夫曼树, 结点间的结点间的关系用游标表示关系用游标表示，即采用，即采用静态链表静态链表来来存储哈夫曼树。存储哈夫曼树。 1、存储结构、存储结构 每个结点需包含其双亲结点信息和孩子结每个结点需包含其双亲结点信息和孩子结点信息，所以构成一个静态三叉链表。点信息，所以构成一个静态三叉链表。 weight

30、parent Lchild Rchild 权值权值 双亲序号双亲序号 左孩子序号左孩子序号 右孩子序号右孩子序号 静态三叉链表结构定义静态三叉链表结构定义#define N 30#define M 2*N-1 typedef struct int weight ; int parent，Lchild，Rchild ; HTNode, HuffmanTreeM+1; /*0号单元不用号单元不用*/ 静态三叉链表静态三叉链表数组中数组中前前 n 个元素存储叶子结点，个元素存储叶子结点，后后n-1个元素存储分支结点即不断生成的新结点，个元素存储分支结点即不断生成的新结点，最后一个元素存储哈夫曼树的根

31、结点。最后一个元素存储哈夫曼树的根结点。 2、哈夫曼算法、哈夫曼算法 初始化：先将初始化：先将n个元素都视为根结点，个元素都视为根结点，即孩子和双亲指针全置即孩子和双亲指针全置0。 建哈夫曼树的过程是：反复在数组中建哈夫曼树的过程是：反复在数组中选双亲为选双亲为0(表示它们当前是树根表示它们当前是树根)且权值最且权值最小的两结点小的两结点, 将它们作为左右孩子挂在新将它们作为左右孩子挂在新的结点之下的结点之下, 新结点权值为左右孩子权值新结点权值为左右孩子权值之和。之和。 void CrtHuffmanTree(HuffmanTree ht , int w, int n) /* w存放已知的存

32、放已知的n个权值，构造哈夫曼树个权值，构造哈夫曼树ht */ m=2*n-1; for(i=1;i=n;i+) hti=wi,0,0,0; for(i=n+1;i=m;i+) hti=0,0,0,0;for(i=n+1;i=m;i+) select(ht,i-1,&s1,&s2); / /* *htht前前i-1i-1项选双亲为零且权最小的两结点项选双亲为零且权最小的两结点* */ / ht i.weight=hts1.weight+hts2.weight; hti.Lchild=s1;ht i.Rchild=s2; hts1.parent=i;hts2.parent=i; 例

33、给定权值例给定权值: 9,14 ,10 ,10, 12, 13, 9 ,11 i wt par Lch Rch1 5 0 0 02 29 0 0 03 7 0 0 04 8 0 0 05 14 0 0 06 23 0 0 07 3 0 0 08 11 0 0 09 0 0 0 010 0 0 0 011 0 0 0 012 0 0 0 013 0 0 0 014 0 0 0 015 0 0 0 08 0 1 79915 0 3 4101019 0 8 9111129 0 5 10121242 0 6 11131358 0 2 121414100 0 13 141515for(i=1;i=n;i

34、+) hti=wi,0,0,0;for(i=n+1;i=m;i+) hti=0,0,0,0;for(i=n+1;i=m;i+) select(ht,i-1,&s1,&s2); hts1.parent=i; hts2.parent=i; hti.Lchild=s1; hti.Rchild=s2; hti.weight=hts1.weight +hts2.weight; 哈夫曼树最典型的应用是在编码，利用哈哈夫曼树最典型的应用是在编码，利用哈夫曼树，可以得到平均长度最短的编码。夫曼树，可以得到平均长度最短的编码。6.7.2 6.7.2 哈夫曼编码哈夫曼编码 平均长度最短的编码一般为

35、不等长编码，平均长度最短的编码一般为不等长编码，为使各编码间无需加分界符即可识别，其编码为使各编码间无需加分界符即可识别，其编码应是应是前缀码。前缀码。前缀码：前缀码：同一字符集中任何一个字符的编码都同一字符集中任何一个字符的编码都不是另一个字符编码的前缀（最左子串）不是另一个字符编码的前缀（最左子串）。一、概念一、概念 利用哈夫曼树可以构造不等长的二进制编利用哈夫曼树可以构造不等长的二进制编码，并且构造所得的编码是一种码，并且构造所得的编码是一种最优前缀编码最优前缀编码，即可以使所传信息的总长度最短。即可以使所传信息的总长度最短。二、哈夫曼编码二、哈夫曼编码: : 对对哈夫曼树哈夫曼树中每个

36、左分支赋予中每个左分支赋予0 0，右分支，右分支赋予赋予1 1，则从根到每个叶子的路径上，各分支，则从根到每个叶子的路径上，各分支的值构成该叶子的的值构成该叶子的哈夫曼编码。哈夫曼编码。例：若要传输如下单词例：若要传输如下单词 state, seat, act, tea, cat, set, a, eat如何使所传送的信息编码长度最短？如何使所传送的信息编码长度最短？ 为保证信息编码长度最短，先统计各字为保证信息编码长度最短，先统计各字符出现的次数，然后以此作为权值符出现的次数，然后以此作为权值, , 构造哈构造哈夫曼树。夫曼树。723515851025000011110010010011编码

37、编码:左分支左分支:0右分支右分支:1；根到叶子路径上的值构根到叶子路径上的值构成叶子的编码。成叶子的编码。11需传输信息：需传输信息：state, seat, act, tea, cat, set, a, eat25783ceats各字符权值：各字符权值：010001011011ceats各字符编码：各字符编码： 构造哈夫曼树：构造哈夫曼树：结论一：结论一：哈夫曼编码是前缀码。哈夫曼编码是前缀码。结论二结论二: :哈夫曼编码是最优前缀码。哈夫曼编码是最优前缀码。 若若d di iddj j( (字符不同字符不同) )，则对应的树叶不同，则对应的树叶不同，因为从根到每个叶子的路径是不同的，所以

38、一因为从根到每个叶子的路径是不同的，所以一条路径不可能是另一条路径的前部（前缀），条路径不可能是另一条路径的前部（前缀），因此哈夫曼编码是前缀码。因此哈夫曼编码是前缀码。 用字符出现的频率用字符出现的频率( (Pi) )为权值构造哈夫曼为权值构造哈夫曼树树, ,并以此来构造字符的哈夫曼编码，由于哈并以此来构造字符的哈夫曼编码，由于哈夫曼树的夫曼树的WPLWPL最小：最小：所以传输的报文长度：所以传输的报文长度： 必定最小。必定最小。 WPL= wilii=1n报文长报文长= Pilii=1n三、哈夫曼编码应用举例三、哈夫曼编码应用举例例：例：设有一台模型机，共有设有一台模型机，共有7 7种不同

39、的指令，种不同的指令，各指令的使用频率各指令的使用频率Pi为：为：指指 令令I1I2I3I4I5I6I7 使用频率使用频率pi0.400.300.150.050.040.030.03 哈夫曼树最典型、最广泛的应用是在编码哈夫曼树最典型、最广泛的应用是在编码技术上，而操作码的优化也是其应用之一。技术上，而操作码的优化也是其应用之一。 以指令的使用频率为权值构造哈夫曼树，以指令的使用频率为权值构造哈夫曼树，并求各指令的哈夫曼编码。并求各指令的哈夫曼编码。则指令的平均码长为：则指令的平均码长为：pili =0.4*7+0.3*2+0.15*3+0.05*5+0.04*5 +0.03*5+0.03*5

40、 = 2.20ni=1若用等长编码，其平均码长为若用等长编码，其平均码长为3。 指令指令I1I2I3I4I5I6I7编码编码10100100011000100000100000各指令的哈夫曼编码为：各指令的哈夫曼编码为： 四、哈夫曼编码算法四、哈夫曼编码算法 利用哈夫曼树求编码时，编码是利用哈夫曼树求编码时，编码是由后向前生成的，需要走一条从叶子由后向前生成的，需要走一条从叶子到根的路径：到根的路径： 当前结点若是其双亲的左子树时，当前结点若是其双亲的左子树时，则置当前编码位为则置当前编码位为0，否则置为，否则置为1。 当由叶子走到根结点时，完成一当由叶子走到根结点时，完成一个叶子结点编码的求

41、取。个叶子结点编码的求取。 由哈夫曼树生成编码时由哈夫曼树生成编码时, 编码存储在多个字编码存储在多个字符数组中符数组中, 每个数组表示一个叶子结点的编码。每个数组表示一个叶子结点的编码。存储定义：存储定义：typedef char * Huffmancoden+1;char * cd;int start;例：例： 0 4 5 6 7 8 start cd: 0 1 1 0 0 4 hc 1 0 1 1 0 0 2 1 0 0 3 1 1 1 0 0 4 1 1 1 1 0 5 1 1 0 0 6 0 0 0 7 0 1 1 1 0 8 0 1 0 0 CrtHuffmanCode(Huffm

42、anTree ht,HuffmanCode hc,int n) /*从叶子到根，逆向求每个叶子对应的哈夫曼编码从叶子到根，逆向求每个叶子对应的哈夫曼编码*/ for(i=1;i=n;i+) /*求求每个每个叶子的哈夫曼编码叶子的哈夫曼编码*/ start=n-1; c=i ; p=hti.parent; while ( p!=0) -start; if(ht)p.Lchild = c) cdstart=0; /*左分支标左分支标0*/ else cdstart=1; /*右分支标右分支标1*/ c=p; p=htp.parent; hci=(char *)malloc(n-start)*sizeof(char); st