数据结构第二讲.ppt

《数据结构第二讲.ppt》由会员分享，可在线阅读，更多相关《数据结构第二讲.ppt（81页珍藏版）》请在三一办公上搜索。

1、1,第二讲 树与二叉树,2,本章出题特点,从09年到11年每年都是4个客观题，8分。2012年2道客观题，一道主观题题目难易跨度较大。知识点主要是操作细节和基本应用功能。主观题一般涉及的是特殊二叉树的应用。,3,知识归纳,4,本讲主要内容,树与二叉树的基本概念及性质（理解、应用）二叉树的遍历（掌握）树、森林与二叉树的转换（了解）线索二叉树（理解）二叉树的应用 二叉排序树（掌握）二叉平衡树（掌握）赫夫曼树（应用）,5,（1）树的基本概念,结点、结点的度、叶子（终端结点）、分支结点（非终端结点）、树的度、孩子、双亲、兄弟、子孙、层次、堂兄弟、树的深度、森林等等。,6,（2）二叉树的概念及基本性质,

2、二叉树概念 二叉树是有限的结点集合。这个集合或者是空。或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。,7,二叉树的五种基本形态：,N,空树,只含根结点,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,N,N,N,8,在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。,9,若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶结点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树。,完全二叉树,10,二叉树性质 性质1 非空二叉树上叶结点数等于双分支结点数加1。证明

3、：设二叉树上叶结点数为n0,单分支结点数为n1,双分支结点数为n2,则总结点数n=n0+n1+n2。根据树的性质1可知，一棵树的结点总数等于所有结点的度数加1，即 n=0*n0+1*n1+2*n2+1=n1+2n2+1 综上可得：n1+2n2+1=n0+n1+n2 即：n0=n2+1,11,性质2 非空二叉树上第i层上至多有2i-1个结点,这里应有i1。性质3 高度为h的二叉树至多有2h-1个结点(h1)。,12,性质4 具有n个(n0)结点的完全二叉树的高度为log2(n+1)或log2n+1。由完全二叉树的定义和树的性质4可推出。,13,性质5 对完全二叉树中编号为 i 的结点(1in,n

4、1,n为结点数)有：(1)若in/2,即2in,则编号为 i 的结点为分支结点,否则为叶子结点。(2)若n为奇数,则每个分支结点都既有左孩子结点,也有右孩子结点；若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子结点,没有右孩子结点,其余分支结点都有左、右孩子结点。,14,(3)若编号为i的结点有左孩子结点,则左孩子结点的编号为2i；若编号为i的结点有右孩子结点,则右孩子结点的编号为(2i+1)。(4)除树根结点外,若一个结点的编号为i,则它的双亲结点的编号为i/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子结点,当i为奇数时,其双亲结点的编号为(i-1)/

5、2,它是双亲结点的右孩子结点。,15,2023/6/29,16,1.一棵完全二叉树的第6层有8个叶子结点，则该完全二叉树的结点个数最多为。A.39 B.52 C.111 D.1192.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2个结点，10个度为1的结点，则树T中结点的总个数为。41 B.82 C.113 D.122,真题演练,17,3.如图所示的4棵二叉树中，不是完全二叉树,C,4.一棵二叉树的第k层最多有 个结点；一棵有n个结点的满二叉树共有 个叶子和 个非终端结点。,18,（3）树与二叉树的存储,树的存储1、双亲存储结构2、孩子链存储结构2、孩子兄弟链存储

6、结构二叉树的存储1、顺序存储结构2、链式存储结构,19,2023/6/29,第19页,二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号,其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中,则该编号就是下标值加1(注意,C/C+语言中数组的起始下标为0)。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。,注意:从数组里第一个位置（即下标为0）开始存储只是指的一般的方法。而在实际操作时，可以根据需要或爱好从下标为1的位置开始存储，而下标为0的位置存储其它信息。,20,顺序存储结构,11,21,A,B,C,D,E

7、,F,2,5,1,14,3,7,一般的二叉树先用空结点补全成为完全二叉树，然后对结点编号,22,二叉树的链式存储结构 在二叉树的链接存储中,结点的结构如下:typedef struct node ElemType data;struct node*lchild,*rchild;BTNode;其中,data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点(即左、右子树的根结点)的存储位置。,23,二叉树及其链式存储结构,A,B,C,D,E,F,G,(a),(b),24,真题演练,下列存储方式中，哪一个不是树的存储形式（）A

8、.双亲表示法 B.孩子链表示法 C.孩子兄弟链表示法 D.顺序存储表示法,D,25,（四）二叉树的遍历,按照遍历时根结点被访问的次序不同，可将二叉树的遍历的分为三类：先序遍历，中序遍历和后序遍历。,26,1.先序遍历过程先序遍历二叉树的过程是：(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。,27,2023/6/29,第27页,先序序列：,A,B,C,D,E,H,G,K,F,28,2.中序遍历过程中序遍历二叉树的过程是：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。,29,中序序列：,A,B,C,D,E,H,G,K,F,30,2023/6/29,第30页,3.后序

9、遍历过程后序遍历二叉树的过程是：(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。,31,后序序列：,A,B,C,D,E,H,G,K,F,32,除了上述给出的常用的三种遍历方法外，实际上在考试中还有可能出现别的遍历方法，根据我们所有根、左子树和右子树的先后顺序，它们的不同序列应该有六种。NLR LNR LRN NRL RNL RLN如，某一年的考题如下：,33,真题演练,给定一棵二叉树如图所示，其遍历序列为3175624，则其遍历的方式是（）A.LRN B.NRL C.RLN D.RNL,D,34,例如,已知先序序列为ABDGCEF,中序序列为DGBAECF,则构造二叉树的过程如下

10、所示。,根结点：A左先序:BDG 左中序:DGB右先序:CEF 右中序:ECF,根结点：B左先序:DG 左中序:DG右先序:空 右中序:空,根结点：D左先序:空 左中序:空右先序:G 右中序:G,根结点：G左先序:空 左中序:空右先序:空 右中序:空,根结点：E左先序:空 左中序:空右先序:空 右中序:空,根结点：C左先序:E 左中序:E右先序:F 右中序:F,根结点：F左先序:空 左中序:空右先序:空 右中序:空,35,例如,已知中序序列为DGBAECF,后序序列为GDBEFCA。对应的构造二叉树的过程如下所示。,根结点：A左中序:DGB 左根:B右中序:ECF 右根:C,根结点：G左中序:

11、空 左根:空右中序:空 右根:空,根结点：B左中序:DG 左根:D右中序:空 右根:空,根结点：C左中序:E 左根:E右中序:F 右根:F,根结点：D左中序:空 左根:空右中序:G 右根:G,根结点：E左中序:空 左根:空右中序:空 右根:空,根结点：F左中序:空 左根:空右中序:空 右根:空,36,真题演练,若一棵二叉树的先序遍历序列是aebdc，后序遍历序列是bcdea，则根结点的孩子结点（）A.只有e B.有eb C.有ec D.无法确定,A,37,树和二叉树的相互转换,树 二叉树 二叉树 树,（五）树、森林的遍历与二叉树的转换,树的左孩子是其原来最左边的孩子结点，树的右孩子是其右兄弟结

12、点,38,A,B,C,D,E,F,G,H,I,I,将森林转换为二叉树的过程,39,A,B,C,D,A,B,C,D,图 二叉树还原成森林的过程,40,（六）线索二叉树,按照某种遍历序列，利用二叉链表中的结点的空指针，若是左指针为空，则该指针就指向其该种遍历下的前驱，如果右指针为空，则指向其后继。指向前驱或后继的这些指针就称为线索。这样得到的二叉树序列就是某种序列的线索二叉树。,41,真题演练,已知一个有2011个结点的树，其叶子结点个数为116，该树对应的二叉树中无右孩子的结点个数为（）A.115 B.116 C.1895 D.1896,D,42,二叉树的线索化,起因：因为二叉树的链式存储结构会

13、有很多指针域为空，所以我们可以利用这些指针域。以二叉链表为例，如果左孩子存在，则左指针指向其左孩子，否则指向其前驱；若右孩子存在，则右指针指向其右孩子，否则右指针指向其后继。由于在不同的遍历方式中，某结点的前驱和后继也不同，因而可得出不同形式的二叉线索树。,43,中序线索化,中序遍历序列为：DGBAECF,44,各种线索二叉树的好处如下：,中序线索树找结点的前驱和后继都方便先序线索化找后继方便后序线索化找前驱方便,45,真题演练,下列线索二叉树中，符合后序线索树定义的是（）,A,B,C,D,NULL,NULL,A,B,C,D,NULL,(1),(2),(3),D B C A,46,（七）树的应

14、用,赫夫曼树二叉排序树平衡二叉树,47,赫夫曼树,哈夫曼树的定义 设二叉树具有n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和,叫做二叉树的带权路径长度。其中,n表示叶子结点的数目,wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度(即从叶子结点到达根结点的分支数)。具有最小带权路径长度的二叉树称为哈夫曼树。,48,8,W=0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,5,29,7,14,8,15,23,3,11,8,3,5,19,15,7,8,29,42,58,100,49,29,14,23,11,8,3,5,19

15、,15,7,8,29,42,58,100,0,0,0,0,1,0,0,1,0,1,1,1,1,3:0000 5:0001 11:001 7:10008:1111 23:01 29:10 14:110,1,50,真题演练,1、对n（n=2）个权值均不相同的字符构造哈夫曼树，关于概述的叙述，错误的是（）该树一定是一棵完全二叉树树中一定没有度为1的结点树中两个权值最小的结点一定是兄弟结点树中任一非叶子结点的权值一定不小于下一层任一结点的权值,A,51,1、设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表

16、最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。（1）给出完整的合并过程，并求出最坏情况下比较的总次数。（2）根据你的合并进程，描述n个不等长升序表的合并策略，并说明理由。,52,解析：,（1）6个表的合并顺序如图所示：,10,35,40,200,50,60,45,85,395,195,110,53,根据上图的赫夫曼树，6个有序表合并的过程可描述如下：a)表A和表B合并，生成45个元素的表AB；b)表AB和表C合并，生成含有85个元素的表ABC；c)表D和表E合并，生成含有110个元素的表DE；d)表ABC和表DE合并，生成具有195个元素的表ABCDE；e)表ABC

17、DE和表F合并，最后生成一个含有395个元素的最终表。,由于合并两个长度分别为m和n的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：第一次合并：10+35-1=44；第二次合并：45+40-1=84 第三次合并：50+60-1=109；第四次合并：85+110-1=19；第五次合并：195+200-1=394 因此，最多的比较次数是：825。,54,（2）合并策略是：,在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用赫夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下得合并效率。,55,二叉排序树,二叉排

18、序树(简称BST)又称二叉查找(搜索)树,其定义为：二叉排序树或者是空树,或者是满足如下性质的二叉树：(1)若它的左子树非空,则左子树上所有记录的值均小于根记录的值；(2)若它的右子树非空,则右子树上所有记录的值均大于根记录的值；(3)左、右子树本身又各是一棵二叉排序树。,56,50,30,80,20,90,10,85,40,35,25,23,88,例如:,是二叉排序树。,不,57,50,30,80,20,90,85,40,35,88,32,例如:二叉排序树查找过程,查找关键字,=50,50,50,35,50,30,40,35,50,90,50,80,90,95,58,例9.2 已知一组关键字

19、为25,18,46,2,53,39,32,4,74,67,60,11。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。解：生成的二叉排序树如右图所示。,二叉排序树查找的过程即为其创建的过程。每一次的插入都是在叶子上进行的。,59,二叉排序树结点的删除,分为三种情况（1）被删除的结点是叶子结点（2）被删除的结点只有左子树或者只有右子树（3）被删除的结点既有左子树，也有右子树,60,50,80,20,90,85,40,35,88,32,（1）被删除的结点是叶子结点：直接删去该结点。,例如:,被删关键字=20,88,其双亲结点中相应

20、指针域的值改为“空”,30,61,50,30,80,20,90,85,40,35,88,32,（2）被删除的结点只有左子树或者只有右子树，用其左子树或者右子树代替它。,其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。,被删关键字=40,80,62,50,30,80,20,90,85,40,35,88,32,（3）被删除的结点既有左子树，也有右子树,40,40,以其前驱替代之，然后再删除该前驱结点。前驱是左子树中最大的结点。,被删结点,前驱结点,被删关键字=50,63,真题演练,（1）对下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）A.95 22 91 24

21、94 71 B.92 90 91 34 88 35 C.21 89 77 29 36 38 D.12 25 71 68 33 34,A,64,若一个查找序列是1 3 5 7 9,试画出根据该查找过程构造出的二叉排序树，并计算其平均查找长度。,1,3,5,7,9,其平均查找长度为：ASL=(1+2+3+4+5)/5=2.6,将近表长的一半！,65,平衡二叉树,平衡二叉树或者是空树，或者是满足下列性质的二叉树。：左子树和右子树深度之差的绝对值不大于1；：左子树和右子树也都是平衡二叉树。,如果一棵二叉树既是二叉排序树又是平衡二叉树，称为平衡二叉排序树(Balanced Binary Sort Tre

22、e)。,66,平衡二叉树和不平衡二叉树,67,平衡二叉树中插入新结点方式与二叉排序树相似，只是插入后可能破坏了平衡二叉树的平衡性,解决方法是调整。调整操作可归纳为下列四种情况：,68,(1)LL型调整,单向右旋保平衡,B结点原来的右子树变为A结点的左子树,69,LL调整,5,4,2,4,2,5,L,L,插入关键字2时破坏了平衡,70,(2)RR型调整,单向左旋保平衡,B结点原来的左子树变为A结点的右子树,71,9,5,插入关键字 9,R,R,72,(3)LR型调整,先局部左旋，再向上右旋,73,16,插入7,3,7,7,调整以16为根的不平衡子树,3,16,LR型调整,R,L,74,(4)RL

23、型调整,先局部右旋，再向上左旋,75,7,3,11,9,16,调整以7为根的不平衡子树,8,3,9,7,11,16,插入8,(4)RL型调整,R,L,8,76,例9.3 输入关键字序列16,3,7,11,9,26,18,14,15,给出构造一棵AVL树的步骤。,77,78,删除结点,和二叉排序树中删除结点相似，只是要调整平衡，调整时和插入结点的调整方式类似。,79,平衡二叉树的重要性质,含有N个结点的平衡二叉树的最大高度为O（log2n）,这主要从构造平衡二叉树的过程中得来。首先，构造一系列的平衡二叉树T1，T2，T3，其中，Th是高度为h且尽可能少的平衡二叉树。所来我们可以得出规律，为了构造

24、TN，先分别构造T(N-1)和T（N-2)分别作为TN的左子树和右子树，,80,真题演练,（1）如图所示的平衡二叉树中插入关键字48后得到一棵新的平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右孩子结点中保存的关键字分别是（）A.13,48 B.24,48 C.24,53 D.24,90,24,90,13,37,53,C,81,(2)若平衡二叉树的高度为6，且所有非叶子结点的平衡因子均为1，则该二叉树中结点总数为（）A.12 B.20 C.32 D.33,解：设这样的高度为h的平衡二叉树中结点总数为Nh，则有：N1=1，N2=2，N3=N1+N2+1=4,N4=N2+N3+1=7,N5=N3+N4+1=12,N6=N4+N5+1=20.,B,