数据结构中的树图查找排序.pptx

树树:是是 n(n0)n(n0)个结点的有限集合。如果个结点的有限集合。如果该集合为空，称为空树。在任意一棵非空该集合为空，称为空树。在任意一棵非空树中树中:ABCDEFKLGHIJM树的定义树的定义1)1)有且仅有一个特定的称为有且仅有一个特定的称为根结点根结点 (root)(root)的结点的结点;2)2)其他结点可分为若干个互其他结点可分为若干个互不相交的子集不相交的子集,而且每一个而且每一个子集本身又是一棵树子集本身又是一棵树,称为称为根的子树。根的子树。递归定义递归定义第1页/共212页结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素数据元素+若干指向子树若干指向子树的分支的分支结点分支的个数结点分支的个数,即子树的数目即子树的数目如：如：A A的度的度-3-3；B B的度的度-2-2；K K的度的度-0-0；树中所有结点的度的最大值树中所有结点的度的最大值 如：树的度为如：树的度为3 3；度为零的结点，也称终端结点度为零的结点，也称终端结点如例：如例：K K，L L，F F，G G，M M，I I，J J为终端结点为终端结点度大于零的结点度大于零的结点如例：如例：A,B,C,D,EA,B,C,D,E基本术语基本术语612345第2页/共212页森林：森林：是是 m m（m0m0）棵互不相交的树的集合）棵互不相交的树的集合ArootBEFKLCGDHIJMF第3页/共212页线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)第4页/共212页7.2 7.2 二叉树二叉树第5页/共212页二叉树二叉树或为空树；或是由一个根结或为空树；或是由一个根结点加上两棵分别称为点加上两棵分别称为左左和和右子树右子树的、的、互不交的互不交的二叉树组成。二叉树组成。ABCDEFGHK根结点左子树右子树EF特点：特点：1 1）每个结点）每个结点最多只有两棵最多只有两棵子树；子树；2 2）两颗子树）两颗子树有左右之分，有左右之分，顺序不能换。顺序不能换。第6页/共212页二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树第7页/共212页特殊特殊的二叉树：的二叉树：满二叉树满二叉树满二叉树：满二叉树：指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树。个结点的二叉树。123456789 10 11 12 13 14 151234567深度为深度为3，节点数，节点数=23-1=7深度为深度为4，节点数，节点数=24-1=15特点：特点：1）每一层上的结点数都是最大结点数；）每一层上的结点数都是最大结点数；2）叶子结点都在最后一层。）叶子结点都在最后一层。第8页/共212页完全二叉树：完全二叉树：树中所含的树中所含的n 个结点和满个结点和满二叉树中编号为二叉树中编号为1 至至n 的结点一一对应。的结点一一对应。12345612345612345特点：特点：1）除了最下一层外其余各层都是满的；）除了最下一层外其余各层都是满的；2）最下一层的结点都集中在该层的左侧。）最下一层的结点都集中在该层的左侧。12345678 9 10特殊特殊的二叉树：的二叉树：完全二叉树完全二叉树第9页/共212页性质性质1：满二叉树的第满二叉树的第i层上有层上有2i-1 个结点个结点(i1)用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1时，只有一个根结点，时，只有一个根结点，2i-1=20=1；假设第假设第j j层有层有2 2j-1j-1结点，命题成立结点，命题成立;第第j层的每个结点都有层的每个结点都有2个结点，则第个结点，则第(j+1)层上的结点数层上的结点数=2*2j-1=2j=2(j+1)-1。二叉树的性质二叉树的性质1234 5 6 7第10页/共212页性质性质1的推论：的推论：在二叉树的第在二叉树的第i层上至多有层上至多有2i-1 个结点个结点(i1)。第11页/共212页性质性质2：深度为深度为k 的满二叉树共有的满二叉树共有2k-1 个结个结点（点（k1）。证明：证明：基于上一条性质，深度为基于上一条性质，深度为k 的满二叉树上的满二叉树上的结点数为：的结点数为：20+21+2k-1=2k-1性质性质2的推论的推论：深度为深度为k 的二叉树上最多的二叉树上最多有有2k-1 个结点（个结点（k1）第12页/共212页性质性质3：设二叉树叶子结点数为设二叉树叶子结点数为n0，度为度为 2的结点数为的结点数为n2，则必存在关系式：，则必存在关系式：n0=n2+1。性质性质4 4：具有具有 n n 个结点的完全二叉树的个结点的完全二叉树的深深度度为为 loglog2 2n n +1+1第13页/共212页性质性质 5 5：对于具有对于具有n n个结点的完全二叉树，如个结点的完全二叉树，如果按照从上到下和从左至右的顺序对二叉树果按照从上到下和从左至右的顺序对二叉树中的所有结点从中的所有结点从 1 1 至至 n n进行编号，则对于任进行编号，则对于任意的序号为意的序号为 i i 的结点，有的结点，有：(1)(1)若若 i1i1，则序号为，则序号为i i的结点的双亲结点的序号的结点的双亲结点的序号为为i/2i/2；如果；如果i=1i=1，则该结点是根，无双亲，则该结点是根，无双亲;(2)(2)若若 2i=n2in2in 则该结点无左孩子；则该结点无左孩子；(3)(3)若若 2i+1=n2i+1n2i+1n，则序号为，则序号为i i的结点无右的结点无右孩子结点。孩子结点。第14页/共212页二叉树的存储结构二叉树的存储结构二、二叉树的链式存储表示二、二叉树的链式存储表示一、一、二叉树的顺序存储表示二叉树的顺序存储表示第15页/共212页 用一组连续的存储单元存储二叉树的数用一组连续的存储单元存储二叉树的数据元素据元素,以结点存储的相对位置表示结点之以结点存储的相对位置表示结点之间的关系。间的关系。为了正确地反映结点之间的关系为了正确地反映结点之间的关系,任何任何二叉树都必须按照二叉树都必须按照完全二叉树完全二叉树的形式来存储的形式来存储.这种存储方式对某些二叉树的存储会造成这种存储方式对某些二叉树的存储会造成存储空间的浪费。存储空间的浪费。顺序存储结构顺序存储结构第16页/共212页 在高级语言中在高级语言中,可以用一维数组来描述可以用一维数组来描述这种顺序存储结构。这种顺序存储结构。例如：例如：ABCDFABCDE完全二叉树的顺序存储存储位置123456数据元素ABCDEF一般二叉树的存储存储位置123456数据元素ABCDNOTES:代表空元素第17页/共212页#defineMAX_TREE_SIZE100/二叉树的最大结点数二叉树的最大结点数TElemTypeSqBiTreeMAX_TREE_SIZE;/1号单元存储根结点号单元存储根结点例如例如:ABDCEF1234567891011121314ABCDEF第18页/共212页练习：练习：1已知一棵完全二叉树有已知一棵完全二叉树有64个叶子结点，则该树可能达个叶子结点，则该树可能达到的最大深度为（）到的最大深度为（）A7B8C9D102若一棵二叉树有若一棵二叉树有11个叶子结点，则该二叉树中度为个叶子结点，则该二叉树中度为2的结点个数是（）的结点个数是（）A10B11C12D不确定的不确定的3.已知一棵二叉树的顺序存储序列为：已知一棵二叉树的顺序存储序列为：aebfcd，则：，则：1）e的左孩子是哪个结点？右孩子是哪个结点？的左孩子是哪个结点？右孩子是哪个结点？2）d的双亲是哪个结点？的双亲是哪个结点？答案：B答案：A答案：1）没有左孩子；右孩子是f；2）b；第19页/共212页练习：练习：3 3假设一棵二叉树的顺序存储结构如图所示，假设一棵二叉树的顺序存储结构如图所示，请回答下列问题：请回答下列问题：（1 1）哪个结点是根结点？）哪个结点是根结点？（2 2）哪些结点是叶子结点？）哪些结点是叶子结点？（3 3）哪些结点是）哪些结点是H H的祖先？的祖先？（4 4）哪些结点是）哪些结点是B B的兄弟？的兄弟？（5 5）树的深度是多少？）树的深度是多少？ABCDE H1234567891011121314A AD,HD,HA,C,EA,C,EC C4 4第20页/共212页二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2三叉链表三叉链表第21页/共212页二叉链结构二叉链结构 每个结点包含三个域每个结点包含三个域:数据域和左右指数据域和左右指针域针域,如下表所示如下表所示lchilddatarchildADEBCF root二叉链表二叉链表第22页/共212页structBTNodedatatypedata;structBTNode*lchild,*rchild;TypedefBTNode*BTree;将二叉树类型将二叉树类型BTreeBTree定义为指向二叉链表结点结构定义为指向二叉链表结点结构的指针类型。的指针类型。lchilddatarchild结点结构结点结构:C语言的类型描述如下语言的类型描述如下:第23页/共212页三叉链表三叉链表 三叉链表结构：每个结点除包含数据域和左右指三叉链表结构：每个结点除包含数据域和左右指针域外针域外,还包含一个指向其双亲结点的指针域。还包含一个指向其双亲结点的指针域。rootADEBCF parentlchilddatarchild第24页/共212页structTriTNode/结点结构结点结构datatypedata;structTriTNode*lchild,*rchild;/左右孩子指针左右孩子指针structTriTNode*parent;/双亲指针双亲指针typedefTriTNode*TriTree;parentlchilddatarchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:第25页/共212页v 在这两种结构中在这两种结构中,只需要给出指向根结点只需要给出指向根结点的指针的指针,即可访问树中任意一个结点即可访问树中任意一个结点.v 尽管在二叉表中无法由结点直接找到其尽管在二叉表中无法由结点直接找到其双亲，但由于二叉链表的结构灵活，操作双亲，但由于二叉链表的结构灵活，操作方便，对于一般情况下的二叉树，甚至比方便，对于一般情况下的二叉树，甚至比顺序存储结构还节省空间。因此二叉链表顺序存储结构还节省空间。因此二叉链表是最常用的二叉树存储方式。是最常用的二叉树存储方式。今后，我们所涉及到的二叉树，如不今后，我们所涉及到的二叉树，如不加特别说明均采用二叉链表存储。加特别说明均采用二叉链表存储。说明说明第26页/共212页二叉树的遍历二叉树的遍历第27页/共212页 遍历二叉树遍历二叉树是指按照是指按照一定的规律一定的规律对对二叉树中的二叉树中的每个结点每个结点，访问且仅访问，访问且仅访问一一次次的处理过程。的处理过程。“访问访问”的含义可以很广，如：求结点的的含义可以很广，如：求结点的度、层次、输出结点的信息等等。度、层次、输出结点的信息等等。第28页/共212页“遍历遍历”是任何类型均有的操作，是任何类型均有的操作，1 1）对线性结构而言，只有一条搜索路径）对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继因为每个结点均只有一个后继)，故不需要，故不需要另加讨论。另加讨论。2 2）而二叉树是非线性结构，每个结点有）而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的两个后继，则存在如何遍历即按什么样的搜搜索路径索路径进行进行遍历的问题。遍历的问题。第29页/共212页对对“二二叉叉树树”而而言言，可可以以把把二二叉叉树树看看成成由由三三个个基基本本单单元元组组成成:根根结结点点(D)(D)、左左子子树树(L)(L)、右右子子树树(R),(R),并并且且规规定定左左子子树树上上的的所所有有结结点点应应该该在在右右子子树树上上的的所所有有结结点点之之前前被被访访问问,由由此此可可以以得得到到三三种种遍遍历历顺顺序序:先先序序遍遍历历(DLR)(DLR)、中序遍历、中序遍历(LDR)(LDR)、后序遍历、后序遍历(LRD)(LRD)先先序的遍历算法中中序的遍历算法后后序的遍历算法遍历算法遍历算法第30页/共212页若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树。）先序遍历右子树。先序的遍历算法：先序的遍历算法：ABCDEGF先序遍历：ABDEGCF第31页/共212页若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。中序的遍历算法：中序的遍历算法：ABCDEGF中序遍历：DBGEACF第32页/共212页若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。后序的遍历算法：后序的遍历算法：ABCDEGF后序遍历：DGEBFCA第33页/共212页ABCEDGFH先序遍历：中序遍历：后序遍历：ABDGCEHFBGDAHECFGDBHEFCA例题例题第34页/共212页中序遍历：先序遍历：后序遍历：a+b*cde/f-+a*bcd/efabcd-*+ef/-例题例题+/e*bfacd()第35页/共212页根据遍历序列画二叉树根据遍历序列画二叉树由一棵二叉树的由一棵二叉树的先序序列和中序序列先序序列和中序序列或或中序和后序中序和后序能够唯一确定一棵二叉树。能够唯一确定一棵二叉树。先序序列：先序序列：ABCDEFGHI中序序列：中序序列：BCAEDGHFIABDECFIGH第36页/共212页练习练习已知一棵二叉树的已知一棵二叉树的先序序列和中序序列先序序列和中序序列，请，请画出该二叉树。画出该二叉树。先序序列：先序序列：ABCDEFGHIJ中序序列：中序序列：CBEDFAHGJIABGHDIJCEF第37页/共212页树和森林树和森林 第38页/共212页树的存储结构树的存储结构一、双亲表示法一、双亲表示法二、孩子链表表示法二、孩子链表表示法三、树的二叉链表三、树的二叉链表(孩子孩子-兄弟）兄弟）存储表示法存储表示法第39页/共212页树的双亲表示法树的双亲表示法 以一组连续空间以一组连续空间(数组数组)存储树的结点存储树的结点,同时同时在每个结点中附设一个指示器指示其双亲结点在每个结点中附设一个指示器指示其双亲结点在数组中的位置在数组中的位置.typedefstructdatatypedata;intparent;Node;typedefNodeTreeMAX_NODE_NUM#defineMAX_NODE_NUM100C C语言的类型描述语言的类型描述:ABCDEFG0A-11B02C03D04E25F26G5dataparent第40页/共212页孩子表示法孩子表示法 存储每个结点及其孩子信息。每个结点的所有存储每个结点及其孩子信息。每个结点的所有孩子结点形成该结点的孩子链表。孩子结点形成该结点的孩子链表。ABCDEFG0A1B2C3D4E5F6G65123孩子链表孩子链表0A1B2C3D4E5F6G-1000224645123带双亲的孩子链带双亲的孩子链表表4第41页/共212页孩子孩子-兄弟表示法兄弟表示法structTreeNodedatatypedata;structTreeNode*children;structTreeNode*next;typedefstructTree;C C语言的类型描述语言的类型描述:结点结构结点结构:每个结点除其信息域外，再增加两个分别指向每个结点除其信息域外，再增加两个分别指向该结点的该结点的第一个孩子结点第一个孩子结点和和下一个兄弟结点下一个兄弟结点的指针。的指针。childrendatanext第42页/共212页孩子孩子-兄弟表示法兄弟表示法第43页/共212页树、森林与二叉树树、森林与二叉树之间的转换之间的转换 第44页/共212页将树转换成二叉树的方法将树转换成二叉树的方法l加线：在兄弟之间加一连线加线：在兄弟之间加一连线l抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系l旋转：以树的根结点为轴心，将整树顺时针转旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空第45页/共212页将二叉树转换成树将二叉树转换成树l加线：若加线：若p p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p p的右孩子，右孩子的右孩子，的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与p p的双亲用线连起来的双亲用线连起来l抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线l调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI第46页/共212页ABCDEFGHIABCDEFGHI树的树的先序遍历先序遍历和和后序遍历后序遍历可以借用二叉可以借用二叉树的树的先序遍历先序遍历和和中序遍历中序遍历的算法来实现。的算法来实现。先序序列：先序序列：ABEFGCDHIABEFGCDHI后序序列：后序序列：EFGBCHIDAEFGBCHIDA先序序列：先序序列：ABEFGCDHIABEFGCDHI中序序列：中序序列：EFGBCHIDAEFGBCHIDA后序序列：后序序列：GFEIHDCBAGFEIHDCBA树树二叉树二叉树第47页/共212页森林转换成二叉树l将各棵树分别转换成二叉树l将每棵树的根结点用线相连l以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第48页/共212页二叉树二叉树转换成森林转换成森林l抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树有右孩子间连线全部抹掉，使之变成孤立的二叉树l还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第49页/共212页由此，树和森林的各种操作均可与二叉树的各种操作相对应。应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟左是孩子，右是兄弟第50页/共212页把下面的树转化成二叉树。把下面的树转化成二叉树。ABCDEFGHI练习练习KLJABCDEFGHIJKL第51页/共212页哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码第52页/共212页相关概念相关概念树的路径长度树的路径长度定义为：定义为：树中每个结点的路径长度之和。树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为：定义为：从根结点到该结点的路径上分支的数目。从根结点到该结点的路径上分支的数目。树的带权路径长度树的带权路径长度定义为：定义为：树中所有树中所有叶子结点的带权路径叶子结点的带权路径长度长度之和之和WPL(T)=wklk(对所有叶子结点对所有叶子结点)结点的带权路径长度结点的带权路径长度定义为：定义为：从根结点到该结点的路径长度与结点上权从根结点到该结点的路径长度与结点上权的乘积。的乘积。第53页/共212页设：a,b,c,d的权值为：a=7,b=5,c=2,d=4;下面三棵不同的树的带权路径长度为：(7+5+4+2）*2=36(7+5)*3+4*2+2=467+5*2+(2+4)*3=35第第3 3棵树棵树的带权路径长度最小。的带权路径长度最小。第54页/共212页最优二叉树:设有n个权值w1,w2,w3,.,wn,构造有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树(赫夫曼树).赫夫曼树的应用：判定问题。例：将学生的百分制变成五级分制：设学生的成绩分布在五个等级上是不均匀的。分数分数0-590-5960-6960-6970-7970-7980-8980-8990-10090-100五级分制五级分制不及格不及格及格及格中中良良优优比例比例0.050.050.150.150.40.40.30.30.10.1第55页/共212页二、如何构造最优树二、如何构造最优树赫夫曼算法:(1)根据给定的n个权值w1,w2,w3,.,wn构成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空.(2)在集合F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和.(3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.第56页/共212页9例如:已知权值 W=5,6,2,9,756275276976713952795271667132900001111000111100101(1)根据给定的n个权值w1,w2,w3,.,wn构成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空.(2)在集合F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和.(3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.第57页/共212页哈夫曼编码通信中的信息传递问题：在传递信息时，如何在能够识别的前提下，使传递的字符数最少。例：电报中的报文“ABACCDA”四个字符的编码问题。两位编码：00011011如果用不同长度的编码：例用010001前缀编码:对于不等长编码,若任一个字符的编码都不是另一个字符的编码的前缀,则这种编码称为前缀编码.前缀编码使得字符编码的平均长度最短.赫夫曼编码是一种前缀编码.赫夫曼编码的方法:(1)把字符出现的频率作为权值,根据这些权值构造一棵赫夫曼树.(2)约定在赫夫曼树中,左分支表示字符0,右分支表示字符1,则从根结点到叶子结点的路径上的分支字符组成的字符串即为该叶子结点字符的编码.第58页/共212页 已知某系统在通信联系中只可能出现已知某系统在通信联系中只可能出现8 8种字符：种字符：abcdefghabcdefgh，其概率分别为，其概率分别为0.050.05，0.290.29，0.07，0.08，0.140.14，0.23,0.030.23,0.03，0.110.11，试据此构造哈夫，试据此构造哈夫曼树，要求：曼树，要求：1)1)画出构造哈夫曼树的过程；画出构造哈夫曼树的过程；2)2)求每个字符的哈夫曼编码。求每个字符的哈夫曼编码。例题例题哈夫曼编码：哈夫曼编码：a:0110b:10c:1110d:1111bfhagcd2311e5291437801000000111111e:110f:00g:0111h:010第59页/共212页设权值序列为设权值序列为8，5，3，4，7，据此构造一棵哈夫曼树。，据此构造一棵哈夫曼树。画出构造哈夫曼树过程。画出构造哈夫曼树过程。练习练习58347第60页/共212页习习 题题 一一第61页/共212页1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。A15 B16 C17 D472.深度为5的二叉树至多有_个结点。A.16 B.32 C.31 D.103.对一个满二叉树，m个树叶，n个结点，深度为h，则_。A.n=h+m B.h+m=2n C.m=h-1 D.n=2 h-1答案：B C D第62页/共212页4.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_。A.正确 B.错误5.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca6.在一非空二叉树的中序遍历序列中，根结点的右边_。A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点答案：A D A第63页/共212页7.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对答案：A第64页/共212页8.有一棵树如图所示，回答下面的问题：这棵树的根结点是_；这棵树的叶子结点是_；结点k3的度是_；这棵树的度是_；这棵树的深度是_；结点k3的子女是_；结点k3的父结点是_；k1k7k5k2k4k6k31.k1k2,k5,k7,k4234k5,k6k1第65页/共212页9.9.一棵二叉树的结点数据采用顺一棵二叉树的结点数据采用顺序存储结构，存储于数组序存储结构，存储于数组t t中，中，如图所示，则该二叉树的链接表如图所示，则该二叉树的链接表示形式为示形式为_ _ _。10.深度为k的完全二叉树至少有_个结点。至多有_个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_。1 12 23 34 45 56 67 78 89 9 1010 1111 1212 1313 1414 1515 1616 1717 1818 1919 2020 2121e ea af fd dg gc cj jl lh hb beaEfjcdlghb2k-1、2k-1、2k-1第66页/共212页11.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。aaaaacccccbbbbbbEBEFAECDKGHIJ图6.12第67页/共212页以数据集4，5，6，7，10，12，18为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。623725191813121096745图6.16Huffman树第68页/共212页习题二习题二1.三个结点的二叉树的基本形态有 种，三个结点的树的基本形态有 种。2一棵具有64个结点的完全二叉树的高度为 。3.设一棵二叉树的先序遍历序列为ABCDFEGH，中序遍历序列为BAFDCGEH，请完成下列要求：1）画出该二叉树；2）写出该二叉树的后序遍历序列；3）将该二叉树转换成森林；第69页/共212页习题习题4.已知一棵二叉树的顺序存储结构如下图所示，图中“0”表示不存在的结点，1）画出该二叉树；2）求该二叉树的先序遍历序列和中序遍历序列；3）将该二叉树转换成一棵树。5.设字符集为A，B，C，D，E，其对应的权值为7，5，2，4，9，据此构造哈夫曼树，要求：1）画出构造哈夫曼树过程；2）求每个字符的哈夫曼编码；A B 0 C D 0 0 E 0 F G第70页/共212页本章复习要点本章复习要点1、树的基本概念；、树的基本概念；结点、结点的度、树的度、叶子结点、分支结点、路径、孩子、结点、结点的度、树的度、叶子结点、分支结点、路径、孩子、双亲、结点的层次、树的深度、兄弟、堂兄弟双亲、结点的层次、树的深度、兄弟、堂兄弟2、二叉树的基本概念：二叉树、满二叉树、完全二叉树；、二叉树的基本概念：二叉树、满二叉树、完全二叉树；3、二叉树的、二叉树的5个性质；个性质；4、具有、具有3个结点的二叉树的个结点的二叉树的5种形态；种形态；3个结点的树的个结点的树的2种种的形态；的形态；5、理解二叉树的顺序存储结构；根据二叉树的顺序存储、理解二叉树的顺序存储结构；根据二叉树的顺序存储结构画二叉树；结构画二叉树；6、二叉树的先序、中序和后序遍历；根据先序和中序遍、二叉树的先序、中序和后序遍历；根据先序和中序遍历的序列画二叉树；历的序列画二叉树；7、构造哈夫曼树，写出哈夫曼编码；、构造哈夫曼树，写出哈夫曼编码；8、树、森林、二叉树的互相转换；、树、森林、二叉树的互相转换；第71页/共212页 1.B 2.B 3.C 4.C 1.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_。A.正确 B.错误2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。A15 B16 C17 D473.按照二叉树的定义，具有3个结点的不同形状的二叉树有_种。A.3 B.4 C.5 D.64.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_种。A.5 B.6 C.30 D.32 第72页/共212页5.C 7.D 8.A 5.深度为5的二叉树至多有_个结点。A.16 B.32 C.31 D.107.对一个满二叉树，m个树叶，n个结点，深度为h，则_。A.n=h+m B.h+m=2n C.m=h-1 D.n=2 h-18.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 第73页/共212页9.C 10.A 11.D 9.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_。A.uwvts B.vwuts C.wuvts D.wutsv10.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_。A.正确 B.错误11.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca 第74页/共212页1.A 15.B 12.在一非空二叉树的中序遍历序列中，根结点的右边_。A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点15设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孙 第75页/共212页16.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A.acbed B.decab C.deabc D.cedba第76页/共212页18.如图6.3所示的4棵二叉树，_不是完全二叉树。(A)(B)(C)(D)图6.3(A)(B)(C)(D)图6.3第77页/共212页 第八章第八章 图图第78页/共212页图的基本概念图的基本概念图的定义：图的定义：一个图G是由两个集合V和E组成，V是有限的非空顶点集，E是V上的顶点对所构成的边集，分别用V（G）和E（G）来表示图中的顶点集和边集。用二元组G=（V，E）来表示图G。有向图与无向图有向图与无向图 若图若图G G中的每条边都是中的每条边都是有方向的，则称有方向的，则称G G为为有向图有向图。有向边也称。有向边也称为为弧弧。若图。若图G G中的每条边都是没有方向的，中的每条边都是没有方向的，则称则称G G为为无向图无向图。第79页/共212页完全图完全图 对有对有n n个顶点的图，若为无向图且个顶点的图，若为无向图且边数为边数为n(n-1)/2n(n-1)/2，则称其为，则称其为无向完全图无向完全图；若为有向图且边数为若为有向图且边数为n(n-1)n(n-1)，则称其为，则称其为有有向完全图。向完全图。邻接顶点邻接顶点 若（若（v vi i,v,vj j）是一条无向边，则称）是一条无向边，则称顶点顶点v vi i和和v vj j互为邻接点，或称互为邻接点，或称v vi i和和v vj j相邻接，相邻接，并称边（并称边（v vi i,v,vj j）关联于顶点）关联于顶点v vi i和和v vj j，或称，或称（v vi i,v,vj j）与顶点）与顶点v vi i和和v vj j相关联。若（相关联。若（v vi i,v,vj j）是一条弧，则称顶点）是一条弧，则称顶点v vi i邻接至顶点邻接至顶点v vj j,顶顶点点v vj j邻接至顶点邻接至顶点v vi,i,。弧（。弧（v vi i,v,vj j）与顶点）与顶点v vi i、v vj j关联。关联。第80页/共212页n n顶点的度顶点的度顶点的度顶点的度 一个顶点一个顶点一个顶点一个顶点v v的度是与它相关联（依附）的度是与它相关联（依附）的度是与它相关联（依附）的度是与它相关联（依附）的边的条数。的边的条数。的边的条数。的边的条数。顶点顶点顶点顶点 v v的入度的入度的入度的入度 是以是以是以是以 v v为终点的有向边的条数。为终点的有向边的条数。为终点的有向边的条数。为终点的有向边的条数。顶点顶点顶点顶点 v v的出度的出度的出度的出度是以是以是以是以 v v为始点的有向边的条数。为始点的有向边的条数。为始点的有向边的条数。为始点的有向边的条数。有向图的顶点的度有向图的顶点的度有向图的顶点的度有向图的顶点的度等于它的入度与出度之和。等于它的入度与出度之和。等于它的入度与出度之和。等于它的入度与出度之和。n n子图子图子图子图 设有两个图设有两个图设有两个图设有两个图 GG(V,E)(V,E)和和和和 GG(V,E)(V,E)。若。若。若。若 VV VV且且且且 EE E,E,则称则称则称则称 图图图图GG是是是是 图图图图GG的子图。的子图。的子图。的子图。第81页/共212页 路径路径路径路径 在图在图在图在图 G G G G(V V V V,E E E E)中中中中,若存在一个顶点序列若存在一个顶点序列若存在一个顶点序列若存在一个顶点序列 v v v vp p p p1 1 1 1,v v v vp p p p2 2 2 2,v v v vpmpmpmpm，使得，使得，使得，使得(v v v vi i i i,v v v vp p p p1 1 1 1)、(v v v vp p p p1 1 1 1,v v v vp p p p2 2 2 2)、.、(v v v vpmpmpmpm,v v v vj j j j)均属于均属于均属于均属于E E E E，则称顶点则称顶点则称顶点则称顶点v v v vi i i i到到到到v v v vj j j j存在一存在一存在一存在一 条路径。若一条路径上除了条路径。若一条路径上除了条路径。若一条路径上除了条路径。若一条路径上除了v v v vi