数据结构分析与管理讲义

1、前言缘起数据结构是一门计算机专业基础课，各类计算机考试都禁不住要考它，专升本考试自然也不例外。我给学生辅导这门课程已经有几个年头了，讲稿换了几次，逐渐丰富起来。加之看到学生们埋头记笔记时辛苦的样子，就产生了写一本小册子的想法。另外，还有一层意思就是对数次辅导进行总结，以便交流之用。说明首先，需要要说明的的是这本本书在语语言风格格上不太太讲究，常常有些不不严谨的的表达，或或调侃，或或土得掉掉渣，难难登大雅雅之堂，请请勿在正正规场合合引用这这些说法法。这样样做的目目的，仅仅仅是为为了更简简练、更更直接地地描述思思想，方方便理解解、记忆忆和使用用。凡是是这种情情况，往往往都用用引号括括起来，并并加以

2、脚脚注说明明。还有，本书书需配合合数据据结构(严蔚敏敏)教材材使用。由由于篇幅幅有限，多多数概念念、术语语没有详详释。 另外，每章章之后都都配有习习题，或或多或少少，难度度不一，并并没有局局限于专专升本的的要求。对对所有习习题都提提供了参参考答案案。致谢我要感谢所所有给予予我帮助助的人。张志老师的的大力支支持和帮帮助使得得本书得得以面世世，他还还提供了了近年专专升本试试题。李李永干老老师的帮帮助使得得本书顺顺利印刷刷。谭业业武老师师给了我我很大支支持，还还提出了了很多建建议。最后，我要要感谢隆隆坤，她她总是给给我最大大的支持持，使那那些本来来只在我我想象中中的事情情变成现现实。庄波于滨州学学院

3、TOC o 1-3 h z u HYPERLINK l _Toc101798259 第0章 复复习提示示 /ASL = (115+223)/8 = 111/8注：关键字字在链表表中的插插入位置置可以在在表头或或表尾，也也可以在在中间以以便保持持关键字字有序。最后，此哈哈希表的的装填因因子是= 88/111。习题 STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 1 对对n=110个元元素的表表顺序查查找，在在等概率率情况下下(对每每个元素素查找的的概率相相同)，查查找成功功时的平平均查找找长度是是多少？如果查查找失败败的概率率为0.2，平平均查找找长度又又是多少少？ ST

4、YLEREF 1 s 9. SEQ 习题 * ARABIC s 1 2 表表长155的有序序表进行行折半查查找，计计算等概概率情况况下查找找成功时时的平均均查找长长度和查查找第33个元素素需要比比较关键键字的个个数。 STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 3 对对表长110233的有序序表折半半查找，比比较8个个关键字字才能找找到的元元素有多多少个？至多比比较8次次就能找找到的元元素有多多少个？ STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 4 长长度为1100000的表表进行分分块查找找，用顺顺序查找找确定所所在块，块块内元素素无序

5、，为为使平均均查找长长度最小小应该分分几块？ STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 5 编编写算法法判断给给定的二二叉树是是否是二二叉排序序树。 STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 6 给给定一组组关键字字(133，244，377，900，533，400，200)，建建立二叉叉排序树树。 STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 7 给给定一组组关键字字(133，244，377，900，533，400，200)，建建立平衡衡二叉排排序树。 STYLEREF 1 s 9. SEQ 习题 * ARA

6、BIC s 1 8 编编写平衡衡二叉排排序树的的查找算算法。 STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 9 具具有200个结点点的二叉叉排序树树的最大大深度是是(_)，最最小深度度是(_)；200个结点点的平衡衡二叉排排序树最最大深度度是(_)。 STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 10 在一棵棵非空的的5阶BB-树中中，非叶叶子结点点中最少少有(_)棵子树树，最多多有(_)个关键键字；除除根以外外的非终终端结点点中最少少有(_)棵子树树。 STYLEREF 1 s 9. SEQ 习题 * ARABIC s 1 11 已知一一组

7、关键键字119, 14, 233, 11, 668, 20, 855, 99，采采用哈希希函数HH(keey)=keyy MOOD 113，请请分别采采用以下下处理冲冲突的方方法构造造哈希表表，并求求各自的的平均查查找长度度。 11) 采采用线性性探测再再散列； 2) 采用用伪随机机探测再再散列，伪伪随机函函数为ff(n) = n2+2nn+3； 3) 采用用链地址址法。内部排序基础知识和和算法排序的有关关概念排序（按关关键字大大小顺序序排列数数据）。排序方法：内部排排序，外部排排序；简简单的排排序方法法O(nn2)，先先进的排排序方法法O(nnloggn)，基数排序O(dn)；插入排序，交换

8、排序，选择排序，归并排序，计数排序。排序方法的的稳定性性：取决决于该方方法采取取的策略略，不是是由一次次具体的的排序结结果决定定的。但但是通过过列举不不稳定的的排序实实例可以以说明该该排序算算法的不不稳定性性。直接插入排排序思路将待排序记记录插入入已排好好的记录录中，不不断扩大大有序序序列一句话，“将待排排序记录录插入有有序序列列，重复复n-11次” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 不准确的说法，只为便于理解和记忆，不要在正式场合引用。例：52，449，880，336，114，558，661 进进行直接接插入排排序。808036145861(52)52)36145861

9、(4980)5236145861(49524980)5861(3649365280)5861(144936525880)61(14493652586180)(14分析表 STYLEREF 1 s 10. SEQ 表 * ARABIC s 1 1 直接接插入排排序比较移动记录顺序有有序时n-10最好记录逆序有有序时(n+22)(nn-1)/22(n+44)(nn-1)/22最坏平均n2/4，算算法的时时间复杂杂度O(n2)。直直接插入入排序是是稳定的的排序算算法。折半插入排排序思路在直接插入入排序中中，查找找插入位位置时采采用折半半查找的的方法。程序void BinnInsserttSorrt

10、XE BiinInnserrtSoort ( T a, iint n ) forr ( i=11; iin; i+ ) / 在在a00.ii-1中折半半查找插插入位置置使ahigghaiiaahiigh+1.i-11 llow = 00; higgh = i-1; wwhille ( loow=higgh ) m = ( loow+hhighh )/2; iff ( aiihhighh; jj- ) aj+11 = aj; aa hhighh+1 = x; / 完成插插入 分析时间复杂度度O(nn2)。比比直接插插入排序序减少了了比较次次数。折折半插入入排序是是稳定的的排序算算法。希尔排序（缩

11、缩小增量量排序）思路先将待排序序列分割割成若干干个子序序列，分分别进行行直接插插入排序序，基本本有序后后再对整整个序列列进行直直接插入入排序。步骤：10. 分分成子序序列(按按照增量量dk)；20. 对对子序列列排序(直接插插入排序序)；30. 缩缩小增量量，重复复以上步步骤，直直到增量量dk=1。增量序列中中最后一一个增量量一定是是1，如如： 99, 55, 33, 22, 11和 113, 4, 1。如如没有明明确说明明增量序序列可以以选择 3, 2, 1或 5, 3, 2, 1。例：希尔排排序(552，449，880，336，114，558，661)。8080493614586152dk

12、=358145249806136dk=249145258806136dk=149365258618014注意：希尔尔排序是是不稳定定的。时时间复杂杂度大约约为O(n3/2)。程序void SheellSSortt XE SheellSSortt ( T a, iint n ) dk = nn/2; whiile ( ddk=1 ) / 一一趟希尔尔排序，对对dk个个序列分分别进行行插入排排序 ffor ( ii=dkk; ii=0 aand xaaj; jj-=ddk ) ajj+dkk = aj; aj+ddk = xx; / 缩缩小增量量 ddk = dkk/2; 起泡排序思路一句话，“依

13、次比比较相邻邻元素，逆序则交换，重复n-1次” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 不准确的说法，只为便于理解和记忆，不要在正式场合引用。例：冒泡排排序(552，449，880，336，114，558，661)。8080493614586152365214586180491436525861804949145258618036493652586180144936525861801449365258618014程序请参考 REF _Ref96512884 w h 第11章 二二、BuubblleSoort算算法。分析比较和交换换总是发发生在相相邻元素素之间，是是稳定的的排序算

14、算法。时时间复杂杂度O(n2)。快速排序思路一趟排序把把记录分分割成独独立的两两部分，一一部分关关键字均均比另一一部分小小，然后后再分别别对两部部分快排排。例：522 449 80 366 114 58 611 快快速排序序。下面是一次次划分的的详细步步骤：808049365861)(5261)58141480493661)581480493661)581480493661)58(14(804936)52技巧：选第1个记录为轴，分别从后向前，从前向后扫描记录，后面“抓大放小”(如：)，前面“抓小放大”(如：)，交替进行(-)，最后将轴记录放在中间()，划分成两个序列。整个快速排排序过程程如下：

15、80804936145861)(5261)58(1449(8036)52144936)(36)(49(6158)80(58)6114364952586180程序void QuiickSSortt XE QuiickSSortt ( T a, iint loww, iint higgh ) if ( llow hhighh ) / 划划分 ppivoot = aloww; ii = loww; jj = higgh; wwhille ( i jj ) whhilee ( i= pivvot ) j; ai = aaj; whhilee ( ijj & ai = pivvot ) i+; aj =

16、 aai; aai = pivvot; / 对对子序列列快排 QQuicckSoort ( aa, llow, i-1); QQuicckSoort ( aa, ii+1, hiigh); 分析平均情况下下，时间间复杂度度O(nnloggn)。记记录本来来有序时时为最坏坏情况，时时间复杂杂度为OO(n22)。空间复杂度度(考虑虑递归调调用的最最大深度度)在平平均情况况下为OO(loogn)，在最最坏情况况下为OO(n)。快速排序是是不稳定定的。简单选择排排序思路第i趟排序序过程是是在剩余余的待排排记录中中选一个个最小（大大）的，放放在第ii个位置置。一句话，“在待排排记录中中选取最最小的，交交

17、换到合合适位置置，重复复n-11次” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 不准确的说法，只为便于理解和记忆，不要在正式场合引用。例：522 449 80 366 114 58 611简单单选择排排序。804980493614586152804936145861528049361458615280493614586152804936145861528049361458615280493614586152程序void SellecttionnSorrt XE SeelecctioonSoort ( T a, iint n ) forr ( i=00; iin-1; i+ ) k

18、k = i; ffor ( jj=i+1; jnn; jj+) iff ( ajj=hiigh ) retturnn; elsse mmid = (loww+hiigh)/2; MMerggeSoort ( aa, llow, miid ); MMerggeSoort ( aa, mmid+1, higgh ); MMergge ( a, loow, midd, hhighh ); 自底向上的的归并排排序：void MerrgeSSortt XE MerrgeSSortt ( T a, iint n ) t = 1; whiile ( ttn ) ss = t; t = ss*2; ffor

19、( ii=0; i+t=n; i+=t ) Meergee ( a, i, i+ss-1, i+t-11 ); iif ( i+snn ) Meergee ( a, i, i+ss-1, n-1 ); 附：Merrge()，将将有序序序列aloww.mmid和amidd+1.hiigh归并到到allow.hiigh。void Merrge XE MMergge ( T aa, innt llow, innt mmid, innt hhighh ) / 归并到到b i = loow; j = mmid+1; k = llow; whiile ( ii=mmid andd j=hiigh ) ii

20、f ( ai=aj ) bk = aai; i+; eelsee bk = aaj; j+; kk+; / 归并剩剩余元素素 whiile ( ii=mmid ) bkk+ = aii+; whiile ( jj=hhighh ) bk+ = aj+; / 从b复制制回a allow.hiigh = bllow.hiigh;分析时间复杂度度O(nnloggn)。需需要空间间多，空空间复杂杂度O(n)。归归并排序序是稳定定的排序序。基数排序思路多关键字排排序最高位优先先（MSSD），最低位优先（LSD）。链式基数排排序链式基数排排序采用用“分配”和“收集”策略。例：5003，0087，5512，

21、0061，9908，1170，8897，2275，6653分析：数字字099共100种情况况，rdd=100。 每个个关键字字都有33位数字字，d=3。 共有有9个记记录，nn=9。先“收集”成一个个链表，按最低位（个个位）“分配”到100个链表表中（00号99号）：00123456789170061512503275087908653897按个位顺序序“收集”成一个个链表：( 1700, 0061, 5112, 5033, 6653, 2775, 0877, 8897, 9008 )再按第2位位数字（十十位）“分配”到100个链表表中：0012345678950351265306117089

22、7908275“收集”成成一个链链表：( 5033, 9908, 5112, 6533, 0061, 1770, 2755, 8897 )按第3位数数字（百百位）“分配”到100个链表表中：00123456789061170275503653897908512“收集”成成一个链链表：( 0611, 1170, 2775, 5033, 5512, 6553, 8977, 9908 )完成排序。分析对n个数据据进行基基数排序序，每个个数据基基数为rrd，有有d位数数字。那那么，一一趟分配配和收集集用时nn+rdd(分配配用n，收收集用rrd)，共共需d趟趟，总的的时间复复杂度为为O(dd(n+rd

23、)。基数排序是是稳定的的排序算算法。各种排序方方法比较较表 STYLEREF 1 s 10. SEQ 表 * ARABIC s 1 2 排序序方法的的比较排序方法时间复杂性性空间复杂性稳定特点平均最好最坏简单插入排排序O(n2)O(n)O(n2)O(1)是元素少或基基本有序序时高效效希尔排序O(n3/2)O(1)否冒泡排序O(n2)O(n)O(n2)O(1)是快速排序O(nloogn)O(nloogn)O(n2)O(loggn)否平均时间性性能最好好简单选择排排序O(n2)O(1)否比较次数最最多堆排序O(nloogn)O(1)否辅助空间少少归并排序O(nloogn)O(n)是稳定的基数排序O

24、(d(nn+rdd)O(rd)是适合个数多多关键字字较小基于关键字字比较的的排序方方法，在在最坏情情况下所所能达到到的最好好的时间间复杂度度是O(nloogn)。习题 STYLEREF 1 s 10. SEQ 习题 * ARABIC s 1 1 对待排排序列(24, 866, 448, 56, 722, 336)进进行 11) 直直接插入入排序，22) 希希尔排序序，3) 起泡泡排序，44) 快快速排序序，5) 简单单选择排排序，66) 堆堆排序，77) 归归并排序序，8) 链式式基数排排序。 STYLEREF 1 s 10. SEQ 习题 * ARABIC s 1 2 证明：借助比比较进行行

25、的排序序方法，在在最坏情情况下所所能达到到的最好好的时间间复杂度度是O(nloogn)。附录A: 习题解解答 REF _Ref94387123 1.1 编编写冒泡泡排序算算法，使使结果从从大到小小排列。void BubbbleeSorrtDeec XE BuubblleSoortDDec ( DaataTTypee a, intt n ) forr ( i=00; iin-1; i+ ) cchannge = ffalsse; ffor( j=0; jnn-i-1; j+ ) iff ( ajjaaj+1 ) / 逆序 swaap( ajj, ajj+1 ); chaangee = truue

26、; iif ( noot cchannge ) bbreaak; / 没有交交换则完完成排序序 REF _Ref99086399 h 1.2 计计算下面面语句段段中指定定语句的的频度： 1) foor ( i=1; i=n; i+ ) ffor ( jj=i; j=n; j+ ) xx+;/ 2) ii = 1; whiile ( ii=nn ) i = i*2;/ 分析：计算算语句频频度是计计算时间间复杂度度的基础础。可以以用观察察和归纳纳进行简简单的计计算。1) 问问题规模模n执行次次数1122+133+2+11.nn+2+1=nn(n+1)/2结论：语句句频度为为n(nn+1)/2。2)

27、 问问题规模模n执行次次数11223243.2kkk+1结论：语句句频度为为。 REF _Ref94417305 h 2.1 将将顺序表表中的元元素反转转顺序。void Revversse XE Reeverrse ( SqqLisst& L ) forr ( i=00; iiL.lenngthh/2; i+) / eq oac(,?) 还是 =00 & L.eleemiixx; ii-) LL.ellemi+11 = L.eleemii; / 插入xx (因因为最后后执行ii-，故故应在ii+1处处) L.eelemmi+1 = xx; L.llenggth+; retturnn truue

28、; REF _Ref94429906 2.3 删删除顺序序表中所所有等于于x的元元素。void Remmovee XE Remmovee ( SqqLisst &L, DattaTyype x ) i = 0; / 剩余元元素个数数，同时时是下一一个元素素的插入入位置 forr ( j=00; jjL.lenngthh; jj+ ) iif ( L.eleemjj!=x ) / 复制不不等于xx的元素素组成新新表 iff ( i!=j ) LL.ellemi = LL.ellemj; / 当当i=j时不不必复制制 i+; L.llenggth = ii; / 剩余元元素个数数本算法的时时间复杂

29、杂度为OO(n)；若改改用反复复调用查查找和删删除算法法，时间间复杂度度会达到到O(nn2)。 REF _Ref94429914 2.4 编编写算法法实现顺顺序表元元素唯一一化(即即使顺序序表中重重复的元元素只保保留一个个)，给给出算法法的时间间复杂度度。思路：设已已经唯一一化的序序列是(a0, , ai-1)，剩剩余序列列是(aaj, aan)。所所要做的的就是在在已经唯唯一化的的序列LL.ellem0.i-11中查查找L.eleemjj，如如果未找找到则复复制到LL.ellemi处处。如此此重复直直到剩余余序列为为空。void Uniiquee XE Uniiquee ( SqqLisst

30、 &L ) if ( LL.leengtth=1 ) rretuurn; / 空表或或只有一一个元素素的表已已经唯一一化了 i = 1; / 开始LL.ellem0.0是是唯一化化序列 forr ( j=11; jjL.lenngthh; jj+ ) / 在在L.eelemm0.i-1中中查找LL.ellemj ffor ( kk=0; ki; k+ ) iff ( L.eelemmk=LL.ellemj ) breeak; iif ( k=i ) / L.eelemmj未出现现过，复复制到LL.ellemi处处 iff ( j!=i ) LL.ellemi = LL.ellemj; i+;

31、L.llenggth = ii; / 表长为为i以上算法的的时间复复杂度为为O(nn2)。当当然，可可以反复复将重复复元素删删除达到到唯一化化，时间间复杂度度仍是OO(n22)，但但是与以以上算法法相比要要移动更更多元素素。 REF _Ref94429918 2.5 非非递减有有序的顺顺序表元元素唯一一化(参参见习题题2.4)，要要求算法法的时间间复杂度度为O(n)。分析：由于于该表是是有序的的，相等等的元素素必然靠靠在一起起，不必必从头开开始查找找，所以以算法的的时间复复杂度可可以降低低。思路：类似似习题 REF _Ref94428249 h 22.4，但是是查找部部分只要要与L.eleem

32、ii-1比较就就可以了了。void Uniiquee XE Uniiquee ( SqqLisst &L ) i = 0; / 开开始的唯唯一化序序列为空空( eq oac(,?)对比习习题 REF _Ref94428249 h 2.4思考为为什么不不用i=1开始始 原因是这里不能确定表是否为空，而习题2.4则用开始的if语句排除了空表的情况。事实上，习题2.4也可以仿照此处修改，请读者自己完成。) 原因是这里不能确定表是否为空，而习题2.4则用开始的if语句排除了空表的情况。事实上，习题2.4也可以仿照此处修改，请读者自己完成。 forr ( j=11; jjneext; / 原链表表 L-

33、nexxt = NUULL; / 新表(空表) whiile ( pp ) / 从从原链表表中取下下结点ss ss = p; pp = p-nexxt; / 插插入L新新表表头头 ss-nnextt = L-nexxt; LL-nnextt = s; REF _Ref94429922 2.7 采采用插入入法将单单链表中中的元素素排序。void InsserttionnSorrt XE IInseertiionSSortt ( LinnkLiist &L ) h = L-neext; / 原链表表 L-nexxt = NUULL; / 新空表表 whiile ( hh ) / 从从原链表表中取下

34、下结点ss ss = h; h = hh-nnextt; / 在在新表中中查找插插入位置置 pp = L; wwhille ( p-neext & p-nexxt-dattadatta ) p = pp-nnextt; / 在在p之后后插入ss ss-nnextt = p-nexxt; pp-nnextt = s; REF _Ref94429925 2.8 采采用选择择法将单单链表中中的元素素排序。void SellecttionnSorrt XE SeelecctioonSoort ( LLinkkLisst &L ) p = L; whiile ( pp-nnextt ) / 选选择最小小

35、(从pp-nnextt至表尾尾) qq = p; / 最小元元素的前前驱q ss = p; wwhille ( s-neext ) iff ( s-nexxt-datta neext-daata ) q = s; s = ss-nnextt; mm = q-nexxt; / 找到最最小m / 最最小元素素m插入入有序序序列末尾尾(p之之后) iif ( q!=p ) q-neext = mm-nnextt; / 解下最最小m m-neext = pp-nnextt; / 插入pp之后 p-neext = mm; pp = p-nexxt; / L-nexxt至pp为有序序序列 REF _Ref

36、94429926 2.9 将将两个非非递减有有序的单单链表归归并成一一个，仍仍并保持持非递减减有序。/ 将非非递减有有序的单单链表llb合并并入laa，保持持非递减减有序/ 结果果la中中含有两两个链表表中所有有元素，llb为空空表void Merrge XE MMergge ( LinnkLiist &laa, LLinkkLisst &lb ) p = laa, q = lbb; whiile ( pp-nnextt annd qq-nnextt ) / 跳跳过laa中较小小的元素素 wwhille ( p-neext andd (pp-nnextt-ddataa neext-daata)

37、 ) p = pp-nnextt; / 把把lb中中较小的的元素插插入laa中 wwhille ( p-neext andd q-neext andd (qq-nnextt-ddataa nexxt-datta) ) s = qq-nnextt; q-neext = ss-nnextt; s-neext = pp-nnextt; p-neext = ss; p = ss; if ( llb-nexxt ) / 表lbb剩余部部分插入入la末末尾 pp-nnextt = lb-neext; llb-nexxt = NUULL; REF _Ref94546422 h 3.1 元元素1,2,33,4

38、依依次入栈栈，不可可能的出出栈序列列有哪些些？分析：什么么是不可可能的出出栈序列列？如果果后入栈栈的数(如4)先出栈栈，则此此前入栈栈元素(如1,2,33)在栈栈中的顺顺序就确确定了，它它们的出出栈顺序序一定是是逆序(如3,2,11)，否否则就是是不可能能的出栈栈序列(如2,1,33)。不可能的出出栈序列列有：441233，41132，442133，42231，443122，34412，331422，31124。其其中后33种都含含3122这一不不可能序序列。 REF _Ref94546425 h 3.2 设设循环队队列Q少少用一个个元素区区分队列列空和队队列满，MMAXSSIZEE=5，QQ

39、.frrontt=Q.reaar=00，画出出执行下下列操作作时队列列空和队队列满的的状态。入入队列aa,b,c，出出队列aa,b,c，入入队列dd,e,f,gg。farfabrfabcrfbcrffcr ff r 队列空空 . frfdefgrfde 队列满满。 REF _Ref94546427 h 3.3 编编写算法法利用栈栈将队列列中的元元素翻转转顺序。思路：先将将队列中中的元素素入栈，然然后从栈栈中取出出重新入入队列。void Revversse XE Reeverrse ( SqqQueeue &Q ) IniitSttackk ( S ); whiile ( ! QuueueeEm

40、ppty(Q) ) DDeQuueuee ( Q, x ); PPushh ( S, x ); whiile ( ! SttackkEmppty(S) ) PPop ( SS, xx ); EnnQueeue ( QQ, xx ); REF _Ref94533139 h 4.1 长长度为nn的串的的子串最最多有多多少个？思路：对子子串长度度归纳。子串的长度度是0，11，2，.，n，对应子串的个数分别是1(空串)，n，n-1，.，1，总起来就是1+n+(n-1)+.+2+1=1+n(n+1)/2。 REF _Ref94628946 h 6.1 度度为k的的树中有有n1个度为为1的结结点，nn2个

41、度为为2的结结点，nk个度为为k的结结点，问问该树中中有多少少个叶子子结点。分析：分别别从结点点个数和和分支个个数考虑虑。设叶子个数数为n00，结点点总数：n = n00+n1+n2+nnk，分支支数目：n-11 = n1+2 n2+kk nkk，于是是得到叶叶子个数数 REF _Ref94628950 h 6.2 有有n个叶叶子结点点的完全全二叉树树的高度度是多少少?分析：完全全二叉树树中度为为1的结结点至多多有一个个。完全二叉树树中的结结点数nn+(nn-1) N n + (n-11) + 1，即即2n-1 N 2nn，二叉叉树的高高度是于是，(11) 当当n=22k时，当当没有度度为1的

42、的结点时时；，当当有1个个度为11的结点点时。(2) 其他情情况下，。 REF _Ref94628952 h 6.3 编编写算法法按照缩缩进形式式打印二二叉树。void PriintBBinaaryTTreee XE PriintBBinaaryTTreee ( BiinTrree bt, innt iindeent ) if ( ! btt ) reeturrn; forr ( i=00; iidatta ); PriintBBinaaryTTreee ( bt-lcchilld, inddentt+1 ); PriintBBinaaryTTreee ( bt-rcchilld, indde

43、ntt+1 ); REF _Ref94628953 h 6.4 编编写算法法按照逆逆时针旋旋转900度的形形式打印印二叉树树。void PriintBBinaaryTTreee XE PriintBBinaaryTTreee ( BiinTrree bt, innt lleveel ) if ( ! btt ) reeturrn; PriintBBinaaryTTreee ( bt-rcchilld, levvel+1 ); / 旋转后后先打印印右子树树 forr ( i=00; iidatta ); PriintBBinaaryTTreee ( bt-lcchilld, levvel+1 )

44、; REF _Ref94628972 h 6.5 编编写算法法判断二二叉树是是否是完完全二叉叉树。分析：按层层遍历完完全二叉叉树，当当遇到第第一个空空指针之之后应该该全都是是空指针针。bool IsCCompplette XE IssCommpleete ( BiinTrree bt ) / 按层遍遍历至第第一个空空指针 IniitQuueuee ( Q ); EnQQueuue ( Q, btt ); whiile ( ! QuueueeEmppty(Q) ) DDeQuueuee ( Q, p ); iif ( p ) EnnQueeue ( QQ, pp-llchiild ); EnnQ

45、ueeue ( QQ, pp-rrchiild ); ellse brreakk; / 遇到第第一个空空指针时时停止遍遍历 / 检查队队列中剩剩余元素素是否全全部是空空指针 whiile ( ! QuueueeEmppty(Q) ) DDeQuueuee ( Q, p ); iif ( ! p ) rretuurn fallse; / 不不是完全全二叉树树 retturnn truue; / 完全全二叉树树 REF _Ref94628974 h 6.6 编编写算法法求二叉叉树中给给定结点点的所有有祖先。分析：进行行后序遍遍历时，栈栈中保存存的是当当前结点点的所有有祖先。所所以，后后序遍历历二叉

46、树树，遇到到该结点点时，取取出栈中中的内容容即是所所有祖先先。/ 求二二叉树bbt中结结点xpptr的的所有祖祖先vectoor AAnceestoors XE AAnceestoors ( BiinTrree bt, BiinTrree xpttr ) staack s; sttackk taag; p = btt; whiile ( pp | ! s.eemptty() ) iif ( p ) s.pussh ( p ); taag.ppushh ( 1 ); p = pp-llchiild; ellse p = ss.poop(); f = taag.ppop(); iff ( f=1

47、) s.ppushh ( p ); tagg.puush ( 22 ); p = p-rcchilld; elsse if ( p=xpptr ) vv = s; / 当前前栈的内内容就是是xpttr的所所有祖先先 rretuurn v; p = NUULL; / wwhille retturnn veectoor(); / retturnn a nulll vvecttor注：这里为为描述方方便借助助了C+中的的某些描描述方式式。 REF _Ref94628975 h 6.7 编编写算法法求二叉叉树中两两个结点点的最近近的共同同祖先。思路：用后后序遍历历求出两两者的所所有祖先先，依次次比较。

48、/ 求二二叉树bbt中两两个结点点q和rr的最近近的共同同祖先BinTrree LasstAnncesstorr XE LasstAnncesstorr ( BiinTrree bt, BiinTrree q, BinnTreee rr ) staack sq, srr; staack s; sttackk taag; / 求q和和r的所所有祖先先 p = btt; whiile ( pp | ! s.eemptty() ) iif ( p ) s.pussh ( p ); taag.ppushh ( 1 ); p = pp-llchiild; ellse p = ss.poop(); f =

49、 taag.ppop(); iff ( f=1 ) s.ppushh ( p ); tagg.puush ( 22 ); p = p-rcchilld; elsse if ( p=q ) sq = ss; / q的所所有祖先先 if ( p=r ) sr = ss; / s的所所有祖先先 p = NUULL; / 先跳过过不同层层的祖先先，然后后依次比比较同一一层的祖祖先 if ( ssq.ssizee()sr.sizze() ) whhilee ( sq.sizze()srr.siize() ) ssq.ppop(); elsse whiile ( ssr.ssizee()sq.sizze(

50、) ) srr.poop(); / 求q和和r的最最近的共共同祖先先 whiile ( !sq.emppty() aand (sqq.toop()!=ssr.ttop() ) /寻找找共同祖祖先 ssq.ppop(); srr.poop(); if ( !sq.emppty() ) rretuurn sq.topp(); elsse rretuurn NULLL; REF _Ref94628977 h 6.8 编编写算法法输出以以二叉树树表示的的算术表表达式（中中缀形式式），要要求在必必要的地地方输出出括号。分析：当左左孩子的的优先级级低于根根时需要要加括号号，根的的优先级级大于右右孩子时时也

51、需要要加括号号。void PriintEExprresssionn XE PriintEExprresssionn ( BiinTrree bt ) if ( bbt=NULLL ) rretuurn ; if ( bbt-lchhildd=NNULLL annd bbt-rchhildd=NNULLL ) pprinnt ( btt-ddataa ); / 叶子结结点直接接打印 elsse / 左左子树 bbraccketts = btt-llchiild andd iss_opperaatorr(btt-llchiild-daata) aand commp_ooperratoor(bbt-

52、lchhildd-ddataa, bbt-datta)lchhildd ); iif ( brrackketss ) prrintt (“)”); / 根根结点 pprinnt ( btt-ddataa ); / 右右子树 bbraccketts = btt-rrchiild andd iss_opperaatorr(btt-llchiild-daata) aand commp_ooperratoor(bbt-datta, bt-rcchilld-datta)0; / 根的的优先级级大于右右孩子 iif ( brrackketss ) prrintt (“(“); PPrinntExxpree

53、ssiion ( bbt-rchhildd ); iif ( brrackketss ) prrintt (“)“); 注：is_opeerattor(c)判判断c是是否是运运算符；commp_ooperratoor(aa,b)比较两两个运算算符的优优先级。bool is_opeerattor(chaar cc) / 判断cc是否是是运算符符 retturnn c=+ | cc=- | c=* | c=/;int ccompp_opperaatorr(chhar opl, chhar opr) / 比较两两个运算算符的优优先级 retturnn (opl=* | oopl=/ | oopr=+

54、 | oopr=-) ? +1 : -11; REF _Ref94628980 h 6.9 树树采用孩孩子-兄兄弟链表表存储，编编写算法法求树中中叶子结结点的个个数。分析：树中中的叶子子没有孩孩子，即即firrstcchilld为空空。/ 求树树t中叶叶子结点点的个数数int LLeaffCouunt XE LLeaffCouunt ( CSSTreee tt ) if ( tt=NNULLL ) reeturrn 00; / 空树 if ( tt-ffirsstchhildd=NNULLL ) / 没有孩孩子 rretuurn 1 + LeeafCCounnt(tt-nnexttsibbli

55、nng); elsse rretuurn LeaafCoountt(t-fiirsttchiild) + LeaafCoountt(t-neextssibllingg); REF _Ref94628983 h 6.10 采用孩孩子-兄兄弟链表表存储树树，编写写算法求求树的度度。分析：度最最大的结结点的度度数。int DDegrree XE DDegrree ( CSSTreee tt ) if ( tt=NNULLL ) reeturrn 00; elsse rretuurn maxx( DDegrree(t-firrstcchilld), 1+Deggreee(t-neextssibllin

56、gg); REF _Ref94628986 h 6.11 采用孩孩子-兄兄弟链表表存储树树，编写写算法求求树的深深度。int DDeptth XE Deepthh ( CSSTreee tt ) if ( tt=NNULLL ) reeturrn 00; elsse ddepcchilld = Deepthh(t-fiirsttchiild); / 孩子的的深度 ddepssibllingg = Deppth(t-nexxtsiibliing); / 兄弟的的深度 rretuurn maxx(deepchhildd+1, deepsiibliing); / 取较大大者 REF _Ref9462

57、8988 h 6.12 已知二二叉树的的前序和和中序序序列，编编写算法法建立该该二叉树树。分析：划分分先序序序列a=(D,(L),(RR)和和后序序序列b=(LL),DD,(RR)，然然后对子子序列(L)和和(R)递归。/ 根据据先序序序列asi.tii和中中序序列列bssj.tj构造二二叉树BinTrree CreeateeBinnaryyTreee XE CrreatteBiinarryTrree ( T a, iint si, innt tti, T bb, innt ssj, intt tjj ) if ( nnlchhildd = CreeateeBinnaryyTreee ( a,

58、 sii+1, sii+k-sj, b, sjj, kk-1 ); / 建立左左子树 p-rchhildd = CreeateeBinnaryyTreee ( a, sii+k-sj+1, b, k+11, ttj); / 建立右右子树 retturnn p;GFDKICBAEHJ REF _Ref94795003 h 6.13 树T的的先根遍遍历序列列为GFFKDAAIEBBCHJJ，后根根遍历序序列为DDIAEEKFCGFDKICBAEHJ分析：根据据先根和和后根序序列可以以唯一确确定一棵棵树。先先根序列列中的第第一个是是树的根根，后根根序列中中最后一一个是根根，然后后根据先先根序列列和后

59、根根序列，将将其余序序列划分分成若干干不相交交的子序序列，就就是根的的子树，对对每一个个子树，重重复前面面的步骤骤，最终终就可以以得到整整个树。先根GFKKDAIIEBCCHJ 根为GG，第一一棵子树树的根为为F，又又后根DDIAEEKFCCJHBBG，所所以第一一棵子树树为(DDIAEEKF)，同样样第二棵棵子树为为(CJJHB)，依此此类推，可可得该树树。BADGCEFHIKLJ REF _Ref94795005 h 6.14 一森林林F转换换成的二二叉树的的先序序序列为AABCDDEFGGHIJJKL，中中序序列列为CBBEFDDGABADGCEFHIKLJ分析：根据据森林和和二叉树树的

60、对应应关系，可可知森林林的先序序序列和和中序序序列。划划分出每每一棵树树，正好好得到每每棵树的的先序和和后序序序列，最最终得到到整个森森林。 REF _Ref94795009 h 6.15 某通信信过程中中使用的的编码有有8个字字符A,B,CC,D,E,FF,G,H，其其出现的的次数分分别为220, 6, 34, 111, 99, 77, 88, 55。若每每个字符符采用33位二进进制数编编码，整整个通信信需要多多少字节节？请给给出哈夫夫曼编码码，以及及整个通通信使用用的字节节数？分析：由于于每个字字符出现现的频率率不同，使使用固定定长度的的编码往往往比哈哈夫曼编编码使得得整个通通信量增增多。