数据结构课件第六章.pptx

1第6章 树和二叉树（Tree&Binary Tree）6.1 树的基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）第1页/共81页26.1 树的基本概念树的基本概念1.树的定义2 若干术语3.逻辑结构4.存储结构5.树的运算第2页/共81页31.树的定义树的定义注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。第3页/共81页4树的表示法有几种：图形表示法嵌套集合表示法广义表表示法目录表示法左孩子右兄弟表示法这些表示法的示意图参见教材P120树的抽象数据类型定义参见教材P118-119第4页/共81页5图形表示法：教师学生其他人员2003级 2004级 2005级2006级河南大学物理系计算机系化学系叶子根子树第5页/共81页6广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)根作为由子树森林组成的表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当开设多少个链域?第6页/共81页7左孩子右兄弟表示法A AB BC CD DE EF FG GH HI IJ JK KL LMM数据左孩子 右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)第7页/共81页8 树的抽象数据类型定义（见教材P118-119）ADT Tree数据对象D:数据关系R:基本操作 P：ADT Tree若D为空集，则称为空树；/允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：root 唯一 /关于根的说明 DjDk=/关于子树不相交的说明 /关于数据元素的说明D是具有相同特性的数据元素的集合。/至少有15个第8页/共81页92.若干术语若干术语即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根 叶子 森林有序树无序树即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。第9页/共81页102.若干术语（续）若干术语（续）即树的数据元素结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）问：右上图中的结点数 ；树的度 ；树的深度1334第10页/共81页113.树的逻辑结构树的逻辑结构(特点)：一对多（1:n1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。4.树的存储结构 讨论1：树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。第11页/共81页12讨论3：树的链式存储方案应该怎样制定？可规定为：可规定为：从上至下、从左至右从上至下、从左至右将树的结点依次存入内存。将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论2：树的顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。二叉树二叉树第12页/共81页135.树的运算树的运算 要明确：要明确：1.普普通通树树（即即多多叉叉树树）若若不不转转化化为为二二叉叉树树，则运算很难实现。则运算很难实现。2.二二叉叉树树的的运运算算仍仍然然是是插插入入、删删除除、修修改改、查查找找、排排序序等等，但但这这些些操操作作必必须须建建立立在在对对树树结点能够结点能够“遍历遍历”的基础上！的基础上！（遍遍历历指指每每个个结结点点都都被被访访问问且且仅仅访访问问一一次次，不遗漏不重复）。不遗漏不重复）。本章重点：二叉树的表示和实现第13页/共81页146.2 6.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “叉叉”的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一可以证明，所有树都能转为唯一对应的二叉树，不失一般性。般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构（二叉树的运算见6.3节）第14页/共81页151.1.1.1.二叉树的定义二叉树的定义二叉树的定义二叉树的定义定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1：2）基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒（有序树）。基本形态：问：具有问：具有3 3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？5种/2种第15页/共81页16二叉树的抽象数据类型定义二叉树的抽象数据类型定义（见教材（见教材P P121-121-122122）ADT BinaryTree数据对象D:数据关系R:基本操作 P：ADT BinaryTree若D=，则R=；若D，则R=H；存在二元关系：root 唯一 /关于根的说明 DjDk=/关于子树不相交的说明 /关于数据元素的说明 /关于左子树和右子树的说明D是具有相同特性的数据元素的集合。/至少有20个第16页/共81页172.2.2.2.二叉树的性质二叉树的性质二叉树的性质二叉树的性质 (3+2)(3+2)(3+2)(3+2)讨论1：第i层的结点数至多是多少？（利用二进制性质可轻松求出）性质1:在二叉树的第i层上至多有2 2i-1i-1个结点（i0）。性质2:深度为k的二叉树至多有2 2k k-1-1个结点（k0）。2i-1个提问：第i层上至少有 个结点？1讨论2：深度为k的二叉树，至多有多少个结点？（利用二进制性质可轻松求出）2k-1提问：深度为k时至少有 个结点？k第17页/共81页18讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 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度结点数1ABCGEIDHFJ第18页/共81页19满二叉树：满二叉树：一棵深度为一棵深度为k 且有且有2k-1个结点的二叉个结点的二叉树。树。（特点：每层都（特点：每层都“充满充满”了结点）了结点）完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树深度为4的完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原！完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。这其实是顺序顺序二叉树二叉树的含义。在图论概图论概念中念中的“完全二叉树”是指n1=0的情况。第19页/共81页20对于两种特殊形式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树），还特别具备以下），还特别具备以下2 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-1log2n1)f=n*fact(n-1);else f=1;return(f);第32页/共81页33先序遍历算法DLR(liuyu*root)if(root!=NULL)/非非空空二二叉叉树树 printf(“%d”,root-data);/访问访问D 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);return(0);结点数据类型自定义typedef struct liuyuint data;struct liuyu*lchild,*rchild；liuyu;liuyu*root;第33页/共81页34对遍历的分析：1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)O(n)/每个结点只访问一次空间效率:O(n)O(n)/栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）第34页/共81页35例：例：编写递归算法，计算二叉树中叶子结点的数目。思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。DLR(liuyu*root)/采用中序遍历的递归算法 if(root!=NULL)/非空二叉树条件，还可写成if(root)if(!root-lchild&!root-rchild)/是叶子结点则统计并打印 sum+;printf(%dn,root-data);DLR(root-lchild);/递归遍历左子树，直到叶子处；DLR(root-rchild);/递归遍历右子树，直到叶子处；return(0);第35页/共81页36注：要实现遍历运算必须先把二叉树存入机内。思路：利用前序遍历来建树（结点值陆续从键盘输入，用DLR为宜）Bintree createBTpre()Bintree T;char ch;scanf(“%c”,&ch);if(ch=)T=NULL;elseT=(Bintree)malloc(sizeof(BinTNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre();return T;怎样建树？见教材P131程序。第36页/共81页37习题讨论：1.1.求二叉树深度，或从求二叉树深度，或从x x结点开始的子树深度。结点开始的子树深度。算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。左子树右子树根hlhrHeight=max(hr,hr)+1AFEDCBG第37页/共81页38后序遍历求二叉树的高度递归算法：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;第38页/共81页392.2.按层次输出二叉树中所有结点。按层次输出二叉树中所有结点。算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，由此便可产生按层次输出的效果。ADFCGEHBVoid Layout(BiTree root)EnQueue(s,root);While(!QueueEmpty(s)DeQueue(s,p);printf(“%c”,root-data);EnQueue(s,p-lchild);EnQueue(s,p-rchild);第39页/共81页40遍历的非递归遍历的非递归遍历的非递归遍历的非递归(迭代迭代迭代迭代)算法算法算法算法以中序遍历以中序遍历以中序遍历以中序遍历算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。在中序遍历中，我们是通过顺着左子树的根直走到最左端，然后访问最左端元素，遍历右，再返回上一层，访问结点，遍历右，然后再访问上一层，这样又顺着左子树的根回到A。在递归调用中，返回上一层的操作是通过调用函数执行结束自然返回上一层的。如果不用递归，如何返回上一层。先从A走到F，在从F返回到A，最后走到的先访问，所以可以用栈。把根和左子树的根全部入栈然后判断是否有右子树，如果有，则遍历右子树，HIAFEDCBG第40页/共81页41特别讨论：特别讨论：若已知先序若已知先序/后序遍历结果和中序后序遍历结果和中序遍历结果，能否遍历结果，能否“恢复恢复”出二叉树？出二叉树？证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。分析：由后序遍历特征，根结点必在后序序列尾部（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。第41页/共81页42中序遍历：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 EGHABBFF第42页/共81页436.4 6.4 树和森林树和森林1.树和森林与二叉树的转换2.树和森林的存储方式3.树和森林的遍历第43页/共81页4412345879618第44页/共81页45 利用除根结点外每个结点只有唯一的双亲的性质，以一组连续的空间存储树的结点，同时在每个结点中附设一个指示域指示其双亲结点在存储空间中的位置。6.4 树的存储结构一、双亲表示法#define MAX_TREE_SIZE 100结点结构：Typedef struct PTNode Elem data;int parent;PTNode;Data parentTypedef struct PTNode nodesMAX_TRee_size;int r,n;第45页/共81页466.4 树的存储结构EDABRCFGHk6H6G3F1E1D0C0B0A-1RK60123456789R=0N=10第46页/共81页47特点：1）求结点的双亲操作可以在常量时间内实现；2）求结点的孩子时需要遍历整个向量。第47页/共81页48二、孩子表示法孩子结点：Typedef struct CTNode int child;struct CTNode*next;*childPtr;双亲结点:Typedef struct Elem data;childPtr firstchild;CTBox;第48页/共81页49树结构：Typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;Ctree;第49页/共81页50FEBCADGR=0N=70123456ABCDEFG123456 -1000225 第50页/共81页51三、树的二叉链表 （孩子-兄弟）存储表示法 typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;第51页/共81页52FEBCADGABCEDFG ABCEDFG第52页/共81页531.树和森林与二叉树的转换转换步骤：step1:将树中同一结点的兄弟相连;step2:保留结点的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子旋转45度角。加线抹线旋转讨论1：树如何转为二叉树？第53页/共81页54方法：加线抹线旋转 abeidfhgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连长兄为父孩子靠左根结点肯定没根结点肯定没有右孩子！有右孩子！第54页/共81页55讨论讨论2 2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！abeidfhgc第55页/共81页56法一：各森林先各自转为二叉树；依次连到前一个二叉树的右子树上。讨论3：森林如何转为二叉树？法二：森林直接变兄弟，再转为二叉树（参见教材P138图6.17，两种方法都有转换示意图）即F=T1,T2,Tm B=root,LB,RB第56页/共81页57ABCDEFGHJIABCDEFGHJIA ABCDEFGHJI森林转二叉树举例：森林转二叉树举例：（法二）（法二）兄弟相连 长兄为父孩子靠左 头根为根 A A第57页/共81页58讨论讨论4 4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B=root,LB,RB F=T1,T2,Tm第58页/共81页59树的遍历可有三条搜索路径：先根序（次序）遍历 若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根（次序）遍历 若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历 若树不空，则自上而下自左至右访问树中每个结点。第59页/共81页60CFEBADGHIJK先根遍历时顶点的访问次序：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第60页/共81页61先序遍历F若森林为空，返回；F访问森林中第一棵树的根结点；F先序遍历第一棵树中根结点的子树森林；F先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历F若森林为空，返回；F中序遍历森林中第一棵树的根结点的子树森林；F访问第一棵树的根结点；F中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历ABCDEFGHJI第61页/共81页62ABCDEFGHKIABCDEFGLJ第62页/共81页63路 径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：霍 夫 曼 树：6.5 Huffman6.5 Huffman树及其应用树及其应用一、最优二叉树（霍夫曼树）由一结点到另一结点间的分支所构成路径上的分支数目从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积预备知识：若干术语debacf g树中所有叶子结点的带权路径长度之和带权路径长度最小的树。ae的路径长度树长度210第63页/共81页64HuffmanHuffman树简介：树简介：树的带权路径长度如何计算？WPL=wklk k=1nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：经典之例：WPL=36WPL=46WPL=35哈夫曼树则是：WPL 最小的树。Huffman树Weighted Path Length第64页/共81页65(1)(1)由给定的由给定的 n n 个权值个权值 w w0 0,w w1 1,w w2 2,w wn n-1-1，构造具有，构造具有 n n 棵扩充二棵扩充二叉树的叉树的森林森林F F=T T0 0,T T1 1,T T2 2,T Tn n-1-1 ，其中每一棵扩充二叉树，其中每一棵扩充二叉树 T Ti i 只有一个带有权值只有一个带有权值 w wi i 的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。(2)(2)重复以下步骤重复以下步骤,直到直到 F F 中仅剩下一棵树为止：中仅剩下一棵树为止：在在 F F 中中选取两棵根结点的权值最小选取两棵根结点的权值最小的扩充二叉树的扩充二叉树,做为左、做为左、右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为根结点的权值为其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和。在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树加入 F F。构造霍夫曼树的基本思想：构造霍夫曼树的基本思想：构造Huffman树的步骤（即Huffman算法）：权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径。先举例！第65页/共81页66操作要点：对权值的合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权构造构造HuffmanHuffman树的步骤：树的步骤：注：方框表示外结点（叶子，字符对应的权值），圆框表示内结点（合并后的权值）。赫夫曼编码第66页/共81页67例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=111adin000111用二叉树来设计前缀编码最快的编码是哪个？是非等长的前缀编码！任一个字符的编码都不是另一个字符编码的前缀约定：左分支表示0右分支表示1则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子的编码。第67页/共81页68ACBDEKFGHIJ第68页/共81页69如何得到电文长度最短的二进制前缀编码？若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。d,i,a,n，出现的频度分别为7,5,2,4 假设每种字符在电文中出现的次数为wi,，其编码长度为Li,电文中只有n种字符，则电文总长度为=niiLiW1=niiLiW1 由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一颗赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。对应到二叉树上，若置wi为叶子结点的权，Li恰为从根到叶子的路径长度。则：恰为二叉树上带权路径长度。第69页/共81页70操作要点：操作要点：按左按左0 0右右1 1对对HuffmanHuffman树的所有分支编号！树的所有分支编号！dain111000Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit72bit5+3bit(2+4)=35特点：每一码都不是另一码的前缀，绝不会错译!称为前缀码将将 Huffman树 与 Huffman编码 挂钩第70页/共81页71例2 2（严题集6.266.26）：假设用于通信的电文仅由假设用于通信的电文仅由8 8个字个字母母 a,b,c,d,e,f,g,ha,b,c,d,e,f,g,h 构成，它们在电文中出构成，它们在电文中出现的概率分别为现的概率分别为 0.07,0.19,0.02,0.06,0.32,0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.100.03,0.21,0.10，试为这，试为这8 8个字母设计哈夫曼个字母设计哈夫曼编码。编码。如果用如果用0 07 7的二进制编码方案又如何？的二进制编码方案又如何？霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。解：先将概率放大100倍，以方便构造哈夫曼树。权值集合 w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。第71页/共81页72w4=19,21,28,32为清晰起见，重新排序为为清晰起见，重新排序为:w=2,3,6,7,10,19,21,32w=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哈夫曼树 第72页/共81页73对应的哈夫曼编码（左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 11001100000011110111101110111010101111111111010111011101000001010011100101110111第73页/共81页74另一种结果表示：第74页/共81页75Void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)if(n=1)return;n个权值构造一颗赫夫曼树需要的结点个数是：2n-1这 2n-1 个结点的存储方式：链式，顺序AWPLR1234567mAw000Bw000Cw000Dw000Ew000Fw0001234567m000000000000HT=（HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT,i=1;i=n；+i,+p,+w)*p=*w,0,0,0;for(;i=m;+i,+p)*p=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;AW=8BW=3CW=9DW=5EW=10FW=4第75页/共81页76800030009000500010000400012345678970001200017 0003W:3 4 5 8 9 10W:5 7 8 9 1047512W:8 9 10 129817W:10 12 171022W:17 223922 000W:3910778899264713111010581139 000910第76页/共81页7780030090050010004001234567897121734751298171022392210778899264713111010581139 0910W:3 4 5 8 9 10W:5 7 8 9 10W:8 9 10 12W:10 12 17W:17 22W:3911第77页/共81页7880030090050010004001234567897121734751298171022392210778899264713111010581139 091011第78页/共81页79例例3 3（实验二方案（实验二方案3 3）：设字符集为设字符集为2626个英文字母，其个英文字母，其出现频度如下表所示。出现频度如下表所示。51481156357203251频度zyxwvut t字符11611882380频度p21fq15gr47hsonmlkj字符5710332221364186频度ie edcba空格空格字符先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。要求编程实现：第79页/共81页80二叉树小结二叉树小结1、定义和性质2、存储结构3、遍历4、线索化：线索树顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树森林中序遍历后序遍历先序遍历霍夫曼树霍夫曼编码第80页/共81页81感谢您的观看！第81页/共81页