《数据结构789树》PPT课件

数据结构DataStructure彭宏京南京工业大学计算机科学系2007年9月,学时数：48(32+16）学分：3教材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月（配题集）参考书：1殷人昆等，数据结构（用面向对象方法与C+描述），清华大学出版社，1999年7月。￥262殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。￥263李春葆，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。￥284丁宝康等，数据结构自学考试指导，清华大学出版社，2001年5月。￥23,内容安排,实验：课内上机（16规定内容）+课外上机（24平时作业中编程题验证）,数据结构课程的内容,各种数据结构的应用,1、树的定义和基本术语2、二叉树3、遍历二叉树和线索二叉树4、树和森林5、树和等价问题6、赫夫曼树及其与树的应用7、回溯法与树的遍历8、树的计数,目录,第六章树和二叉树特点：非线性结构，一个直接前驱，但可能有多个直接后继。（一对多或1:n）,1、树的定义和基本术语,（1）.树的定义,注：树的定义具有递归性，即“树中还有树”。,由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。,（1）.树的定义（2）.若干术语,（3）.逻辑结构（4）.存储结构（5）.树的运算,树的表示法主要有5种：,图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子右兄弟表示法,1、树的定义和基本术语,自学,图形表示法：,南工大信息学院,叶子,根,子树,左孩子右兄弟表示法,（2）.若干术语,即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即以某结点为根的子树中的任一结点,根叶子森林有序树无序树,即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数),双亲孩子兄弟堂兄弟祖先子孙,结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。,（2）.若干术语（续）,即树的数据元素结点挂接的子树数,结点结点的度结点的层次终端结点分支结点,树的度树的深度(或高度),从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）,所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数；树的度；树的深度,13,3,4,（有几个直接后继就是几度，亦称“次数”）,结点A的度：3结点B的度：2结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结点I的双亲：D结点L的双亲：E,结点B，C，D为兄弟结点K，L为兄弟,树的度：3,结点A的层次：1结点M的层次：4,树的深度：4,结点F，G为堂兄弟结点M的祖先是A、D、H,（3）.树的逻辑结构,一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,（4）.树的存储结构,讨论1：树是非线性结构，该怎样存储？,特点：,仍然有顺序存储、链式存储等方式。,注：这两种存储方式对于线性结构来说很直观也很自然。那么，这两种存储方式如何反映1:n的树型关系呢？（想一想？）,二叉树,讨论3：树的链式存储方案应该怎样制定？,复原困难,讨论2：树的顺序存储方案应该怎样制定？,可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。,先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。,可规定为：,从上至下、从左至右将树的结点依次存入内存。,重大缺陷：,解决思路：,不能唯一复原就没有实用价值！,（5）.树的运算,要明确：1.普通树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！,本章重点：二叉树的表示和实现,遍历指每个结点都被访问且仅访问一次，不遗漏不重复,2、二叉树,为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；所有树都能转为唯一对应的二叉树（可以预习6.4节）。,（1）.二叉树的定义（2）.二叉树的性质（3）.二叉树的存储结构,2、二叉树,（1）、二叉树的定义是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的分别称为左子树和右子树的二叉树组成。(即:空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。）逻辑结构：一对二（1:2）基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒。,2、二叉树,（2）、二叉树的性质：,证：k=1时成立，设k=i-1时成立则当k=i时在二叉树的第i层上至多有2i-1-1*2=2i-1个结点,讨论1：第i层的结点数最多是多少？,2i-1个,性质3：二叉树的叶子结点数n0等于度为2的结点数n2+1（即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：深度为k的二叉树，最多有多少个结点？,2k-1个,讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？,2.深度为的二叉树的结点总数，最多为个。)k-1)log2k)k)k,1.树中各结点的度的最大值称为树的。)高度)层次)深度)度,D,C,C,3.深度为9的二叉树中至少有个结点。)9)8)91,课堂练习：,2、二叉树,完全二叉树:深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。,2、二叉树,B,C,D,E,F,L,A,P,S,Q,R,U,性质5：对一棵有n个结点的完全二叉树按照从第一层（根所在的层次到最后一层，并且每一层都按照从左到右的次序进行编号。根结点的编号为1，最后一个结点的编号为n。对任何一个编号为i的结点而言，则如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2如果2in，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,12,11,10,9,8,7,6,5,4,3,2,1,为何要研究这两种特殊形式？,因为只有这两种形式可以实现二叉树的顺序存储。,问题:设一棵完全二叉树具有1000个结点，则它有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。,489,488,1,0,由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。,解：易求出总层数和末层叶子数。总层数k=log2n1=10;且前9层总结点数为29-1=511(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。,请注意叶子结点总数末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。分析：末层的489个叶子只占据了上层的245个结点（489/2)上层（k=9)右边的0度结点数还有29-1-245=11个！,第i层上的满结点数为2i-1,所以，全部叶子数489(末层)11(k-1层)=500个。度为2的结点叶子总数1=499个。,2、二叉树,（3）、二叉树的存储结构：,一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,ABCDEFGHI,问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5）例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,讨论：不是完全二叉树怎么办？,答：一律补全为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,ABCDE,缺点：浪费空间；插入、删除不便,2、二叉树,(3)、二叉树的存储结构：二、链式存储结构仅定义结点的类型即可。,typedefstructBiTNodeTELemTypedata;structBiTNode*lchild;structBiTNode*rchild;BitTNode,*BiTree;BiTreep;,标准形式：（二叉链表）,typedefstructBiTNodeTELemTypedata;structBiTNode*lchild;structBiTNode*rchild;structBiTNode*parent;BitTNode,*BiTree;BiTreep;,广义标准形式：（三叉链表）,如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,用二叉链表即可方便表示。一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）,例：,root,结点结构:,二叉链表,3、遍历二叉树和线索二叉树,一、遍历二叉树,遍历定义遍历用途遍历方法,指按某条搜索路线遍访每个结点且不重复（又称周游）。,它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。,对每个结点的查看通常都是“先左后右”。,3、遍历二叉树和线索二叉树,遍历规则,二叉树由根、左子树、右子树构成，定义为D、L、R,以根结点为参照系,注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，则有三种实现方案：,DLRLDRLRD先序遍历中序遍历后序遍历,3、遍历二叉树和线索二叉树,例1：,先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：,DBEACDEBCA,口诀：DLR先序遍历，即先根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根,A,B,D,E,C,先序遍历结果+*/ABCDE前缀表示法中序遍历结果A/B*C*D+E中缀表示法后序遍历结果AB/C*D*E+后缀表示法层次遍历结果+*E*D/CAB,例2：用二叉树表示算术表达式,中序遍历算法LDR(node*root)if(root!=NULL)LDR(root-lchild);printf(“%d”,root-data);LDR(root-rchild);return(0);,后序遍历算法LRD(node*root)if(root!=NULL)LRD(root-lchild);LRD(root-rchild);printf(“%d”,root-data);return(0);,结点数据类型自定义typedefstructnodeintdata;structnode*lchild,*rchild；node;node*root;,先序遍历算法DLR(node*root)if(root!=NULL)/非空二叉树printf(“%d”,root-data);/访问DDLR(root-lchild);/递归遍历左子树DLR(root-rchild);/递归遍历右子树return(0);,对遍历的分析：,1.从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径上，每个结点经过3次。,第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历,2.二叉树遍历的时间效率和空间效率时间效率:O(n)/每个结点只访问一次空间效率:O(n)/栈占用的最大辅助空间,精确值：树深为k的递归遍历需要k+1个辅助单元,3、遍历二叉树和线索二叉树,B,C,D,E,L,A,(1)、遍历二叉树：续先序的非递归实现：1、根结点进栈2、结点出栈，被访问3、结点的右、左儿子（非空）进栈4、反复执行2、3，至栈空为止。,先序：A、L、B、E、C、D,e.g:,3、遍历二叉树和线索二叉树,(1)、遍历二叉树：续中序的非递归实现：1、结点（初始时是根结点）进栈，沿左指针查找左儿子。2、若有左儿子，返回第一步。3、若无左儿子，判栈空？空则结束。非空，栈顶结点出栈访问。转向右子树，返回1。,e.g:,B,C,D,E,L,A,X,W,中序：B、L、E、A、C、W、X、D,initstack(s);push(s,t);/t是根结点while(!stackempty(s)while(Gettop(s,p),3、遍历二叉树和线索二叉树,(2)、线索二叉树(自学)为什么采用线索二叉树：二叉树中的空指针场多达n+1个。简单证明：设二叉树中结点的总数为n，度为2的结点总数为n2。空指针场用方框代表。增加了方框结点的二叉树称之为扩展二叉树。在该二叉树之中，原来的n个结点全部成为度为2的结点，方框结点成为叶子。根据二叉树的性质3，原命题得证。,e.g:n=8的二叉树,扩展二叉树,怎样利用这n+1个空指针场？中序穿线树后序穿线树,作业：习题3,本次课小结,1、掌握树和二叉树的基本概念，性质；2、满二叉树和完全二叉树及其性质；3、二叉树的顺序存储是通过补全为完全二叉树，依从上到下、从左到右的规定顺序来实现的；4、二叉树的链式存储和线性表的链式存储一样，是通过指向前驱和后继结点来实现，二叉链表较常用；5、二叉树的遍历是其它操作和运算的基础，务必掌握遍历二叉树的递归和非递归算法；6、下面的“遍历算法的应用举例”请认真消化。,4、遍历算法的应用举例(稍加提示，同学们课后阅读),(2)、统计二叉树中叶子结点的个数,(3)、求二叉树的深度(后序遍历),(4)、复制二叉树(后序遍历),(5)、建立二叉树的存储结构,(1)、查询二叉树中某个结点,1)在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回TRUE;,2)否则在左子树中进行查找,若找到,则返回TRUE;,3)否则继续在右子树中进行查找,若找到,则返回TRUE,否则返回FALSE;,(1)、查询二叉树中某个结点,StatusPreorder(BiTreeT,ElemTypex,BiTreereturnOK,/ifelsereturnFALSE;,elseif(Preorder(T-lchild,x,p)returnOK;elsereturn(Preorder(T-rchild,x,p);/else,(2)、统计二叉树中叶子结点的个数,算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:若是叶子，则计数器增1。,voidCountLeaf(BiTreeT,int/if/CountLeaf,intCountLeaf(BiTreeT)/返回指针T所指二叉树中所有叶子结点个数if(!T)return0;if(!T-lchild/else/CountLeaf,(3)、求二叉树的深度(后序遍历),算法基本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系。,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中访问结点的操作为:求得左、右子树深度的最大值，然后加1。,intDepth(BiTreeT)/返回二叉树的深度if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;,voidDepth(BiTreeT,intlevel,int/调用之前level的初值为1,dval的初值为0.,(4)、复制二叉树(后序遍历),其基本操作为:生成一个结点。,根元素,T,左子树,右子树,左子树,右子树,BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr)if(!(T=newBiTNode)exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;returnT;,生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr),BiTNode*CopyTree(BiTNode*T)if(!T)returnNULL;if(T-lchild)newlptr=CopyTree(T-lchild);/复制左子树elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/复制右子树elsenewrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);returnnewT;/CopyTree,(5)、建立二叉树的存储结构,用空格字符表示无孩子或指针为空,注：要实现遍历运算，必须先把二叉树存入电脑内,怎样建树？见教材P131例,例：将下面的二叉树以二叉链表形式存入计算机内。,考虑1：输入结点时怎样表示“无孩子”？考虑2：以何种遍历方式来输入和建树？,将二叉树按先序遍历次序输入：ABCDEGF,以先序遍历最为合适，让每个结点都能及时被连接到位。,建树算法：StatusCreateBiTree(BiTree/CreateBiTree,输入序列：ABCDEGF,上次课回顾和本次课内容提示:,本章（树和二叉树）第二次授课,已经弄清和解决二叉树的存储，及其重要的遍历运算。请同学们继续：1、设法理清楚解决二叉树的存储问题的基本思路；和线性结构相比，它有什么特点；2、完全二叉树的特点和性质为我们实现普通二叉树的顺序存储提供了什么启示和帮助，该顺序存储有什么缺陷？3、二叉树的递归性定义，使得“遍历”运算很容易实现；充分理解使用堆栈实现“遍历”的非递归算法；,本次课主要解决1、一般树的存储问题和“遍历”运算的实现（只要掌握了树转化为二叉树的方法，那么上述问题就是直接的）；2、重点介绍赫夫曼的构造及其应用。,4、树和森林,1、树的存储结构标准形式：树中的每个结点除有数据场之外，还有K个指针场；其中K为树的度数。1、,数据场,第一个儿子结点的地址,第二个儿子结点的地址,第K个儿子结点的地址,父亲结点的地址,广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针场。,E.g:度数K3的树,A,B,C,D,E,F,G,H,I,L,A123-1B94-10C5-1-10D67-10E-1-1-11F-1-1-12G8-1-13H-1-1-13I-1-1-16P-1-1-1-1,0123456789,-1表示空缺点：空指针场太多，多达(K-1)n+1个。改进：结点中设立度数场，指针场依度数定。但操作麻烦。采用左儿子、兄弟表示法。,用数组表示左图的树,4、树和森林,1、树的存储结构左儿子、兄弟表示法：树中的每个结点有数据场、指向它的第一棵子树树根的指针场、指向它的兄弟结点的指针场。实质上是用二叉树表示一棵树。,数据场,第一棵子树根结点的地址,下一个亲兄弟结点的地址,E.g:度数K3的树,A,B,C,D,E,F,G,H,I,L,A,B,C,D,E,F,G,H,L,I,4、树和森林,2、树、森林于二叉树的转换树转换成相对应的二叉树：1、保留每个结点的最左面的分支，其余分支都被删除。2、同一父结点下面的结点成为它的左方结点的兄弟。,E.g:度数K3的树,A,B,C,D,E,F,G,H,I,L,A,B,C,D,E,F,G,H,I,L,4、树和森林,2、树、森林于二叉树的转换森林转换成相对应的二叉树：增加一个虚拟的根结点，它的儿子为各棵树的根。那么，就变成了树转换成二叉树的问题。,E.g:3棵分别以B、C、D为根的树,B,C,D,E,F,G,H,I,L,B,C,D,E,F,G,H,I,L,A,B,C,D,E,F,G,H,I,L,相应的二叉树,4、树和森林,2、树、森林于二叉树的转换森林转换成相对应的二叉树：增加一个虚拟的根结点，它的儿子为各棵树的根。那么，就变成了树转换成二叉树的问题。,E.g:3棵分别以B、C、D为根的树,B,C,D,E,F,G,H,I,L,B,C,D,E,F,G,H,I,L,A,B,C,D,E,F,G,H,I,L,相应的二叉树,树与二叉树转换,将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树,4、树和森林,3、树、森林的遍历树的前序、后序遍历：1、类似于二叉树的前序遍历：NLR；N:根；L：左子树（第一棵子树），R：其余的那些子树，遍历方向由第二棵子树至最后一棵子树2、类似于二叉树的后序遍历：LRN：L：左子树（第一棵子树），R：其余的那些子树，遍历方向由第二棵子树至最后一棵子树，N:根,4、树和森林,3、树、森林的遍历森林的前序、中序遍历：前序遍历类似于树的前序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行前序遍历，即得到森林的前序序列（不含树根结点）后序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的儿子为各棵树的根。那么对这棵树进行后序遍历，即得到森林的后序序列（去掉树根结点）注意：本书称之为中序遍历,如称之为后序遍历更合理。,前序：B、L、E、C、F、D、G、I、H中序：L、E、B、F、C、I、G、H、D,B,C,D,E,F,G,H,I,L,A,B,C,D,E,F,G,H,I,L,4、树和森林,3、树、森林的遍历树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应：前序序列和对应的二叉树的前序序列完全一致。E、G：左图的树的根A，及它的儿子结点B、C、D在树的的前序序列和相应的二叉树中前序序列中的序号。根A:11结点B：22结点C：55结点D：77,B,C,D,E,F,G,H,I,L,A,A,B,C,D,E,F,G,H,I,L,以C为例：在树中：序号根节点数第一棵子树的结点数15在二叉树中：序号根节点数左儿子数左儿子子树结点数15,4、树和森林,3、树、森林的遍历树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应：后序序列和对应的二叉树的中序序列完全一致。E、G：左图的树的根A，及它的儿子结点B、C、D在树的的后序序列和相应的二叉树的中序序列中的序号。根A:1010结点B：33结点C：55结点D：99,B,C,D,E,F,G,H,I,L,A,A,B,C,D,E,F,G,H,I,L,后序：L、E、B、F、C、I、G、H、D、A,以C为例：在树中：序号第一棵子树的结点数C的子树的结点数15在二叉树中：序号B的左子树的结点数B的结点数C的左子树结点数15,中序：L、E、B、F、C、I、G、H、D、A,4、树和森林,3、树、森林的遍历森林的前序、中序（当作后序更好理解）和相应的二叉树的前序、中序遍历序列一一对应,E.g:3棵分别以B、C、D为根的树,B,C,D,E,F,G,H,I,L,B,C,D,E,F,G,H,I,L,A,B,C,D,E,F,G,H,I,L,A,相应的二叉树,6、赫夫曼树及其应用,1、最优二叉树（赫夫曼树）路径长度：结点之间的树枝的总数树的路径长度：从根到每一结点的路径长度之和树的带权路径长度：叶子结点的带权路径长度之和。设有n片叶子，它们的权值分别为w1、w2、.wn，相应的路径长度分别为L1、L2、.Ln。则树的带权路径长度可记为：nWPL=wklkk=1,E,G,H,L,L,E,H,G,E,G,H,L,7,7,7,5,2,4,4,4,2,2,5,5,WPL=36,WPL=46,WPL=35,最优二叉树或赫夫曼树：树的带权路径长度WPL最小的二叉树。,6、赫夫曼树及其应用,1、最优二叉树（赫夫曼树）赫夫曼算法（产生最优二叉树的算法）的实现：1、给定一个具有n个权值w1,w2,wn的结点的集合F=T1,T2,Tn。2、