数据结构第二讲

1、1第二讲第二讲 树与二叉树树与二叉树2本章出题特点本章出题特点从从09年到年到11年每年都是年每年都是4个客观题，个客观题，8分。分。2012年年2道客观题，一道主观题道客观题，一道主观题题目难易跨度较大。知识点主要是操作细题目难易跨度较大。知识点主要是操作细节和基本应用功能。节和基本应用功能。主观题一般涉及的是特殊二叉树的应用。主观题一般涉及的是特殊二叉树的应用。3知识归纳树森林二叉树相关概念性质存储结构遍历方法特殊二叉树森林的遍历树的遍历顺序存储结构线索化链式存储结构赫夫曼树二叉排序树平衡二叉树先序遍历中序遍历层序遍历后序遍历4本讲主要内容本讲主要内容树与二叉树的基本概念及性质（树与二叉树

2、的基本概念及性质（理解、应用理解、应用）二叉树的遍历（二叉树的遍历（掌握掌握）树、森林与二叉树的转换（树、森林与二叉树的转换（了解了解）线索二叉树（线索二叉树（理解理解）二叉树的应用二叉树的应用 二叉排序树（二叉排序树（掌握掌握） 二叉平衡树（二叉平衡树（掌握掌握） 赫夫曼树（赫夫曼树（应用应用）5（1）树的基本概念）树的基本概念结点、结点的度、叶子（终端结点）、分支结结点、结点的度、叶子（终端结点）、分支结点（非终端结点）、树的度、孩子、双亲、兄点（非终端结点）、树的度、孩子、双亲、兄弟、子孙、层次、堂兄弟、树的深度、森林等弟、子孙、层次、堂兄弟、树的深度、森林等等。等。 A C G J B

3、 E D F I H M K L 6（2）二叉树的概念及基本性质）二叉树的概念及基本性质二叉树概念二叉树概念 二叉树是有限的结点集合。二叉树是有限的结点集合。 这个集合或者是空。这个集合或者是空。 或者由一个或者由一个根结点根结点和两棵互不相交的称为和两棵互不相交的称为左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。7二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点LRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树NNN8 在一棵二叉树中在一棵二叉树中,如果如果所有分支结点都有左孩子结点所有分支结点都有左孩子结点和右孩

4、子结点和右孩子结点,并且并且叶结点都集中在二叉树的最下一层叶结点都集中在二叉树的最下一层,这这样的二叉树称为样的二叉树称为满二叉树满二叉树。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 满二叉树满二叉树 9 若二叉树中最多若二叉树中最多只有最下面两层的结点的度数可只有最下面两层的结点的度数可以小于以小于2,并且并且最下面一层的叶结点都依次排列在该层最下面一层的叶结点都依次排列在该层最左边的位置上最左边的位置上,则这样的二叉树称为则这样的二叉树称为完全二叉树完全二叉树。 A B C D E H I J K F

5、 G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树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+n

6、2 即：即：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,则

7、编号为则编号为 i 的结点为分支结点的结点为分支结点,否则为叶子结点。否则为叶子结点。 (2) 若若n为奇数为奇数,则每个分支结点都既有左孩子结点则每个分支结点都既有左孩子结点,也也有右孩子结点；若有右孩子结点；若n为偶数为偶数,则编号最大的分支结点则编号最大的分支结点(编编号为号为n/2)只有左孩子结点只有左孩子结点,没有右孩子结点没有右孩子结点,其余分支结其余分支结点都有左、右孩子结点。点都有左、右孩子结点。14 (3) 若编号为若编号为i的结点有左孩子结点的结点有左孩子结点,则左孩子结点的编则左孩子结点的编号为号为2i；若编号为；若编号为i的结点有右孩子结点的结点有右孩子结点,则右孩子结

8、点的则右孩子结点的编号为编号为(2i+1)。 (4) 除树根结点外除树根结点外, 若一个结点的编号为若一个结点的编号为i, 则它的双亲则它的双亲结点的编号为结点的编号为 i/2 , 也就是说也就是说,当当i为偶数时为偶数时, 其双亲结点的其双亲结点的编号为编号为i/2,它是双亲结点的左孩子结点它是双亲结点的左孩子结点, 当当i为奇数时为奇数时,其双其双亲结点的编号为亲结点的编号为(i-1)/2, 它是双亲结点的右孩子结点。它是双亲结点的右孩子结点。152022-3-21ii+12i2i+12i+22i+3(a) i和和i+1结点在同一层结点在同一层i+12i+22i+3i2i2i+1(b) i

9、和和i+1结点不在同一层结点不在同一层图图 完全完全二叉二叉树中结点树中结点i和和i+1的左右孩子的左右孩子2/ i161.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的结点，则树的结点，则

10、树T T中结点的总个数为中结点的总个数为。A.A.4141 B. 82 C. 113B. 82 C. 113 D. 122D. 122真题演练真题演练173.如图所示的4棵二叉树中， 不是完全二叉树 C4.一棵二叉树的第k层最多有 个结点；一棵有n个结点的满二叉树共有 个叶子和 个非终端结点。12k2) 1( n2) 1( n18（3）树与二叉树的存储）树与二叉树的存储树的存储树的存储1、双亲存储结构、双亲存储结构2、孩子链存储结构、孩子链存储结构2、孩子兄弟链存储结构、孩子兄弟链存储结构二叉树的存储二叉树的存储1、顺序存储结构、顺序存储结构2、链式存储结构、链式存储结构192022-3-21

11、第19页二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：对该树二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号中每个结点进行编号, ,其编号从小到大的顺序就是结点存放其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。在连续存储单元的先后次序。 若把二叉树存储到一维数组中若把二叉树存储到一维数组中, ,则该编号就是下标值加则该编号就是下标值加1 1( (注意注意,C/C+,C/C+语言中数组的起始下标为语言中数组的起始下标为0)0)。树中各结点的编。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。号与等高度的完全二叉树中对

12、应位置上结点的编号相同。 注意注意: 从数组里第一个位置（即下标为0）开始存储只是指的一般的方法。而在实际操作时，可以根据需要或爱好从下标为1的位置开始存储，而下标为下标为0的位置存储其它信息。的位置存储其它信息。20 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 A BCDEFGHIJK123456789101112131415顺序存储结构顺序存储结构01121ABCDEF2511437一般的二叉树先用一般的二叉树先用空结点空结点补全成为完全二叉树补全成为完全二叉树，然，然后对结点编号后对结点编号 AB D # C # E

13、# # # # # # 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分别表示左指针域和右指针域分别表示左指针域和右指针域,用于分别存储左孩子结点和右用于分别存储左孩子结点和右孩子结点孩子结点(

14、即左、右子树的根结点即左、右子树的根结点)的存储位置。的存储位置。23二叉树及其链式存储结构二叉树及其链式存储结构 A B C E F D G A B C D E F G (a) (b) 24真题演练真题演练下列存储方式中，哪一个不是树的存储形下列存储方式中，哪一个不是树的存储形式式 （ ） A. 双亲表示法双亲表示法 B. 孩子链表示法孩子链表示法 C. 孩子兄弟链表示法孩子兄弟链表示法 D. 顺序存储表示法顺序存储表示法D25（四）二叉树的遍历（四）二叉树的遍历 按照遍历时根结点被访问的次序不同，可将按照遍历时根结点被访问的次序不同，可将二叉树的遍历的分为三类：二叉树的遍历的分为三类：先序

15、遍历，中序遍历先序遍历，中序遍历和后序遍历。和后序遍历。261. 先序遍历过程先序遍历过程先序遍历二叉树的过程是：先序遍历二叉树的过程是：(1) 访问根结点；访问根结点；(2) 先序先序遍历左子树；遍历左子树；(3) 先序先序遍历右子树。遍历右子树。272022-3-21第27页ABCDEFGHK先序序列：先序序列：A B C D EHGKF282. 中序遍历过程中序遍历过程中序遍历二叉树的过程是：中序遍历二叉树的过程是：(1) 中序遍历左子树；中序遍历左子树；(2) 访问根结点；访问根结点；(3) 中序遍历右子树。中序遍历右子树。29ABCDEFGHK中序序列：中序序列：ABCDE H G

16、K F302022-3-21第30页3. 后序遍历过程后序遍历过程后序遍历二叉树的过程是：后序遍历二叉树的过程是：(1) 后序遍历左子树；后序遍历左子树；(2) 后序遍历右子树；后序遍历右子树；(3) 访问根结点。访问根结点。31ABCDEFGHK后序序列：后序序列：ABCDEHGKF32 除了上述给出的常用的三种遍历方法除了上述给出的常用的三种遍历方法外，实际上在考试中还有可能出现别的遍外，实际上在考试中还有可能出现别的遍历方法，根据我们所有历方法，根据我们所有根、左子树和右子根、左子树和右子树树的先后顺序，它们的不同序列应该有的先后顺序，它们的不同序列应该有六六种。种。NLR LNR LR

17、N NRL RNL RLN如，某一年的考题如下：如，某一年的考题如下：33真题演练真题演练 给定一棵二叉树如图所示，其遍历序给定一棵二叉树如图所示，其遍历序列为，则其遍历的方式是（列为，则其遍历的方式是（ ） A. LRN B. NRL C. RLN D.RNLD34 例如例如,已知先序序列为已知先序序列为ABDGCEF,中序序列为中序序列为DGBAECF,则构造二叉树的过程如下所示。则构造二叉树的过程如下所示。 根结点：根结点：A左先序左先序:BDG 左中序左中序:DGB右先序右先序:CEF 右中序右中序:ECF根结点：根结点：B左先序左先序:DG 左中序左中序:DG右先序右先序:空空 右中

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

19、示。应的构造二叉树的过程如下所示。 根结点：根结点：A左中序左中序:DGB 左根左根:B右中序右中序:ECF 右根右根:C根结点：根结点：G左中序左中序:空空 左根左根:空空右中序右中序:空空 右根右根:空空根结点：根结点：B左中序左中序:DG 左根左根:D右中序右中序:空空 右根右根:空空根结点：根结点：C左中序左中序:E 左根左根:E右中序右中序:F 右根右根:F根结点：根结点：D左中序左中序:空空 左根左根:空空右中序右中序:G 右根右根:G根结点：根结点：E左中序左中序:空空 左根左根:空空右中序右中序:空空 右根右根:空空根结点：根结点：F左中序左中序:空空 左根左根:空空右中序右中

20、序:空空 右根右根:空空36真题演练真题演练 若一棵二叉树的先序遍历序列是若一棵二叉树的先序遍历序列是aebdc，后序遍历序列是，后序遍历序列是bcdea，则根结，则根结点的孩子结点点的孩子结点 （ ） A. 只有只有e B. 有有eb C. 有有ec D.无法确定无法确定A37树和二叉树的相互转换树和二叉树的相互转换 树树 二叉树二叉树 二叉二叉树树 树树（五）树、森林的遍历与二叉树的转（五）树、森林的遍历与二叉树的转换换树的左孩子是其原来树的左孩子是其原来最左边的孩子结点，树的最左边的孩子结点，树的右孩子是其右兄弟结点右孩子是其右兄弟结点38ABCDEFGHII将森林转换为二叉树的过程将森

21、林转换为二叉树的过程39ABCDACBDABCD图图 二叉树还原成森林的过程二叉树还原成森林的过程(a) 二叉树二叉树ABCDGLKHM(b) 去连线后去连线后ABCDMGLKHMGLHK(c) 还原成森林还原成森林ACBD40（六）线索二叉树（六）线索二叉树按照某种遍历序列，利用二叉链表中按照某种遍历序列，利用二叉链表中的结点的空指针，若是左指针为空，的结点的空指针，若是左指针为空，则该指针就指向其该种遍历下的前驱，则该指针就指向其该种遍历下的前驱，如果右指针为空，则指向其后继。指如果右指针为空，则指向其后继。指向前驱或后继的这些指针就称为线索。向前驱或后继的这些指针就称为线索。这样得到的二

22、叉树序列就是某种序列这样得到的二叉树序列就是某种序列的线索二叉树。的线索二叉树。41真题演练真题演练 已知一个有已知一个有2011个结点的树，其叶子个结点的树，其叶子结点个数为结点个数为116，该树对应的二叉树中无右，该树对应的二叉树中无右孩子的结点个数为孩子的结点个数为 （ ） A.115 B.116 C.1895 D.1896D42二叉树的线索化二叉树的线索化 起因：起因：因为二叉树的链式存储结构会有很因为二叉树的链式存储结构会有很多指针域为空，所以我们可以利用这些指多指针域为空，所以我们可以利用这些指针域。以二叉链表为例，如果左孩子存在，针域。以二叉链表为例，如果左孩子存在，则左指针指向

23、其左孩子，否则指向其前驱；则左指针指向其左孩子，否则指向其前驱；若右孩子存在，则右指针指向其右孩子，若右孩子存在，则右指针指向其右孩子，否则右指针指向其后继。否则右指针指向其后继。 由于在不同的遍历方式中，某结点的由于在不同的遍历方式中，某结点的前驱和后继也不同，因而可得出不同形式前驱和后继也不同，因而可得出不同形式的二叉线索树。的二叉线索树。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各种线索二叉树的好处如

24、下：各种线索二叉树的好处如下：中序线索树找结点的前驱和后继都方便中序线索树找结点的前驱和后继都方便先序线索化找后继方便先序线索化找后继方便后序线索化找前驱方便后序线索化找前驱方便45真题演练真题演练下列线索二叉树中，符合后序线索树定义下列线索二叉树中，符合后序线索树定义的是（的是（ ）ABCDNULLABCDNULLNULLABCDNULL(1)(2)(3)D B C A46赫夫曼树赫夫曼树二叉排序树二叉排序树平衡二叉树平衡二叉树47赫夫曼树赫夫曼树 哈夫曼树的定义哈夫曼树的定义 设二叉树具有设二叉树具有n个带权值的叶子结点个带权值的叶子结点,那么那么从根结点到各个叶子结点的路径长度与相应结从

25、根结点到各个叶子结点的路径长度与相应结点权值的乘积的和点权值的乘积的和,叫做二叉树的带权路径长度。叫做二叉树的带权路径长度。 其中其中,n表示叶子结点的数目表示叶子结点的数目,wi和和li分别表分别表示叶子结点示叶子结点ki的权值和根到的权值和根到ki之间的路径长度之间的路径长度(即从叶子结点到达根结点的分支数即从叶子结点到达根结点的分支数)。 具有最小带权路径长度的二叉树称为哈夫具有最小带权路径长度的二叉树称为哈夫曼树。曼树。 488W= 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.115297148152331183519157829425810

26、0492914231183519157829425810000001001011113:0000 5:0001 11:001 7:10008:1111 23:01 29:10 14:110150真题演练真题演练1、对、对n（n=2）个权值均不相同的字符构造哈夫）个权值均不相同的字符构造哈夫曼树，关于概述的叙述，错误的是（曼树，关于概述的叙述，错误的是（ ）该树一定是一棵完全二叉树该树一定是一棵完全二叉树树中一定没有度为树中一定没有度为1的结点的结点树中两个权值最小的结点一定是兄弟结点树中两个权值最小的结点一定是兄弟结点A.树中任一非叶子结点的权值一定不小于下一层树中任一非叶子结点的权值一定不小

27、于下一层任一结点的权值任一结点的权值A511、设有、设有6个有序表个有序表A、B、C、D、E、F，分别含有，分别含有10、35、40、50、60和和200个数据元素，各表个数据元素，各表中元素按升序排列。要求通过中元素按升序排列。要求通过5次两两合并，将次两两合并，将6个个表最终合并成表最终合并成1个升序表，并在最坏情况下比较的个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。总次数达到最小。请回答下列问题。（1）给出完整的合并过程，并求出最坏情况下比较）给出完整的合并过程，并求出最坏情况下比较的总次数。的总次数。（2）根据你的合并进程，描述）根据你的合并进程，描述n个不等长升序表

28、的合个不等长升序表的合并策略，并说明理由。并策略，并说明理由。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次，故最坏情况

29、下比较的总次数计算如下： 第一次合并：10+35-1=44；第二次合并：45+40-1=84 第三次合并：50+60-1=109；第四次合并：85+110-1=19； 第五次合并：195+200-1=394 因此，最多的比较次数是：825。54（2）合并策略是：）合并策略是： 在对多个有序表进行两两合并时，若表在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用赫夫曼树的构于表的合并次序。可以借用赫夫曼树的构造思想，依次选择最短的两个表进行合并，造思想，依次选择最短的两个表进行合并，可以获得最坏情况下得合并效率。可以

30、获得最坏情况下得合并效率。55二叉排序树二叉排序树 二叉排序树二叉排序树(简称简称BST)又称二叉查找又称二叉查找(搜索搜索)树树,其其定义为：二叉排序树或者是空树定义为：二叉排序树或者是空树,或者是满足如下性或者是满足如下性质的二叉树：质的二叉树： (1) 若它的左子树非空若它的左子树非空,则左子树上所有记录的值均则左子树上所有记录的值均小于小于根记录的值；根记录的值； (2) 若它的右子树非空若它的右子树非空,则右子树上所有记录的值均则右子树上所有记录的值均大于大于根记录的值；根记录的值； (3) 左、右子树本身又各是一棵二叉排序树。左、右子树本身又各是一棵二叉排序树。5650308020

31、9010854035252388例如例如: :是二叉排序树。是二叉排序树。66不5750308020908540358832例如例如: :二叉排序树查找过程二叉排序树查找过程查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 58 例例 9 . 2 已 知 一 组 关 键 字 为已 知 一 组 关 键 字 为25,18,46,2,53,39,32,4,74,67,60,11。按表中的元素顺序依次插入到一棵初按表中的元素顺序依次插入到一棵初始为空的二叉排序树中始为空的二叉排序树中,画出该二叉画出该二叉排序树排序树,并求在等概率的情况下查找并求在等概率的情

32、况下查找成功的平均查找长度。成功的平均查找长度。 解：生成的二叉排序树如右图所解：生成的二叉排序树如右图所示。示。 25 18 46 39 53 2 4 11 32 74 67 60 5 . 312615243332211ASL 二叉排序树查找的过程即为其创建的过程。每二叉排序树查找的过程即为其创建的过程。每一次的插入都是在叶子上进行的。一次的插入都是在叶子上进行的。59二叉排序树结点的删除二叉排序树结点的删除分为三种情况分为三种情况（1）被删除的结点是叶子结点被删除的结点是叶子结点（2）被删除的结点只有左子树或者只有右被删除的结点只有左子树或者只有右子树子树（3）被删除的结点既有左子树，也有

33、右子被删除的结点既有左子树，也有右子树树60508020908540358832（1）被删除的结点是叶子结点：）被删除的结点是叶子结点：直接删去该结点。直接删去该结点。例如例如:被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”306150308020908540358832（2）被删除的结点只有左子树或者只有右子树，用其左）被删除的结点只有左子树或者只有右子树，用其左子树或者右子树代替它。子树或者右子树代替它。 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左指向被删除结点的左子树或右子树子树或右子树”。被

34、删关键字被删关键字 = 40806250308020908540358832（3）被删除的结点既有左子树，也有右子树）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除以其前驱替代之，然后再删除该前驱结点。前驱是左子树中该前驱结点。前驱是左子树中最大的结点。最大的结点。被删结点被删结点前驱结点前驱结点被删关键字被删关键字 = 5063真题演练真题演练（1）对下列关键字序列，不可能构成某二）对下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是叉排序树中一条查找路径的序列是 （ ） A. 95 22 91 24 94 71 B. 92 90 91 34 88 35 C.

35、 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；：左子树和右子树也都是平衡二叉树。 如果一棵二叉树既是二叉排序树又是平衡如果一棵二叉树既是二叉排序树又

36、是平衡二叉树，称为平衡二叉排序树二叉树，称为平衡二叉排序树(Balanced Binary Sort Tree) 。66 5 2 6 1 4 3 7 1 0 -1 0 1 0 -1 3 1 4 2 5 6 7 (b) (a) 0 -1 -2 -3 -2 -1 0 平衡二叉树和不平衡二叉树平衡二叉树和不平衡二叉树 67 平衡二叉树中插入新结点方式与二叉排序树平衡二叉树中插入新结点方式与二叉排序树相似，只是插入后可能破坏了平衡二叉树的平衡相似，只是插入后可能破坏了平衡二叉树的平衡性性,解决方法是调整。解决方法是调整。调整操作可归纳为下列四种情况：调整操作可归纳为下列四种情况：68 (1) LL型调

37、整型调整单向右旋保平衡单向右旋保平衡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树的步骤。树的步骤。 16 0 (a)插入插入 16 16 1 (b)插入插