资源描述
前面我们学习的线性数据结构，每个元素都有唯一的前驱（第一个除外）和后继（最后一个除外），但是在现实应用中，一些问题的数据元素之间的关系就不这样简单，例如在编译程序中，用树表示源程序的语法结构。本章学习一种非线性数据结构树，数据元素之间是一种层次关系，元素有且只有一个前驱，但可以有多个后继。,第六章树和二叉树,树的概念和基本术语二叉树二叉树遍历线索二叉树树与森林霍夫曼树,第六章树和二叉树,6.1树的概念和基本术语,树的定义树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n1，除根以外的其它结点划分为m(m0)个互不相交的有限集T1,T2,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。,例如,A,只有根结点的树,有13个结点的树,其中:A是根,其余结点分成三个互不相交的子集，T1=B,E,F,K,L；T2=C,G；T3=D,H,I,J,M,T1,T2,T3都是根A的子树，且本身也是一棵树,树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；,兄弟结点：同一双亲的孩子结点；堂兄结点：双亲在同一层的结点互为堂兄弟。结点的层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；,树的高度：树中结点的最大层次.结点的度：结点子树的个数树的度：树内各结点的度的最大值。叶子结点：也叫终端结点，是度为0的结点；分枝结点：度不为0的结点；有序树：子树有序的树，（子树不能互换）如：家族树；无序树：不考虑子树的顺序；,任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林,森林：,是m（m0）棵互不相交的树的集合,A,root,F,路径：树中的k个结点n1,n2，nk，满足ni是ni+1的双亲，n1到nk有一条路径路径长度：分支数路径上结点个数一1,根没有双亲，叶子没有孩子；vi是vj的双亲，则L(vi)=L(vj)-1;堂兄弟的双亲是兄弟关系吗？有序树和无序树的区别；,注意,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),树的常见表示方法,1.直观表示法：用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系.根在上，叶子在下（即树向下生长）,2、集合表示法：根据树的集合定义，写出集合划分。3、文氏图表示法：集合表示的一种直观表示，用图表示集合。,4、目录表示法：将一棵树描述为一本书，书-章-节-小节,5、广义表表示法：将一棵树描述为一个广义表，子树就对应子表。,人们最常用的是第一种，但是不适合计算机！,基本操作,InitTree（T）；操作结果：构造空树T。DestroyTree（T）；初始条件：树T存在。操作结果：销毁树T。CreateTree（T，definition）初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree（T）；初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty（T）初始条件：树T存在。操作结果：若T为空树，则返回ture，否则false。,TreeDepth（T）初始条件：树T存在。操作结果：返回T的深度。Root（T）初始条件：树T存在。操作结果：返回T的根。Value（T,Cur_e）初始条件：树T存在，cure是T中某个结点。操作结果：返回cure的值。Assign（T，cur_e，value）初始条件：树T存在，cure是T中某个结点。操作结果：结点cur_e赋值为value。Parent（T，cure）初始条件：树T存在，cure是T中某个结点。操作结果：若cure是T的非根结点，则返回它的双亲，否则函数值为“空”。Rightsibling（T，cure）初始条件：树T存在，cure是T中某个结点操作结果：若cure有右兄弟，则返回它的右兄弟，否则函数值为“空”。,LeftChild（T，cure）初始条件：树T存在，cure是T中某个结点。操作结果：若cure是T的非叶子结点，则返回它的最左孩子，否则返回“空”。InsertChild（T，p，i，c）；初始条件：树T存在，p指向T中某个结点，1ip所指结点的度1，非空树c与T不相交。操作结果：插入c为T中p指结点的第i棵子树。DeleteChild（T，p，i）；初始条件：树T存在，p指向T中某个结点，1ip指结点的度。操作结果：删除T中p所指结点的第i棵子树。TraverseTree（T，visit（）；初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次.一旦visit（）失败，则操作失败,6.2二叉树6.2.1二叉树的概念6.2.2二叉树的性质6.2.3二叉树的存储结构,定义:二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,6.2.1二叉树定义(BinaryTree),二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,应用举例例可以用二叉树表示表达式,a+b*(c-d)-e/f,性质1在二叉树的第i层上至多有2i1个结点。(i1)证明用归纳法证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，ij1，命题成立，即第j层上至多有2j-1个结点。由归纳假设第i-1层上至多有2i2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i2=2i-1。,6.2.6二叉树的性质,性质2深度为k的二叉树至多有2k-1个结点(k1)。证明：由性质1可见，深度为k的二叉树的最大结点数为,性质3对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0n21.证明：若度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1,定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。,两种特殊形态的二叉树,满二叉树,非完全二叉树,定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。,完全二叉树,性质4具有n(n0)个结点的完全二叉树的深度为log2(n)1证明：设完全二叉树的深度为h，则根据性质2和完全二叉树的定义有2h1-1n2h-1或2h1n2h取对数h1log2nh，又h是整数，因此有h=log2(n)1,性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2,n-1，则有以下关系：若i=0,则i无双亲若i0,则i的双亲为(i-1)/2若2*i+1n,则i的左子女为2*i+1，若2*i+2n,则i的右子女为2*i+2若结点编号i为偶数，且i!=0,则左兄弟结点i-1.若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.,性质5：在完全二叉树中编号（1开始）为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为i/2；,2i+2,2i2i+12i+22i+3i+12i2i+1,i,ii+1,6.2.3二叉树的存储结构二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。,顺序存储结构其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。,#defineMAX_TREE_SIZE100/二叉树的最大结点数typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0号单元存放根结点SqBiTreebt;,一般二叉树的顺序表示,顺序表示,完全二叉树的顺序表示,请分析：深度为k的且只有k个结点的单支树需要长度为？,2.链式存储结构在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：,其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。,typedefstructBiTNodeTElemTypedata;structBiTNodeLchild,*Rchlid;BTNode,*BTree;,GH,DEF,BC,A,举例,这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。,typedefstructTriTNode/结点结构TElemTypedata;structTriTNode*lchild,*rchild;/左右孩子指针structTriTNode*parent;/双亲指针TriTNode,*TriTree;,二叉树链表表示的示例,三叉链表,二叉树,二叉链表,三叉链表的静态结构,上面们二叉链表或三叉链表是用指针实现，是一种动态的链式存储结构，链式存储结构也可用一维数组来实现，用一维数组表示的二叉链表或三叉链表，称为静态链表,6.3二叉树的遍历,遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事,二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？,6.3.1二叉树的遍历方法二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树,令：L：遍历左子树D：访问根结点R：遍历右子树有六种遍历方法：DLR，LDR，LRD，DRL，RDL，RLD,约定先左后右,有三种遍历方法：DLR、LDR、LRD,分别称为先序遍历、中序遍历、后序遍历,先序遍历（DLR）若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；,先序遍历序列：A,B,D,E,G,C,F,例：先序遍历右图所示的二叉树（1）访问根结点A（2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树,中序遍历（LDR）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树,中序遍历序列：D,B,G,E,A,C,F,例：中序遍历右图所示的二叉树（1）中序遍历左子树：即按LDR的顺序遍历左子树（2）访问根结点A（3）中序遍历右子树：即按LDR的顺序遍历右子树,后序遍历（LRD）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点,后序遍历序列：D,G,E,B,F,C,A,例：后序遍历右图所示的二叉树（1）后序遍历左子树：即按LRD的顺序遍历左子树（2）后序遍历右子树：即按LRD的顺序遍历右子树（3）访问根结点A,后序遍历序列：a,b,c,d,-,*,+,e,f,/,-,中序遍历序列：a,+,b,*,c,-,d,-,e,/,f,先序遍历序列：-,+,a,*,b,-,c,d,/,e,f,例：先序遍历、中序遍历、后序遍历下图所示的二叉树,这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1）基本项（也叫终止项）；2）递归项,若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；,先序遍历递归定义递归项,二.遍历的递归算法上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：先序遍历（DLR）的定义：,该定义隐含着若二叉树为空，结束,上面先序遍历的定义等价于：若二叉树为空，结束基本项（也叫终止项）若二叉树非空递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；,下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总是成功的。,先序遍历递归算法voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树,visit()是访问结点的函数。本算法先序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()if(T)/若二叉树不为空，访问根结点；遍历左子树,遍历右子树Visit(T-data)；PreOrderTraverse(T-lchild,Visit);PreOrderTraverse(T-rchild,Visit);/PreOrderTraverse,最简单的Visit函数是：StatusPrintElement(TElemTypee)/输出元素e的值printf(e);returnOK;,2中序遍历递归算法voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，visit()是访问结点的/数。本算法中序遍历以为根结点指针的二叉树，/对每个数据元素调用函数Visit()if(T)/若二叉树为空，结束返回/若二叉树不为空，遍历左子树，访问根结点，/遍历右子树InOrderTraverse(T-lchild,Visit);Visit(T-data)；InOrderTraverse(T-rchild,Visit);/InOrderTraverse,3后序遍历递归算法voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，visit()是访问结点的/函数。本算法中序遍历以为根结点指针的二叉/树，对每个数据元素调用函数Visit()if(T)/若二叉树为空，结束返回/若二叉树不为空，遍历左子树，遍历右子树，/访问根结点PostOrderTraverse(T-lchild,Visit);PostOrderTraverse(T-rchild,Visit);Visit(T-data)；/PostOrderTraverse,例:已知一棵二叉树的中根序列和先根序列分别为ABCDEFGHIJK和EBADCFHGIKJ，试画出这棵二叉树。,4.中序遍历二叉树(非递归算法)用栈实现,ba,ab入栈,b退栈访问,d入栈,d退栈访问,e退栈访问,ec,栈空,a退栈访问,ce入栈,c退栈访问,voidInOrder(BinTreeT)stackS;InitStack(,线索二叉树遍历是二叉树最基本最常用的操作。1）对二叉树所有结点做某种处理可在遍历过程中实现;2）查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：1）遍历算法要复杂的多，费时的多；2）为检索或查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。,5.4线索二叉树(ThreadedBinaryTree),如何将二叉树线性化？以中序遍历为例，我们看到通过遍历可以得到二叉树结点的中序序列。若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。,加上结点前趋后继信息（线索）的二叉树称为线索二叉树,中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E,加上结点前趋后继信息（结索）的二叉树称为线索二叉树,孩子指针前趋指针后继指针,2线索链表线索二叉树的存贮方法：1）为每个结点增加二个标志域。缺点：要点用较多的内存空间。有n个结点的二叉链表，有n+1个空指针域,故可利用这些的空指针域存放结点的前趋和后继指针，以这种结点的构成二叉链表称为线索链表,对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索Thread”。若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread”。,Ltag=0,lchild为左子女指针Ltag=1,lchild为前驱线索Rtag=0,rchild为右子女指针Rtag=1,rchild为后继指针,结点结构,线索链表的类型说明typedefenumlink,threadPointerTag;/link=0,thread=1typedefstructBiThrNodeTElemTypedata;StructBiThrNode*lchild,*rchild;/左右指针域PointerTagLtag,Rtag;/左右标志域，标志域为0时表示左右指针域存储的是左右孩子的指针，标志域为1时表示左右指针域存储的是前趋后继结点的指针BiThrNode，*BiThrTree,为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点.约定：,头结点的lchild域：存放线索链表的根结点指针头结点的rchild域:中序序列最后一个结点指针中序序列第一结点lchild域指向头结点;中序序列最后一个结点的rchild域指向头结点;,如图标出的中序二叉树结点的顺序，可看出1）中序序列的第一结点，是二叉树的最左下结点；2）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点；3）若p所指结点的右孩子域为孩子指针，则p的后继结点为其右子树的最左下结点；,中序遍历序列：D,B,H,E,A,F,C,G,3线索二叉树的遍历在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历。基本步骤：1）p=T-lchild;p指向线索链表的根结点；2）若线索链表非空，循环：（a）循环，顺着p左孩子指针找到最左下结点；访问之（b）若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环：p=p-rchild；并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）（c）一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p-rchild，使p指向右孩子结点；3）返回OK；结束,线索链表的遍历算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)/T指向头结点，头结点的左链lchild指向根结点，/中序遍历二叉线索树T算法，对每个数据元素调用函数Visit。P=T-lchild;/p指向根结点While(p!=T)/空树或遍历结束时，p=TWhile(p-Ltag=Link)p=p-lchild;/找到最左下结点；访问之Visit(p-data)while(p-Rtag=Thread/InOrderTraverse_Thr,树的存储结构在树中，每个结点即可能有孩子也可能有双亲，所以既可以通过保存每个结点的孩子结点位置来表示结点之间的结构关系，也可以通过保存每个结点的双亲结点位置来表示结点之间的结构关系。1.双亲表示：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。,树与森林,*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。,特点:,用双亲表示实现的树定义,#defineMaxSize/最大结点个数typedefcharTreeData;/结点数据typedefstruct/树结点定义TreeDatadata;intparent;/双亲位置域TreeNode;typedefTreeNodeTreeMaxSize;/树,2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。,方法一:顺序存储,#defineMAX_TREE_SIZE100typedefstructPTNodeTElemTypedata;intchild1;/第1个孩子位置域intchild2;/第2个孩子位置域.intchildd;/第d个孩子位置域PTNode;typedefstructPTNodenodesMAX_TREE_SIZE;intn;/结点数PTree;,孩子表示法举例,*便于涉及孩子的操作；求双亲不方便；*采用同构的结点，空间浪费。,方法二:链式存储：对树的每个结点用线性链表存贮它的孩子结点,树的孩子链表类型定义typedefstructCTNode/孩子结点intchild;structCTNode*next;*ChildPtr;typedefstructTElemTypedata;ChildPtrfirstchild;/孩子链表头指针CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;Intn,r;/结点数和根的位置；CTree;,孩子链表存储表示举例,*便于涉及孩子的操作；*求结点的双亲时不方便。,T.nodes;T.n=10;T.r=0;,结点结构,3孩子兄弟表示法(二叉链表示法)孩子兄弟表示法用二叉链表作为树的存贮结构,typedefstructCSNodeELemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,类型定义:,孩子兄弟表示法示例：,树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法,特点：一棵树转换成二叉树后，根结点没有右孩子。,此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表,由此可将树与二叉树对应起来,森林森林：树的集合将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历；,包含两棵树的森林,如果F=T1,T2,Tm是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。(1)若F为空，即m=0,则B为空树；(2)若F非空，则B的根root即为森林中第一棵树的根ROOT(T1)；B的左子树LB是从T1中根结点的子树森林F1=T11,T12,T1m1转换而成的二叉树;其右子对RB是从森林F=T2,T3,Tm转换而成的二叉树.,森林与二叉树的转换,二叉树转换成森林,如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F=T1,T2,Tm：(1)若B为空，则F为空；(2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T1中的根结点的子树森林F1是由B的左子树LB转换而成的森林;F中除T1之外其余树组成的森林F=T2,T3,，Tm是由B的右子树RB转换而成的森林。,当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历ABEFCDG对应二叉树前序遍历ABEFCDG树的先根遍历结果与其对应二叉树表示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现,树的先根次序遍历,树的遍历,树的后根次序遍历:,当树非空时依次后根遍历根的各棵子树访问根结点树后根遍历EFBCGDA对应二叉树中序遍历EFBCGDA树的后根遍历结果与其对应二叉树表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法实现,森林的两种遍历方法：,一、先序遍历森林：若森林非空，则（1）访问森林中第一棵树的根结点；（2）先序遍历第一棵树的根结点的子树森林；（3）先序遍历除去第一棵树之后的森林。二、中序遍历森林：若森林非空，则（1）中序遍历第一棵树的根结点的子树森林；（2）访问森林中第一棵树的根结点；（3）中序遍历除去第一棵树之后的森林。,霍夫曼树(HuffmanTree),在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。在路径上的分支数目被称为路径长度。树的带权路径长度是树的各叶结点所带的权值wi与该结点到根的路径长度li的乘积的和。用公式可表示为：,WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=35,带权路径长度达到最小,霍夫曼树,假设有n个权值1,2,n，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为i,则其中：带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树.在霍夫曼树中，权值大的结点离根最近。,构造赫夫曼树的算法思想,(1)根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左右子树均空.(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左.右子树根结点的权值之和.(3)在F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复(2)和(3),直到F只含一棵树为止.这棵树便是赫夫曼树.,F:7524,7,5,2,4,初始,举例霍夫曼树的构造过程,最佳判定树,考试成绩分布表,判定树,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,WPL=0.10*1+0.15*2+0.25*3+0.35*4+0.15*4=3.15,最佳判定树,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2=0.3+0.45+0.5+0.7+0.3=2.25,霍夫曼编码,主要用途是实现数据压缩。,设给出一段报文：CASTCASTSATATATASA字符集合是C,A,S,T，各个字符出现的频度(次数)是W2,7,4,5。若给每个字符以等长编码A:00T:10C:01S:11则总编码长度为(2+7+4+5)*2=36.,若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为2/18,7/18,4/18,5/18,化整为2,7,4,5。以它们为各叶结点上的权值,建立霍夫曼树。左分支赋0，右分支赋1，得霍夫曼编码(变长编码)。,7,2,5,4,0,1,0,0,1,1,A,C,T,S,A:0T:10C:110S:111它的总编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。总编码长度正好等于霍夫曼树的带权路径长度WPL。霍夫曼编码是一种无前缀编码。解码时不会混淆。,霍夫曼编码树,前缀编码:指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,1.如图所示的树回答下面题：1）哪个是根结点？2）哪些是叶子结点？3）哪个是E的父结点？4）哪些是E的子孙点？5）哪些是E的兄弟结点？哪些是C的兄弟结点？6）结点B和结点I的层数分别是多少？7）树的深度是多少？8）以结点G为根的子树的深度是多少？9）树的度是多少？,2.分别画出含3个结点的树与二叉树的所有不同形态。3.高度为h的完全二叉树至少有多少个结点？最多有多少个结点？,4.采用顺序存储方法和链式存储方法分别画出上图所示二叉树的存储结构。5.分别写出上图所示二叉树的前序、中序和后序遍历序列。,6.若二叉树中各结点值均不相同。1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA，请画出此二叉树。2)已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG，请画出此二叉树。7.一个二叉树如图所示,分别写出其前序、中序、后序的遍历序列。,8.有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为5、2、1、6、4。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。,
展开阅读全文