数据结构第二讲课件

数据结构第二讲数据结构第二讲6、黄金时代是在我们的前面，而不在我们的后面。7、心急吃不了热汤圆。8、你可以很有个性，但某些时候请收敛。9、只为成功找方法，不为失败找借口(蹩脚的工人总是说工具不好)。10、只要下定决心克服恐惧，便几乎能克服任何恐惧。因为，请记住，除了在脑海中，恐惧无处藏身。-戴尔卡耐基。（1）树的基本概念）树的基本概念结点、结点的度、叶子（终端结点）、分支结结点、结点的度、叶子（终端结点）、分支结点（非终端结点）、树的度、孩子、双亲、兄点（非终端结点）、树的度、孩子、双亲、兄弟、子孙、层次、堂兄弟、树的深度、森林等弟、子孙、层次、堂兄弟、树的深度、森林等等。等。6（2）二叉树的概念及基本性质）二叉树的概念及基本性质二叉树概念二叉树概念 二叉树是有限的结点集合。二叉树是有限的结点集合。这个集合或者是空。这个集合或者是空。或或者者由由一一个个根根结结点点和和两两棵棵互互不不相相交交的的称称为为左左子子树树和和右子树右子树的二叉树组成。的二叉树组成。7二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点LRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树NNN8 在在一一棵棵二二叉叉树树中中,如如果果所所有有分分支支结结点点都都有有左左孩孩子子结结点点和和右右孩孩子子结结点点,并并且且叶叶结结点点都都集集中中在在二二叉叉树树的的最最下下一一层层,这这样的二叉树称为样的二叉树称为满二叉树满二叉树。9 若若二二叉叉树树中中最最多多只只有有最最下下面面两两层层的的结结点点的的度度数数可可以以小小于于2,并并且且最最下下面面一一层层的的叶叶结结点点都都依依次次排排列列在在该该层层最左边的位置上最左边的位置上,则这样的二叉树称为则这样的二叉树称为完全二叉树完全二叉树。完全二叉树完全二叉树10二叉树性质二叉树性质 性质性质1 非空二叉树上叶结点数等于双分支结点数加非空二叉树上叶结点数等于双分支结点数加1。证证明明：设设二二叉叉树树上上叶叶结结点点数数为为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+111 性性质质2 非非空空二二叉叉树树上上第第i层层上上至至多多有有2i-1个个结结点点,这这里应有里应有i1。性质性质3 高度为高度为h的二叉树至多有的二叉树至多有2h-1个结点个结点(h1)。12 性质性质4 具有具有n个个(n0)结点的完全二叉树的高度为结点的完全二叉树的高度为 log2(n+1)或或 log2n+1。由完全二叉树的定义和树的性质由完全二叉树的定义和树的性质4可推出。可推出。13 性性质质5 对对完完全全二二叉叉树树中中编编号号为为 i 的的结结点点(1in,n1,n为结点数为结点数)有：有：(1)若若i n/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)/2,它是双亲结点的右孩子结点。它是双亲结点的右孩子结点。152024/6/25ii+12i2i+12i+22i+3(a)i和和i+1结点在同一层结点在同一层i+12i+22i+3i2i2i+1(b)i和和i+1结点不在同一层结点不在同一层图图 完全完全二叉二叉树中结点树中结点i和和i+1的左右孩子的左右孩子161.1.一棵完全二叉树的第一棵完全二叉树的第6 6层有层有8 8个叶子结点，则该完个叶子结点，则该完全二叉树的结点个数最多为全二叉树的结点个数最多为。A.39A.39 B.52B.52 C.111C.111 D.119D.1192.2.在一棵度为在一棵度为4 4的树的树T T中，若有中，若有2020个度为个度为4 4的结点，的结点，1010个度为个度为3 3的结点，的结点，1 1个度为个度为2 2个结点，个结点，1010个度为个度为1 1的的结点，则树结点，则树T T中结点的总个数为中结点的总个数为。A.A.4141 B.82 C.113B.82 C.113 D.122D.122真题演练真题演练173.如图所示的4棵二叉树中，不是完全二叉树 C4.一棵二叉树的第k层最多有 个结点；一棵有n个结点的满二叉树共有 个叶子和 个非终端结点。18（3）树与二叉树的存储）树与二叉树的存储树的存储树的存储1、双亲存储结构、双亲存储结构2、孩子链存储结构、孩子链存储结构2、孩子兄弟链存储结构、孩子兄弟链存储结构二叉树的存储二叉树的存储1、顺序存储结构、顺序存储结构2、链式存储结构、链式存储结构192024/6/25第20页二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：对该树中二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号每个结点进行编号,其编号从小到大的顺序就是结点存放在其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。连续存储单元的先后次序。若把二叉树存储到一维数组中若把二叉树存储到一维数组中,则该编号就是下标值加则该编号就是下标值加1 1(注意注意,C/C+,C/C+语言中数组的起始下标为语言中数组的起始下标为0)0)。树中各结点的编。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。号与等高度的完全二叉树中对应位置上结点的编号相同。注意注意:从数组里第一个位置（即下标为0）开始存储只是指的一般的方法。而在实际操作时，可以根据需要或爱好从下标为1的位置开始存储，而下标为下标为0的位置存储其它信息。的位置存储其它信息。20A BCDEFGHIJK123456789101112131415顺序存储结构顺序存储结构01121ABCDEF2511437一般的二叉树先用一般的二叉树先用空结点空结点补全成为完全二叉树补全成为完全二叉树，然，然后对结点编号后对结点编号 AB D#C#E#F 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150622二叉树的链式存储结构二叉树的链式存储结构 在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下:typedef struct node ElemType data;struct node*lchild,*rchild;BTNode;其其中中,data表表示示值值域域,用用于于存存储储对对应应的的数数据据元元素素,lchild和和rchild分分别别表表示示左左指指针针域域和和右右指指针针域域,用用于于分分别别存存储储左左孩孩子子结结点点和和右右孩子结点孩子结点(即左、右子树的根结点即左、右子树的根结点)的存储位置。的存储位置。23二叉树及其链式存储结构二叉树及其链式存储结构 A B C E F D G A B C D E F G (a)(b)24真题演练真题演练下列存储方式中，哪一个不是树的存储形下列存储方式中，哪一个不是树的存储形式式 （）A.双亲表示法双亲表示法 B.孩子链表示法孩子链表示法 C.孩子兄弟链表示法孩子兄弟链表示法 D.顺序存储表示法顺序存储表示法D25（四）二叉树的遍历（四）二叉树的遍历 按照遍历时根结点被访问的次序不同，可将按照遍历时根结点被访问的次序不同，可将二叉树的遍历的分为三类：二叉树的遍历的分为三类：先序遍历，中序遍历先序遍历，中序遍历和后序遍历。和后序遍历。261.先序遍历过程先序遍历过程先序遍历二叉树的过程是：先序遍历二叉树的过程是：(1)访问根结点；访问根结点；(2)先序先序遍历左子树；遍历左子树；(3)先序先序遍历右子树。遍历右子树。272024/6/25第28页ABCDEFGHK先序序列：先序序列：A B C D EHGKF282.中序遍历过程中序遍历过程中序遍历二叉树的过程是：中序遍历二叉树的过程是：(1)中序遍历左子树；中序遍历左子树；(2)访问根结点；访问根结点；(3)中序遍历右子树。中序遍历右子树。29ABCDEFGHK中序序列：中序序列：ABCDE H G K F302024/6/25第31页3.后序遍历过程后序遍历过程后序遍历二叉树的过程是：后序遍历二叉树的过程是：(1)后序遍历左子树；后序遍历左子树；(2)后序遍历右子树；后序遍历右子树；(3)访问根结点。访问根结点。31ABCDEFGHK后序序列：后序序列：ABCDEHGKF32 除了上述给出的常用的三种遍历方法除了上述给出的常用的三种遍历方法外，实际上在考试中还有可能出现别的遍外，实际上在考试中还有可能出现别的遍历方法，根据我们所有历方法，根据我们所有根、左子树和右子根、左子树和右子树树的先后顺序，它们的不同序列应该有的先后顺序，它们的不同序列应该有六六种。种。NLR LNR LRN NRL RNL RLN如，某一年的考题如下：如，某一年的考题如下：33真题演练真题演练 给定一棵二叉树如图所示，其遍历序给定一棵二叉树如图所示，其遍历序列为列为3175624，则其遍历的方式是（，则其遍历的方式是（）A.LRN B.NRL C.RLN D.RNLD34 例如例如,已知先序序列为已知先序序列为ABDGCEF,中序序列为中序序列为DGBAECF,则构造二叉树的过程如下所示。则构造二叉树的过程如下所示。根结点：根结点：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左左中中序序:空空 左左根根:空空右右中中序序:空空 右右根根:空空根结点：根结点：B左左中中序序:DG 左左根根:D右右中中序序:空空 右右根根:空空根结点：根结点：C左左中中序序:E 左左根根:E右右中中序序:F 右右根根:F根结点：根结点：D左左中中序序:空空 左左根根:空空右右中中序序:G 右右根根:G根结点：根结点：E左左中中序序:空空 左左根根:空空右右中中序序:空空 右右根根:空空根结点：根结点：F左左中中序序:空空 左左根根:空空右右中中序序:空空 右右根根:空空36真题演练真题演练 若一棵二叉树的先序遍历序列是若一棵二叉树的先序遍历序列是aebdc，后序遍历序列是，后序遍历序列是bcdea，则根结，则根结点的孩子结点点的孩子结点 （）A.只有只有e B.有有eb C.有有ec D.无法确定无法确定A37树和二叉树的相互转换树和二叉树的相互转换 树树 二叉树二叉树 二叉二叉树树 树树（五）树、森林的遍历与二叉树的转换（五）树、森林的遍历与二叉树的转换树的左孩子是其原来树的左孩子是其原来最左边的孩子结点，树的最左边的孩子结点，树的右孩子是其右兄弟结点右孩子是其右兄弟结点38ABCDEFGHII将森林转换为二叉树的过程将森林转换为二叉树的过程39ABCDACBDABCD图图 二叉树还原成森林的过程二叉树还原成森林的过程(a)二叉树二叉树ABCDGLKHM(b)去连线后去连线后ABCDMGLKHMGLHK(c)还原成森林还原成森林ACBD40（六）线索二叉树（六）线索二叉树按照某种遍历序列，利用二叉链表中按照某种遍历序列，利用二叉链表中的结点的空指针，若是左指针为空，的结点的空指针，若是左指针为空，则该指针就指向其该种遍历下的前驱，则该指针就指向其该种遍历下的前驱，如果右指针为空，则指向其后继。指如果右指针为空，则指向其后继。指向前驱或后继的这些指针就称为线索。向前驱或后继的这些指针就称为线索。这样得到的二叉树序列就是某种序列这样得到的二叉树序列就是某种序列的线索二叉树。的线索二叉树。41真题演练真题演练 已知一个有已知一个有2011个结点的树，其叶子个结点的树，其叶子结点个数为结点个数为116，该树对应的二叉树中无右，该树对应的二叉树中无右孩子的结点个数为孩子的结点个数为（）A.115 B.116 C.1895 D.1896D42二叉树的线索化二叉树的线索化 起因：起因：因为二叉树的链式存储结构会有很因为二叉树的链式存储结构会有很多指针域为空，所以我们可以利用这些指多指针域为空，所以我们可以利用这些指针域。以二叉链表为例，如果左孩子存在，针域。以二叉链表为例，如果左孩子存在，则左指针指向其左孩子，否则指向其前驱；则左指针指向其左孩子，否则指向其前驱；若右孩子存在，则右指针指向其右孩子，若右孩子存在，则右指针指向其右孩子，否则右指针指向其后继。否则右指针指向其后继。由于在不同的遍历方式中，某结点的由于在不同的遍历方式中，某结点的前驱和后继也不同，因而可得出不同形式前驱和后继也不同，因而可得出不同形式的二叉线索树。的二叉线索树。430 A 00 E 0 0 C 00 F 0 0 B 0 0 D 00 G 0 0 A 01 E 10 C 01 F 10 /10 B 11 D 01 G 1中序线索化中序线索化中序遍历序列为：中序遍历序列为：DGBAECF44各种各种线线索二叉索二叉树树的好的好处处如下：如下：中序中序线线索索树树找找结结点的前点的前驱驱和后和后继继都方便都方便先序先序线线索化找后索化找后继继方便方便后序后序线线索化找前索化找前驱驱方便方便45真题演练真题演练下列线索二叉树中，符合后序线索树定义下列线索二叉树中，符合后序线索树定义的是（的是（）ABCDNULLABCDNULLNULLABCDNULL(1)(2)(3)D B C A46（七）树的应用（七）树的应用赫夫曼树赫夫曼树二叉排序树二叉排序树平衡二叉树平衡二叉树47赫夫曼树赫夫曼树 哈夫曼树的定义哈夫曼树的定义 设二叉树具有设二叉树具有n个带权值的叶子结点个带权值的叶子结点,那么那么从根结点到各个叶子结点的路径长度与相应结从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和点权值的乘积的和,叫做二叉树的带权路径长度。叫做二叉树的带权路径长度。其中其中,n表示叶子结点的数目表示叶子结点的数目,wi和和li分别表示分别表示叶子结点叶子结点ki的权值和根到的权值和根到ki之间的路径长度之间的路径长度(即即从叶子结点到达根结点的分支数从叶子结点到达根结点的分支数)。具有最小带权路径长度的二叉树称为哈夫具有最小带权路径长度的二叉树称为哈夫曼树。曼树。488W=0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.1152971481523311835191578294258100492914231183519157829425810000001001011113:0000 5:0001 11:001 7:10008:1111 23:01 29:10 14:110150真题演练真题演练1、对、对n（n=2）个权值均不相同的字符构造哈夫）个权值均不相同的字符构造哈夫曼树，关于概述的叙述，错误的是（曼树，关于概述的叙述，错误的是（）A.该树一定是一棵完全二叉树该树一定是一棵完全二叉树B.树中一定没有度为树中一定没有度为1的结点的结点C.树中两个权值最小的结点一定是兄弟结点树中两个权值最小的结点一定是兄弟结点D.树中任一非叶子结点的权值一定不小于下一层树中任一非叶子结点的权值一定不小于下一层任一结点的权值任一结点的权值A511、设有、设有6个有序表个有序表A、B、C、D、E、F，分别含有，分别含有10、35、40、50、60和和200个数据元素，各表个数据元素，各表中元素按升序排列。要求通过中元素按升序排列。要求通过5次两两合并，将次两两合并，将6个个表最终合并成表最终合并成1个升序表，并在最坏情况下比较的总个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。次数达到最小。请回答下列问题。（1）给出完整的合并过程，并求出最坏情况下比较的）给出完整的合并过程，并求出最坏情况下比较的总次数。总次数。（2）根据你的合并进程，描述）根据你的合并进程，描述n个不等长升序表的合个不等长升序表的合并策略，并说明理由。并策略，并说明理由。52解析：解析：（1）6个表的合并顺序如图所示：个表的合并顺序如图所示：1035402005060458539519511053 根据上图的赫夫曼树，6个有序表合并的过程可描述如下：a)表A和表B合并，生成45个元素的表AB；b)表AB和表C合并，生成含有85个元素的表ABC；c)表D和表E合并，生成含有110个元素的表DE；d)表ABC和表DE合并，生成具有195个元素的表ABCDE；e)表ABCDE和表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二叉排序树二叉排序树 二叉排序树二叉排序树(简称简称BST)又称二叉查找又称二叉查找(搜索搜索)树树,其其定义为：二叉排序树或者是空树定义为：二叉排序树或者是空树,或者是满足如下性质或者是满足如下性质的二叉树：的二叉树：(1)若若它它的的左左子子树树非非空空,则则左左子子树树上上所所有有记记录录的的值值均均小于小于根记录的值；根记录的值；(2)若若它它的的右右子子树树非非空空,则则右右子子树树上上所所有有记记录录的的值值均均大于大于根记录的值；根记录的值；(3)左、右子树本身又各是一棵二叉排序树。左、右子树本身又各是一棵二叉排序树。56503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不5750308020908540358832例如例如:二叉排序树查找过程二叉排序树查找过程查找关键字查找关键字=50,505035,503040355090,50809095 58 例例 9.2 已已 知知 一一 组组 关关 键键 字字 为为25,18,46,2,53,39,32,4,74,67,60,11。按按表表中中的的元元素素顺顺序序依依次次插插入入到到一一棵棵初初始始为为空空的的二二叉叉排排序序树树中中,画画出出该该二二叉叉排排序序树树,并并求求在在等等概概率率的的情情况况下下查查找找成功的平均查找长度。成功的平均查找长度。解解：生生成成的的二二叉叉排排序序树树如如右右图图所所示。示。二叉排序树查找的过程即为其创建的过程。每二叉排序树查找的过程即为其创建的过程。每一次的插入都是在叶子上进行的。一次的插入都是在叶子上进行的。59二叉排序树结点的删除二叉排序树结点的删除分为三种情况分为三种情况（1）被删除的结点是叶子结点被删除的结点是叶子结点（2）被删除的结点只有左子树或者只有右被删除的结点只有左子树或者只有右子树子树（3）被删除的结点既有左子树，也有右子被删除的结点既有左子树，也有右子树树60508020908540358832（1）被删除的结点是叶子结点：）被删除的结点是叶子结点：直接删去该结点。直接删去该结点。例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”306150308020908540358832（2）被删除的结点只有左子树或者只有右子树，用其左）被删除的结点只有左子树或者只有右子树，用其左子树或者右子树代替它。子树或者右子树代替它。其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被删除结点的左指向被删除结点的左子树或右子树子树或右子树”。被删关键字被删关键字=40806250308020908540358832（3）被删除的结点既有左子树，也有右子树）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除以其前驱替代之，然后再删除该前驱结点。前驱是左子树中该前驱结点。前驱是左子树中最大的结点。最大的结点。被删结点被删结点前驱结点前驱结点被删关键字被删关键字=5063真题演练真题演练（1）对下列关键字序列，不可能构成某二）对下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是叉排序树中一条查找路径的序列是（）A.95 22 91 24 94 71 B.92 90 91 34 88 35 C.21 89 77 29 36 38 D.12 25 71 68 33 34A64若一个查找序列是若一个查找序列是1 3 5 7 9 试画出根据该查找过程构造出的二叉试画出根据该查找过程构造出的二叉排序树，并计算其平均查找长度。排序树，并计算其平均查找长度。13579其平均查找长度为：其平均查找长度为：ASL=(1+2+3+4+5)/5=2.6将近表长的一半！将近表长的一半！65平衡二叉树平衡二叉树 平衡二叉树或者是空树，或者是满足下列性质的二叉树。：左子树和右子树深度之差的绝对值不大于1；：左子树和右子树也都是平衡二叉树。如果一棵二叉树既是二叉排序树又是平衡如果一棵二叉树既是二叉排序树又是平衡二叉树，称为平衡二叉排序树二叉树，称为平衡二叉排序树(Balanced Binary Sort Tree)。66平衡二叉树和不平衡二叉树平衡二叉树和不平衡二叉树 67 平平衡衡二二叉叉树树中中插插入入新新结结点点方方式式与与二二叉叉排排序序树树相相似似，只只是是插插入入后后可可能能破破坏坏了了平平衡衡二二叉叉树树的的平平衡衡性性,解决方法是调整。解决方法是调整。调整操作可归纳为下列四种情况：调整操作可归纳为下列四种情况：68 (1)LL型调整型调整单向右旋保平衡单向右旋保平衡B结点原来的右子树变为结点原来的右子树变为A结点的左子树结点的左子树69 LL调整调整542425LL插入关键字插入关键字2时破坏了平衡时破坏了平衡70 (2)RR型调整型调整单向左旋保平衡单向左旋保平衡B结点原来的左子树变为结点原来的左子树变为A结点的右子树结点的右子树71426589426895插入关键字插入关键字 9RR72 (3)LR型调整型调整先局部左旋，再向上右旋先局部左旋，再向上右旋7316插入插入7377调整以调整以16为根的为根的不平衡子树不平衡子树316LR型调整型调整RL74 (4)RL型调整型调整先局部右旋，再向上左旋先局部右旋，再向上左旋757311916调整以调整以7为根的为根的不平衡子树不平衡子树83971116插入插入8 (4)RL型调整型调整RL876 例例9.3 输输入入关关键键字字序序列列16,3,7,11,9,26,18,14,15,给给出出构构造一棵造一棵AVL树的步骤。树的步骤。7778删删除除结结点点和二叉排序和二叉排序树树中中删删除除结结点相似，只是要点相似，只是要调调整平衡，整平衡，调调整整时时和插入和插入结结点的点的调调整方式整方式类类似。似。79平衡二叉平衡二叉树树的重要性的重要性质质 含有含有N个个结点的平衡二叉点的平衡二叉树的最大高度的最大高度为O（log2n）,这主要从构造平衡二叉主要从构造平衡二叉树的的过程中得来。程中得来。首先，构造一系列的平衡二叉首先，构造一系列的平衡二叉树T1，T2，T3，其中，其中，Th是高度是高度为h且尽可能少的平衡二叉且尽可能少的平衡二叉树。所来我。所来我们可以得出可以得出规律，律，为了构造了构造TN，先分，先分别构造构造T(N-1)和和T（N-2)分分别作作为TN的左子的左子树和右子和右子树，80真真题题演演练练（1）如）如图所示的平衡二叉所示的平衡二叉树中插入关中插入关键字字48后得到一棵新的平衡二叉后得到一棵新的平衡二叉树，在新平衡，在新平衡二叉二叉树中，关中，关键字字37所在所在结点的左、右孩点的左、右孩子子结点中保存的关点中保存的关键字分字分别是是 （）A.13,48 B.24,48 C.24,53 D.24,902490133753C81(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.B8241、学问是异常珍贵的东西，从任何源泉吸收都不可耻。阿卜日法拉兹42、只有在人群中间，才能认识自己。德国43、重复别人所说的话，只需要教育；而要挑战别人所说的话，则需要头脑。玛丽佩蒂博恩普尔44、卓越的人一大优点是：在不利与艰难的遭遇里百折不饶。贝多芬45、自己的饭量自己知道。苏联