数据结构铜陵学院课件

1、1数据结构课程的内容1数据结构课程的内容2第6章 树和二叉树（ Tree & Binary Tree ）6.1 树的基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）2第6章 树和二叉树（ Tree & Binary Tr36.1 树的基本概念1. 树的定义2 若干术语3. 逻辑结构4.存储结构5. 树的运算36.1 树的基本概念1. 树的定义41. 树的定义注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。由一个或

2、多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树 。41. 树的定义注1：过去许多书籍中都定义树为n1，5树的表示法有几种：图形表示法嵌套集合表示法广义表表示法目录表示法左孩子右兄弟表示法这些表示法的示意图参见教材P120树的抽象数据类型定义参见教材P118-1195树的表示法有几种：图形表示法这些表示法的示意图参见教材P16图形表示法：教师学生其他人员2011级2012级2013级2014级铜陵学院会计学院数计学院金融学院叶子根子树6图形表示法：教师学生其他人

3、员2011级2012级2013级7广义表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边datalink 1link 2.link n麻烦问题：应当开设多少个链域?7广义表表示法( A ( B ( E ( K, L ), F8左孩子右兄弟表示法ABCDEFGHIJKLM数据左孩子 右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )8左孩子右兄弟表示法ABCDEFGHIJKLM数据左孩子 9 树的抽象数据类型

4、定义（见教材P118-119）ADT Tree数据对象D:数据关系R:基本操作 P：ADT Tree若D为空集，则称为空树；/允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明D是具有相同特性的数据元素的集合。/至少有15个9 树的抽象数据类型定义（见教材P118-119）ADT T102. 若干术语即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即该结点下层

5、子树中的任一结点ABCGEIDHFJMLK 根 叶子 森林有序树无序树即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。102. 若干术语即上层的那个结点(直接前驱)AB112. 若干术语（续）即树的数据元素结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）所有结点度中的最大值（M

6、ax各结点的度）指所有结点中最大的层数（Max各结点的层次）问：右上图中的结点数 ；树的度 ；树的深度1334112. 若干术语（续）即树的数据元素结点树的度A123. 树的逻辑结构 (特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。 4. 树的存储结构 讨论1：树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。 123. 树的逻辑结构 (特点)： 一对多（1:n），有多个13讨论3：树的链式存储方案应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论2：树的

7、顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。二叉树13讨论3：树的链式存储方案应该怎样制定？可规定为：从上至下145. 树的运算 要明确：1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！（遍历指每个结点都被访问且仅访

8、问一次，不遗漏不重复）。本章重点：二叉树的表示和实现145. 树的运算 要明确：本章重点：二叉树的表示和实现156.2 二叉树为何要重点研究每结点最多只有两个 “叉” 的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1. 二叉树的定义2. 二叉树的性质3. 二叉树的存储结构（二叉树的运算见6.3节）156.2 二叉树为何要重点研究每结点最多只有两个 “叉161. 二叉树的定义定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。逻辑结构： 一对二（1：2） 基本特征: 每个结点最多只有两棵子树（不存

9、在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。基本形态： 问：具有3个结点的二叉树可能有几种不同形态？普通树呢？ 5种/2种161. 二叉树的定义定义：是n（n0）个结点的有限集合，17二叉树的抽象数据类型定义（见教材P121-122）ADT BinaryTree数据对象D:数据关系R:基本操作 P：ADT BinaryTree若D=，则R= ；若D，则R= H；存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明 /关于左子树和右子树的说明D是具有相同特性的数据元素的集合。/至少有20个17二叉树的抽象数据类型定义（见教材P1

10、21-122）ADT182. 二叉树的性质 (3+2)讨论1：第i层的结点数至多是多少？ （利用二进制性质可轻松求出） 性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。性质2: 深度为k的二叉树至多有2k-1个结点（k0）。2i-1个提问：第i层上至少有 个结点？1讨论2：深度为k的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出）2k-1提问：深度为k时至少有 个结点？k182. 二叉树的性质 (3+2)讨论1：第i层的结点19讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2

11、+1）证明： 二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数)又二叉树中全部结点数nB+1 ( 总分支数根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支）而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个)三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1实际意义：叶子数2度结点数1ABCGEIDHFJ19讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？性质20对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：性质4: 具有n个结点的完全二叉树的深度必为log2n1性质5: 对完全二叉

12、树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）。 证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n2k-1 或2k-1n2k三边同时取对数，于是有：k-1log2n1)f=n*fact(n-1); else f=1; return(f); 33遍历的算法实现：用递归形式格外简单！回忆1：二叉树结点的34先序遍历算法DLR( liuyu *root )if (root !=

13、NULL) /非空二叉树 printf(“%d”,root-data); /访问DDLR(root-lchild); /递归遍历左子树DLR(root-rchild); /递归遍历右子树 return(0); 中序遍历算法LDR(x*root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);后序遍历算法LRD (x*root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data)

14、; return(0);结点数据类型自定义typedef struct liuyuint data; struct liuyu *lchild,*rchild； liuyu;liuyu *root; 34先序遍历算法中序遍历算法后序遍历算法结点数据类型自定义35对遍历的分析：1. 从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历2. 二叉树遍历的时间效

15、率和空间效率时间效率:O(n) /每个结点只访问一次空间效率:O(n) /栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）35对遍历的分析：1. 从前面的三种遍历算法可以知道：如果将36例：【严题集6.42】编写递归算法，计算二叉树中叶子结点的数目。 思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。 DLR(liuyu *root) /采用中序遍历的递归算法 if ( root!=NULL ) /非空二叉树条件，还可写成if(root) if(!root-lchild&!root-rchild) /是叶子结点则统计并打印

16、 sum+; printf(%dn,root-data); DLR(root-lchild); /递归遍历左子树，直到叶子处； DLR(root-rchild); /递归遍历右子树，直到叶子处； return(0); 36例：【严题集6.42】编写递归算法，计算二叉树中叶子结37注：要实现遍历运算必须先把二叉树存入机内。思路：利用前序遍历来建树 （结点值陆续从键盘输入，用DLR为宜）Bintree createBTpre( ) Bintree T; char ch;scanf(“%c”,&ch);if(ch=)T=NULL; elseT=( Bintree )malloc(sizeof(Bin

17、TNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre(); return T;怎样建树？见教材P131程序。37注：要实现遍历运算必须先把二叉树存入机内。思路：利用前序38习题讨论：1. 求二叉树深度，或从x结点开始的子树深度。 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。技巧：递归时应当从叶子开始向上计数，层深者保留。否则不易确定层数。 2. 按层次输出二叉树中所有结点。 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。

18、技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，由此便可产生按层次输出的效果。 A B CD E38习题讨论：1. 求二叉树深度，或从x结点开始的子树深度。393 中序遍历的非递归(迭代)算法算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。技巧:按层序遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入

19、队列.若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。393 中序遍历的非递归(迭代)算法算法思路：若不用递归，则40特别讨论：若已知先序/后序遍历结果和中序遍历结果，能否“恢复”出二叉树？【严题集6.31】 证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。 例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。分析：由后序遍历特征，根结点必在后序序列尾部（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（

20、即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。40特别讨论：若已知先序/后序遍历结果和中序遍历结果，能否“41中序遍历：B D C E A F H G后序遍历：D E C B H G F A（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF41中序遍历：B D C E A F H G后序遍历：D42问：用二叉链表法（l_child, r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说

21、明）。除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n1个结点的链域存放指针，指向非空子女结点（即直接后继）。思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。所以， 空指针数目2n(n-1)=n+1个。n+142问：用二叉链表法（l_child, r_child）存储43二、线索二叉树（Threaded Binary Tree）普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺

22、藤摸瓜”而遍历整个树了。两种解决方法：增加两个域：fwd和bwd；存放前驱指针存放后继指针如何预存这类信息？例如中序遍历结果：B D C E A F H G，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继。1. 定义 2. 生成 3. 遍历利用空链域（n+1个空链域）43二、线索二叉树（Threaded Binary Tree44规定：1）若结点有左子树，则lchild指向其左孩子； 否则， lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子； 否则， rchild指向其直接后继(即线索) 。为区别两种不同情况，特增加两个标志域（各1bit)lchi

23、lddatarchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况.右孩子或后继左孩子或前驱LTagRTag44规定：1）若结点有左子树，则lchild指向其左孩子；245附：有关线索二叉树的几个术语： 线索链表：用含Tag的结点样式所构成的二叉链表 线 索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树 线 索 化：对二叉树以某种次序遍历使其变为线索二叉树的过程讨论：增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用堆栈也能遍历整个树。45附：有关线索二叉树的几个术语： 线索链表：用含Tag46dataAGEIDJHCFBltag00111

24、10101rtag0001010111AGEIDJHCFB例：某先序遍历结果如下表所示，请画出对应的二叉树。（多带了两个标志！）46dataAGEIDJHCFBltag0011110101472. 线索二叉树的生成线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）472. 线索二叉树的生成线索化过程就是在遍历过程中修改空指48ABCGEIDHFroot悬空？悬空？解：该二叉树中序遍历结果为: H, D, I, B, E, A, F, C, G所以添加线索应当按如下路径进行：为避

25、免悬空态，应增设一个头结点例1：画出以下二叉树对应的中序线索二叉树。48ABCGEIDHFroot悬空？悬空？解：该二叉树中序遍4900A00C00B11E11F11G00D11I11H注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G0-root0对应的中序线索二叉树存储结构如图所示：4900A00C00B11E11F11G00D11I11H注50例2：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 2825405560330854解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，

26、即在原二叉树中添加虚线。NILNIL50例2：【 2000年计算机系考研题】给定如图所示二叉树T51线索二叉树的生成算法（算法6.6, 见教材P134）目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后 继。注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针当前结点之指针； pre指针前驱结点之指针。技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针p应当送到前驱结点的空右域中。若p-lchildNULL,则p-Ltag=1;p-lchildpre; /p的前驱结点指针pre存入左空域若pre-rchil

27、dNULL, 则pre-Rtag1;pre-rchild=p; /p存入其前驱结点pre的右空域51线索二叉树的生成算法（算法6.6, 见教材P134）目的523. 线索二叉树的遍历理论上，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空时结束。但是，在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，R_child=右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。以中序线索二叉树为例：对叶子结点（RTag=1），直接后继指针就在其rchild域内；对其他结点（RTag=0），直接后继是其右子树最左下的结点；（因为中序遍历规则是LDR，先左再根再右）5

28、23. 线索二叉树的遍历理论上，只要找到序列中的第一个结点53程序注解 (非递归，且不用栈）：P=T-lchild; /从头结点进入到根结点；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍历起点 if(!visit(p-data) return ERROR; /若起点值为空则出错告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后继标志，则直接提取p-rchild中线索并访问后继结点；p=p-rchild; /当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复 的全部过

29、程。Return OK;线索二叉树的中序遍历算法（算法6.5, 参见教材P134）LTag=0RTag=153程序注解 (非递归，且不用栈）：线索二叉树的中序遍历算54算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN演示程序54算法流程：return OK;p=T-lchild;p55提前介绍：二叉树的应用平衡树排序树字典树判定树带权树最优树特点：左右子树深度差 1特点：“左小右大”（见实验二的方

30、案1）由字符串构成的二叉树排序树例如，12个球只称3次分出轻重特点：路径长度带权值 带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。55提前介绍：二叉树的应用平衡树特点：左右子树深度差 566.4 树和森林1. 树和森林与二叉树的转换2. 树和森林的存储方式3. 树和森林的遍历566.4 树和森林1. 树和森林与二叉树的转换571. 树和森林与二叉树的转换转换步骤：step1: 将树中同一结点的兄弟相连;step2: 保留结点的最左孩子连线，删除其它孩子连线；step3: 将同一孩子的连线绕左孩子旋转45度角。加线抹线旋转讨论1：树如何转为二叉树？571. 树和森林与

31、二叉树的转换转换步骤：加线抹线旋转讨58方法：加线抹线旋转 abeidfhgc树转二叉树举例：abeidfhgc兄弟相连长兄为父孩子靠左根结点肯定没有右孩子！58方法：加线抹线旋转 abeidfhgc树转二叉树举例59讨论2：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！ abeidfhgc59讨论2：二叉树怎样还原为树？abeidfhgc要点：把所60法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。讨论3：森林如何转为二叉树？法二：森林直接变兄弟，再转为二叉树（参见教材P138图6.17，两种方法都有转换示意图）即F=T1, T2, ,Tm B=root

32、, LB, RB60法一：讨论3：森林如何转为二叉树？法二：森林直接变兄弟，61ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林转二叉树举例：（法二）兄弟相连 长兄为父孩子靠左 头根为根 A61ABCDEFGHJIABCDEFGHJIABCDEFGH62讨论4：二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B=root, LB, RB F=T1, T2, ,Tm62讨论4：二叉树如何还原为森林？要点：把最右边的子树变为森632. 树和森林的存储方式树有三种常用存储方式：双亲表示法 孩子表示法

33、 孩子兄弟表示法 1、用双亲表示法来存储思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。parentsdata结点结构dataparents1树结构 23n632. 树和森林的存储方式树有三种常用存储方式：1、用双亲64ABCGEIDHF缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例1: 双亲表示法64ABCGEIDHF缺点：求结点的孩子时需要遍历整个结构。65思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表）；再将n个表头用数组存放起来，这样就形成一个

34、混合结构。例如：abecdfhgdefghgfedcbah123456782、用孩子表示法来存储bc65思路：将每个结点的孩子排列起来，形成一个带表头（装父结点66思路：用二叉链表来表示树，但链表中的两个指针域含义不同。左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3、用孩子兄弟表示法来存储指向左孩子指向右兄弟66思路：用二叉链表来表示树，但链表中的两个指针域含义不同。67abecdfhgbacedfgh问：树转二叉树的“连线抹线旋转” 如何由计算机自动实现？答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是转换的过程！

35、例如：67abecdfhgbacedfgh问：树转二叉树的“连线68先序遍历若森林为空，返回；访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历若森林为空，返回；中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历ABCDEFGHJI68先序遍历森林的遍历ABCDEFGHJI69路 径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：霍 夫 曼 树：6.5 Huffman树及其应用一、最优二叉树（霍夫曼树）由一结点到另一结点间的分支所构成路径上的分支数目从

36、树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积预备知识：若干术语debacf g树中所有叶子结点的带权路径长度之和带权路径长度最小的树。ae的路径长度树长度21069路 径：6.5 Huffman树及其应用一、最优70Huffman树简介：树的带权路径长度如何计算？WPL = wklk k=1nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：WPL=36WPL=46WPL= 35哈夫曼树则是：WPL 最小的树。Huffman树Weighted Path Length70Huffman树简介：树的带权路径长度如何计算？WPL 71(1) 由给定的 n

37、 个权值w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林F = T0, T1, T2, , Tn-1 ，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F。构造霍夫曼树的基本思想：构造Huffman树的步骤（即Huffman算法）：权值大的结点用短路径，权值小的结点用长路径。先举例！71(1

38、) 由给定的 n 个权值w0, w1, w2, 72例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2, 4，怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码。例如用二进制编码来实现。 取 d=00，i=01，a=10，n=11怎样实现Huffman编码？法2：不等长编码，例如用哈夫曼编码来实现。 取 d=0; i=10, a=110, n=111最快的编码是哪个？是非等长的Huffman码！先要构造Huffman树！72例1：设有4个字符d,i,a,n，出现的频度分别为7,573操作要点1：对权值的合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权构

39、造Huffman树的步骤：注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。73操作要点1：对权值的合并、删除与替换构造Huffman树74操作要点2：按左0右1对Huffman树的所有分支编号！dain111000Huffman编码结果：d=0, i=10, a=110, n=111WPL=1bit72bit5+3bit(2+4)=35特点：每一码都不是另一码的前缀，绝不会错译! 称为前缀码将 Huffman树 与 Huffman编码 挂钩74操作要点2：按左0右1对Huffman树的所有分支编号！75例2（严题集6.26）：假设用于通信的电文仅由8个字母 a,

40、b, c, d, e, f, g, h 构成，它们在电文中出现的概率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，试为这8个字母设计哈夫曼编码。如果用07的二进制编码方案又如何？霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。解：先将概率放大100倍，以方便构造哈夫曼树。权值集合 w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。75例2（严题集6.26）：假设用于通信的电文仅由

41、8个字母76w4=19, 21, 28, 32为清晰起见，重新排序为:w=2, 3, 6, 7, 10, 19, 21, 322356w1=5, 6, 7, 10, 19, 21, 32w2=7, 10, 11, 19, 21, 32w3=11, 17, 19, 21, 32111071728211940w5=28,32,403260w6=40,60w7=100100bcadegfh哈夫曼树76w4=19, 21, 28, 32为清晰起见，重新排77对应的哈夫曼编码（左0右1）：23561110732172821194060100bcadegfh00000111111100符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 WPL3(0.19+0.32+0.21