数据结构第六章数和二叉树.ppt

1,数据结构课程的内容,2,第6章 树和二叉树（ Tree & Binary Tree ）,6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）,3,6.1 树的基本概念,1. 树的定义 2 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,4,1. 树的定义,注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即树中还有树。,由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树 。,5,树的表示法有几种：,图形表示法 嵌套集合表示法 广义表表示法 目录表示法 左孩子右兄弟表示法,这些表示法的示意图参见教材P120,树的抽象数据类型定义参见教材P118-119,6,图形表示法：,河南大学,叶子,根,子树,7,嵌套集合表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边,8,左孩子右兄弟表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ),9,树的抽象数据类型定义,ADT Tree 数据对象D: 数据关系R: 基本操作 P： ADT Tree,若D为空集，则称为空树；/允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 Hj Hk= 且Hi仍然是一棵树 /关于数据元素的说明,D是具有相同特性的数据元素的集合。,/至少有15个,10,2. 若干术语,即上层的那个结点(直接前驱) 即下层结点的子树的根(直接后继) 同一双亲下的同层结点（孩子之间互称兄弟） 即双亲位于同一层的结点（但并非同一双亲） 即从根到该结点所经分支的所有结点 即该结点下层子树中的任一结点,根 叶子 森林 有序树 无序树,即根结点(没有前驱) 即终端结点(没有后继) 指m棵不相交的树的集合(例如删除A后的子树个数),双亲 孩子 兄弟 堂兄弟 祖先 子孙,结点各子树从左至右有序，不能互换（左为第一） 结点各子树可互换位置。,11,2. 若干术语（续）,即树的数据元素 结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）,结点 结点的度 结点的层次 终端结点 分支结点,树的度 树的深度 (或高度),从根到该结点的层数（根结点算第一层） 即度为0的结点，即叶子 即度不为0的结点（也称为内部结点）,所有结点度中的最大值（Max各结点的度） 指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数 ；树的度 ；树的深度,13,3,4,12,3. 树的逻辑结构,(特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,4. 树的存储结构,讨论1：树是非线性结构，该怎样存储？ 仍然有顺序存储、链式存储等方式。,13,讨论3：树的链式存储方案应该怎样制定？,可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。,讨论2：树的顺序存储方案应该怎样制定？,可用多重链表：一个前趋指针，n个后继指针。 细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。,解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。,二叉树,14,5. 树的运算,要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！ （遍历指每个结点都被访问且仅访问一次，不遗漏不重复）。,本章重点：二叉树的表示和实现,15,6.2 二叉树,为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构,（二叉树的运算见6.3节）,16,1. 二叉树的定义,定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1：2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。 基本形态：,问：具有3个结点的二叉树可能有几种不同形态？普通树呢？,5种/2种,17,二叉树的抽象数据类型定义（见教材P121-122）,ADT BinaryTree 数据对象D: 数据关系R: 基本操作 P： ADT BinaryTree,若D=，则R= ； 若D，则R= H；存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明 /关于左子树和右子树的说明,D是具有相同特性的数据元素的集合。,/至少有20个,18,2. 二叉树的性质 (3+2),讨论1：第i层的结点数至多是多少？ （利用二进制性质可轻松求出）,性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。,性质2: 深度为k的二叉树至多有2k-1个结点（k0）。,2i-1个,提问：第i层上至少有 个结点？,1,讨论2：深度为k的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出）,2k-1,提问：深度为k时至少有 个结点？,k,19,讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？,性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+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度结点数1,20,满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）,完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。,为何要研究这两种特殊形式？ 因为它们在顺序存储方式下可以复原！,完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。 这其实是顺序二叉树的含义。在图论概念中的“完全二叉树”是指n1=0的情况。,21,对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：,性质4: 具有n个结点的完全二叉树的深度必为,性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）。,证明：当i=1时，由完全二叉树的定义，其左孩子是结点2，右孩子是结点3，成立。 当i1时，分两种情况，此时只证最简单的一种情况，即设第j层的第一个结点的编号为i，（由性质2知，前j-1层共有2j-1-1个结点，所以第j层的第一个结点的编号为2j-1，即i= 2j-1），则其左孩子必为第j+1层上的第一个结点，其编号为2j。(因为第j层上有2j-1个结点)，而2j=2(2j-1)=2i，所以，编号为i的结点的左孩子的编号为2i。,证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n2k-1 或2k-1n2k 三边同时取对数，于是有：k-1log2nk 因为k是整数，所以k=,22,3. 深度为9的二叉树中至少有( )个结点。 )9 )8 ) )91,2.深度为k 的二叉树的结点总数，最多为( )个。 )k-1 ) log2k ) k )k,课堂练习： 1. 树中各结点的度的最大值称为树的 。 ) 高度 ) 层次 ) 深度 ) 度,23,课堂讨论：,Q1：满二叉树和完全二叉树有什么区别？ A1：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。 满二叉树是完全二叉树的一个特例。,Q3: 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。,489,488,1,0,Q2：为什么要研究满二叉树和完全二叉树这两种特殊形式？ A2：因为只有这两种形式可以实现顺序存储！,由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。,A3：易求出总层数和末层叶子数。总层数k=log2n1 =10; 且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的) 所以末层叶子数为1000-511=489个。,24,请注意叶子结点总数末层叶子数！ 还应当加上第k-1层（靠右边）的0度结点个数。 分析：末层的489个叶子只占据了上层的245个结点（489/2 ) 上层（k=9)右边的0度结点数还有29-1-245=11个！,另一法：可先求2度结点数,再由此得到叶子总数。 首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉） 另外，末层叶子（刚才已求出为489）所对应的双亲也是度2， （共有489/2244个）。 所以，全部2度结点数为255(k-2层)244(k-1层)=499个； 总叶子数2度结点数1=500个。,第i层上的满结点数为2i-1,所以， 全部叶子数489(末层)11(k-1层)=500个。 度为2的结点叶子总数1=499个。,25,3. 二叉树的存储结构,一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,A B C D E F G H I,问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5） 例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,26,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,A B C D E,缺点：浪费空间；插入、删除不便,27,二、链式存储结构 用二叉链表即可方便表示。,二叉树结点数据类型定义： typedef struct node *tree_pointer; typedef struct node int data; tree_pointer left_child, right_child; node;,一般从根结点开始存储。 （相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,28,例：,29,6.3 遍历二叉树和线索二叉树,一、遍历二叉树（Traversing Binary Tree）,遍历定义指按某条搜索路线遍访每个结点且不重复（又称周游）。 遍历用途它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 遍历方法牢记一种约定，对每个结点的查看都是“先左后右” 。,30,遍历规则,二叉树由根、左子树、右子树构成，定义为D、 L、R D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先 (根)序遍历 中 (根)序遍历 后(根)序遍历 注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,31,例1：,先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是：,A B D E C D B E A C D E B C A,口诀： DLR先序遍历，即先根再左再右 LDR中序遍历，即先左再根再右 LRD后序遍历，即先左再右再根,32,先序遍历 + * * / A B C D E 前缀表达式 中序遍历 A / B * C * D + E 中缀表达式 后序遍历 A B / C * D * E + 后缀表达式 层序遍历 + * E * D / C A B,例2：用二叉树表示算术表达式,33,遍历的算法实现：,回忆1：二叉树结点的数据类型定义： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode,*BitTree;,34,1）先序遍历二叉树 算法思想: 若二叉树非空，则： 1）访问根结点 2）先序遍历左子树 3）先序遍历右子树,算法描述: void Preorder (BiTree bt) /bt为根结点指针 if( bt) /根非空 visit (bt-data)； Preorder (bt-lchild) ; Preorder (bt-rchild) ; ,二叉树的遍历,1）中序遍历二叉树 算法思想: 若二叉树非空，则： 1）中序遍历左子树 2）访问根结点 3）中序遍历右子树,算法描述: void Inorder (BiTree bt) /bt为根结点指针 if( bt) /根非空 Inorder (bt-lchild) ; visit (bt-data)； Inorder (bt-rchild) ; ,36,2）后序遍历二叉树 算法思想: 若二叉树非空，则： 1）后序遍历左子树 2）后序遍历右子树 3）访问根结点,算法描述: void Postorder (BiTree bt) /bt为根结点指针 if( bt) /根非空 Postorder (bt-lchild) ; Postorder (bt-rchild) ; visit (bt -data)； ,37,对遍历的分析：,1. 从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径 上，每个结点经过3次。,第1次经过时访问先序遍历 第2次经过时访问中序遍历 第3次经过时访问后序遍历,2. 二叉树遍历的时间效率和空间效率 时间效率:O(n) /每个结点只访问一次 空间效率:O(n) /栈占用的最大辅助空间 （精确值：树深为k的递归遍历需要k+1个辅助单元！）,38,注：要实现遍历运算必须先把二叉树存入机内。,思路：利用前序遍历来建树 （结点值陆续从键盘输入，用DLR为宜） Bintree createBTpre( ) Bintree T; char ch; scanf(“%c”,怎样建树？见教材P131程序。,39,知识回顾： （1）二叉树的存储： 顺序存储方式： 完全二叉树 满二叉树 一般树补充成的完全二叉树或满二叉树 链式存储方式：适用于各种树 （2）二叉树的遍历： 先序遍历、中序遍历、后序遍历、层序遍历,40,A,B,J,I,D,C,G,F,E,H,1、先序遍历的结果为：,2、中序遍历的结果为：,3、后序遍历的结果为：,A B D H E C F I G J,D H B E A F I C J G,H D E B I F J G C,特点：先访问根， 再遍历左子树， 再遍历右子树,特点：先遍历左子树， 再访问根， 再遍历右子树,特点： 先遍历左子树， 再遍历右子树 最后访问根，,41,（3）二叉树的生成,按先序遍历方式生成 注意：空节点的输入,42,例：编写递归算法，计算二叉树中叶子结点的数目。,思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。,DLR(BiTree *root) /采用中序遍历的递归算法 if ( root!=NULL ) /非空二叉树条件，还可写成if(root) if(!root-lchild ,43,习题讨论：,1. 求二叉树深度，或从x结点开始的子树深度。 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。,Height=max(hl,hr)+1,44,后序遍历求二叉树的高度递归算法： Int PostTreeDepth(BiTree bt) int hl,hr,max; if(bt!=NULL) hl=PostTreeDepth（bt-Lchild); /求左子树的深度 hr=PostTreeDepth(bt-Rchild); /求右子树的深度 max=hlhr?hl:hr; /*得到左、右子树深度较大者*/ return (max+1); /*返回树的深度*/ else return 0; ,45,2. 按层次输出二叉树中所有结点。 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。 技巧：当根结点出队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，由此便可产生按层次输出的效果。,Void Layout(BiTree root) EnQueue(s,root); While(!QueueEmpty(s) DeQueue(s,p); printf(“%c”,root-data); EnQueue(s,p-lchild); EnQueue(s,p-rchild); ,46,6.3.3 遍历的非递归(迭代)算法以中序遍历,算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。,在中序遍历中，我们是通过顺着左子树的根直走到最左端，然后访问最左端元素，遍历右，再返回上一层，访问结点，遍历右，然后再访问上一层，这样又顺着左子树的根回到A。 在递归调用中，返回上一层的操作是通过调用函数执行结束自然返回上一层的。如果不用递归，如何返回上一层。 先从A走到F，在从F返回到A，最后走到的先访问，所以可以用栈。 把根和左子树的根全部入栈 然后判断是否有右子树，如果有，则遍历右子树，,47,48,特别讨论：若已知先序/后序遍历结果和中序遍历结果，能否“恢复”出二叉树？,证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。,例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析： 由后序遍历特征，根结点必在后序序列尾部（即A）； 由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）； 继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。,49,中序遍历：B D C E A F H G 后序遍历：D E C B H G F A,（B D C E）,（ F H G）,A,B,F,（D C E）,（ H G）,C,D E,G,H,A,B,B,F,F,50,6.4 树和森林,1. 树和森林与二叉树的转换 2. 树和森林的存储方式 3. 树和森林的遍历,51,如何存储一棵树呢？,52,利用除根结点外每个结点只有唯一的双亲的性质，以一组连续的空间存储树的结点，同时在每个结点中附设一个指示域指示其双亲结点在存储空间中的位置。,6.4 树的存储结构 一、双亲表示法,#define MAX_TREE_SIZE 100 结点结构： Typedef struct PTNode Elem data; int parent; PTNode;,Data parent,Typedef struct PTNode nodesMAX_TRee_size; int r,n; ,53,6 .4 树的存储结构,6,H,6,G,3,F,1,E,1,D,0,C,0,B,0,A,-1,R,K,6,0 1 2 3 4 5 6 7 8 9,R=0 N=10,54,特点： 1）求结点的双亲操作可以在常量时间内实现； 2）求结点的孩子时需要遍历整个向量。,55,二、孩子表示法,孩子结点： Typedef struct CTNode int child; struct CTNode *next; *childPtr;,双亲结点: Typedef struct Elem data; childPtr firstchild; CTBox;,56,树结构： Typedef struct CTBox nodesMAX_TREE_SIZE; int n,r; Ctree;,57,F,E,B,C,A,D,G,R=0 N=7,0 1 2 3 4 5 6,A B C D E F G,1,2,3,4,5,6,-1,0,0,0,2,2,5,58,三、树的二叉链表 （孩子-兄弟）存储表示法 typedef struct CSNode Elem data; struct CSNode *firstchild,*nextsibling; CSNode,*CSTree;,59,F,E,B,C,A,D,G,60,1. 树和森林与二叉树的转换,转换步骤： step1: 将树中同一结点的兄弟相连; step2: 保留结点的最左孩子连线，删除其它孩子连线； step3: 将同一孩子的连线绕左孩子旋转45度角。,加线,抹线,旋转,讨论1：树如何转为二叉树？,61,方法：加线抹线旋转,树转二叉树举例：,兄弟相连,长兄为父,孩子靠左,根结点肯定没有右孩子！,62,讨论2：二叉树怎样还原为树？,要点：把所有右孩子变为兄弟！,63,法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。,讨论3：森林如何转为二叉树？,法二：森林直接变兄弟，再转为二叉树,（参见教材P138图6.17，两种方法都有转换示意图）,64,森林转二叉树举例：（法二）,兄弟相连 长兄为父 孩子靠左 头根为根,A,65,讨论4：二叉树如何还原为森林？,要点：把最右边的子树变为森林，其余右子树变为兄弟,66,树的遍历可有三条搜索路径： 先根序（次序）遍历 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 后根（次序）遍历 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 按层次遍历 若树不空，则自上而下自左至右访问树中每个结点。,67,先根遍历时顶点的访问次序： A B E F C D G H I J K 后根遍历时顶点的访问次序： E F B C I J K H G D A 层序遍历时顶点的访问次序： A B C D E F G H I J K,68,先序遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 若森林为空，返回； 中序遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 中序遍历除去第一棵树之后剩余的树构成的森林。,森林的遍历,69,A,B,C,D,E,F,G,H,K,I,L,J,70,路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： 霍 夫 曼 树：,6.5 Huffman树及其应用,一、最优二叉树（霍夫曼树）,由一结点到另一结点间的分支所构成,路径上的分支数目,从树根到每一结点的路径长度之和。,结点到根的路径长度与结点上权的乘积,预备知识：若干术语,树中所有叶子结点的带权路径长度之和,带权路径长度最小的树。,ae的路径长度,树长度,2,10,71,Huffman树简介：,树的带权路径长度如何计算？,经典之例：,WPL=36,WPL=46,WPL= 35,哈夫曼树则是：WPL 最小的树。,Huffman树,Weighted Path Length,72,(1) 由给定的 n 个权值w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林F = T0, T1, T2, , Tn-1 ，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F。,构造霍夫曼树的基本思想：,构造Huffman树的步骤（即Huffman算法）：,权值大的结点用短路径，权值小的结点用长路径。,先举例！,73,操作要点：对权值的合并、删除与替换 在权值集合7,5,2,4中，总是合并当前值最小的两个权,构造Huffman树的步骤：,注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。,6.2.2 赫夫曼编码,74,例2：设有4个字符d,i,a,n，出现的频度分别为7,5,2, 4，怎样编码才能使它们组成的报文在网络中传得最快？,法1：等长编码。例如用二进制编码来实现。 取 d=00，i=01，a=10，n=11,法2：不等长编码，例如用前缀编码来实现。 取 d=0; i=10, a=110, n=111,最快的编码是哪个？,是非等长的前缀编码！,任一个字符的编码都不是另一个字符编码的前缀,约定： 左分支表示0 右分支表示1 则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子的编码。,75,76,如何得到电文长度最短的二进制前缀编码？,若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。,d,i,a,n，出现的频度分别为7,5,2,4,假设每种字符在电文中出现的次数为wi,，其编码长度为Li,电文中只有n种字符，则电文总长度为,由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一颗赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。,对应到二叉树上，若置wi为叶子结点的权， Li恰为从根到叶子的路径长度。则： 恰为二叉树上带权路径长度。,77,操作要点：按左0右1对Huffman树的所有分支编号！,Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit72bit5+3bit(2+4)=35,特点：每一码都不是另一码的前缀，绝不会错译! 称为前缀码,将 Huffman树 与 Huffman编码 挂钩,78,例2（严题集6.26）：假设用于通信的电文仅由8个字母 a, 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， 按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。,79,w4=19, 21, 28, 32,为清晰起见，重新排序为: w=2, 3, 6, 7, 10, 19, 21, 32,5,6,w1=5, 6, 7, 10, 19, 21, 32,w2=7, 10, 11, 19, 21, 32,w3=11, 17, 19, 21, 32,11,17,28,w5=28,32,40,w6=40,60,w7=100,哈夫曼树,80,对应的哈夫曼编码（左0右1）：,H