《数据结构》-《数据结构》(c语言版)第六章_树和二叉树

第六章树和二叉树61树的定义和基本术语树的定义和基本术语62二叉树二叉树63遍历二叉树和线索二叉树遍历二叉树和线索二叉树64树和森林树和森林66赫夫曼树及其应用赫夫曼树及其应用学习提要1掌握二叉树的性质,了解相应的证明方法。2熟悉二叉树的各种存储结构的特点及适用范围。3掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。4理解二叉树线索化的实质，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。6了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。重难点内容二叉树的性质及其证明、二叉树的遍历、二叉树的线索化、树和森林与二叉树的转换、哈夫曼树的遍历和哈夫曼编码。61树的定义和基本术语612基本术语基本术语611树的类型定义树的类型定义611树的类型定义树的抽象数据类型定义ADTTREE数据对象DD是具有相同特性的数据元素的集合。数据关系R若D为空集，则称为空树。否则若D仅含一个数据元素，则R为空集。1在D中存在唯一的称为根（ROOT）的结点；2当N1时，其余结点可分为MM0个互不相交的有限集T1,T2,TM，其中每一棵子集本身又是一棵符合本定义的树，称为根的子树（SUBTREE）。基本操作PADTTREEA只有根结点的树ABCDEFGHIJKLM有子树的树根子树基本操作查找类插入类删除类ROOTT/求树的根结点查找类VALUET,CUR_E/求当前结点的元素值PARENTT,CUR_E/求当前结点的双亲结点LEFTCHILDT,CUR_E/求当前结点的最左孩子RIGHTSIBLINGT,CUR_E/求当前结点的右兄弟TREEEMPTYT/判定树是否为空树TREEDEPTHT/求树的深度TRAVERSETREET,VISIT/遍历INITTREEVALUET,EPARENTT,ELEFTCHILDT,ERIGHTCHILDT,ELEFTSIBLINGT,ERIGHTSIBLINGT,EBITREEEMPTYTBITREEDEPTHTPREORDERTRAVERSET,VISITINORDERTRAVERSET,VISITPOSTORDERTRAVERSET,VISITLEVELORDERTRAVERSET,VISITINITBITREEASSIGNT,CREATEBITREEINSERTCHILDT,P,LR,CCLEARBITREEDESTROYBITREEDELETECHILDT,P,LR性质1在二叉树的第I层上至多有2I1个结点。I1622二叉树的性质二叉树的性质用归纳法证明归纳基归纳假设归纳证明I1层时，只有一个根结点2I1201；二叉树上每个结点至多有两棵子树，则第I层的结点数2I222I1。假设对所有的J，1JI，命题成立；性质2深度为K的二叉树上至多含2K1个结点（K1）。证明基于上一条性质，深度为K的二叉树上的结点数至多为20212K12K1性质3对任何一棵二叉树，若它含有N0个叶子结点、N2个度为2的结点，则必存在关系式N0N21。证明设二叉树上结点总数NN0N1N2又二叉树上分支总数BN12N2而BN1N0N1N21由此，N0N21。两种特殊形式的二叉树V满二叉树L定义指的是深度为K且含有2K1个结点的二叉树。L特点每一层上的结点数都是最大结点数。1231145891213671014151234567V完全二叉树L定义树中所含的N个结点和满二叉树中编号为1至N的结点一一对应。L特点U叶子结点只可能在层次最大的两层上出现U对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L1。123114589126710123456性质4具有N个结点的完全二叉树的深度为LOG2N1。证明设完全二叉树的深度为K，则根据第二条性质得2K11N，则该结点无左孩子，否则，编号为2I的结点为其左孩子结点；3若2I1N，则该结点无右孩子结点，否则，编号为2I1的结点为其右孩子结点。DEFINEMAX_TREE_SIZE100/二叉树的最大结点数TYPEDEFTELEMTYPESQBITREEMAX_TREE_SIZE/0号单元存储根结点SQBITREEBT一、顺序存储结构623二叉树的存储结构二叉树的存储结构例如ABCDEFGHIJKL01234567891011ABCKDEHILFGJ123456789101112例如ABCDEFABDCEF0123456789101112132511437特点V结点间关系蕴含在其存储位置中，即编号为I的结点元素存储在一维数组中下标为I1的分量中。V浪费空间，适于存满二叉树和完全二叉树。二、链式存储结构LCHILDDATARCHILD结点结构V二叉链表TYPEDEFSTRUCTBITNODE/结点结构TELEMTYPEDATASTRUCTBITNODELCHILD,RCHILD/左右孩子指针BITNODE,BITREE在N个结点的二叉链表中，有N1个空指针域ABCDEFG例如ABCDEFGTYPEDEFSTRUCTTRITNODE/结点结构TELEMTYPEDATASTRUCTTRITNODELCHILD,RCHILD/左右孩子指针STRUCTTRITNODEPARENT/双亲指针TRITNODE,TRITREELCHILDDATAPARENTRCHILD结点结构V三叉链表ABCDEFGABCDEFG例如63遍历二叉树和线索二叉树632线索二叉树线索二叉树631遍历二叉树遍历二叉树631遍历二叉树遍历二叉树一、问题的提出二、先左后右遍历的定义三、算法的递归描述四、中序遍历算法的非递归描述五、遍历算法的应用举例遍历二叉树，即顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一、问题的提出ABCDEF对“二叉树”而言，可以有三条搜索路径1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。DLRV先（根）序遍历（DLR）二叉树的典型结构V中（根）序遍历（LDR）V后（根）序遍历（LRD）V先序遍历二叉树操作定义若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。ADBCDLRADLRDLRBDCDLR先序遍历序列ABDC先序遍历V中序遍历二叉树操作定义若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。ADBCLDRBLDRLDRADCLDR中序遍历序列BDAC中序遍历V后序遍历二叉树操作定义若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。ADBCLRDLRDLRDADCLRD后序遍历序列DBCA后序遍历B/ABEFCD先序遍历中序遍历后序遍历层次遍历ABCD/EFABCD/EFABCD/EFABCD/EF三、算法的递归描述VOIDPREORDERBITREET,VOIDVISITTELEMTYPE/访问结点PREORDERTLCHILD,VISIT/遍历左子树PREORDERTRCHILD,VISIT/遍历右子树主程序PRET返回返回PRETR返回返回PRETRACBDTBPRINTFBPRETLTAPRINTFAPRETLTDPRINTFDPRETLTCPRINTFCPRETL返回T左是空返回PRETRT左是空返回T右是空返回T左是空返回T右是空返回PRETR先序序列ABDCVISITTDATAPREORDERTLCHILD,VISITPREORDERTRCHILD,VISIT四、中序遍历算法的非递归描述STATUSINORDERTRAVERSEBITREET,STATUSVISITTELEMTYPEEINITSTACKSPTWHILEP|STACKEMPTYSIFPPUSHS,PPPLCHILD/根指针进栈，遍历左子树ELSE/根指针退栈，访问根结点，遍历右子树POPS,PIFVISITPDATARETURNERRORPPRCHILD/WHILERETURNOK/INORDERTRAVERSEABCDEFGPPAPPBPPCPNULLCPNULLBPPDPPEPNULLPNULLEPPGPNULLPGPNULLPPPFPNULLPFDAPNULLV统计二叉树中叶子结点的个数算法基本思想先序或中序或后序遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为若是叶子，则计数器增1。V求二叉树的深度后序遍历算法基本思想从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为求得左、右子树深度的最大值，然后加1。首先分析二叉树的深度和它的左、右子树深度之间的关系。INTDEPTHBITREET/返回二叉树的深度IFTDEPTHVAL0ELSEDEPTHLEFTDEPTHTLCHILDDEPTHRIGHTDEPTHTRCHILDDEPTHVAL1DEPTHLEFTDEPTHRIGHTDEPTHLEFTDEPTHRIGHTRETURNDEPTHVAL64树和森林642森林和二叉树的转换森林和二叉树的转换641树的存储结构树的存储结构643树和森林的遍历树和森林的遍历641树的存储结构树的存储结构一、双亲表示法二、孩子表示法三、孩子兄弟表示法树的三种存储结构DEFINEMAX_TREE_SIZE100TYPEDEFSTRUCTPTNODE/结点结构TELEMTYPEDATAINTPARENT/双亲位置域TNODETYPEDEFSTRUCT/树结构PTNODENODESMAX_TREE_SIZEINTR,N/根的位置和结点数PTREE一、双亲表示法ABCDEFHGI011244401如何找孩子结点EFGHIBDCA012345678DATAPARENTR0，N9二、孩子表示法DATACHILD1CHILD2CHILDDDATADEGREECHILD1CHILD2CHILDDV多重链表每个结点有多个指针域，分别指向其子树的根。U结点同构结点的指针个数相等，为树的度DU结点不同构结点指针个数不等，为该结点的度DN个结点度为K的树中有NK11个空链域V孩子链表每个结点的孩子结点用单链表存储，再用含N个元素的结构数组指向每个孩子链表。TYPEDEFSTRUCTCTNODEINTCHILDSTRUCTCTNODENEXTCHILDPTR孩子结点结构CHILDNEXTTYPEDEFSTRUCTELEMDATACHILDPTRFIRSTCHILD/孩子链的头指针CTBOX双亲结点结构DATAFIRSTCHILD树结构TYPEDEFSTRUCTCTBOXNODESMAX_TREE_SIZEINTN,R/结点数和根结点的位置CTREEABCDEFHGI12348675如何找双亲结点601234578ACDEFGHIBDATAFCR0，N9带双亲的孩子链表501234678ACDEFGHIBDATAFC12348675101124440PARENTABCDEFHGIFIRSTCHILDDATANEXTSIBLING三、孩子兄弟表示法（二叉树表示法）TYPEDEFSTRUCTCSNODEELEMDATASTRUCTCSNODEFIRSTCHILD,NEXTSIBLINGCSNODE,CSTREE结点结构ABCDEFHGIABCDEFGHI642树、森林与二叉树转换ACBED树ABCDE二叉树ABCDEABCDEABCDE对应存储存储解释解释66赫夫曼树及其应用赫夫曼树及其应用661最优二叉树662赫夫曼编码661最优二叉树（赫夫曼树）V结点的路径长度从根结点到该结点的路径上分支的数目。V树的路径长度从树根到每一个结点的路径长度之和。V树的带权路径长度树中所有叶子结点的带权路径长度之和，记作V赫夫曼树（最优二叉树）带权路径长度之和最小的二叉树。V结点的带权路径长度从该结点到树根之间的路径长度与结点上权的乘积。例如ABCD7524WPL7252224236DCAB2475WPL7353214246ABCD7524WPL7152234335（1）根据给定的N个权值W1,W2,WN，构造N棵二叉树的集合FT1,T2,TN，其中每棵二叉树中均只含一个带权值为WI的根结点，其左、右子树为空树；如何构造最优树（赫夫曼算法）以二叉树为例（2）在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；（3）从F中删去这两棵树，同时加入刚生成的新树；（4）重复2和3两步，直至F中只含一棵树为止。9例如已知权值W5,6,2,9,756275276976713952767139527952716671329HUFFMAN算法实现TYPEDEFSTRUCTUNSIGNEDINTWEIGHTUNSIGNEDINTPARENT,LCHILD,RCHILDHTNODE,