自考数据结构重点总结最终修订 .docx

《自考数据结构重点总结最终修订 .docx》由会员分享，可在线阅读，更多相关《自考数据结构重点总结最终修订 .docx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料收集于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结自考 02331 数据结构重点总结 最终修订 第一章概论1. 瑞士运算机科学家沃思提出：算法+数据结构 =程序。算法是对数据运算的描述，而数据结构包括规律结构和储备结构。由此可见，程序设计的实质是针对实际问题挑选一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。2. 数据 是信息的载体。数据元素 是数据的基本单位。一个数据元素可以由如干个数据项 组成， 数据项 是具有独立含义的最小

2、标识单位。数据对象 是具有相同性质的数据元素的集合。3. 数据结构 指的是数据元素之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容：数据的规律结构、数据的储备结构、数据的运算数据的规律结构是从规律关系上描述数据，与数据元素的储备结构无关，是独立于运算机的。数据的规律结构分类:线性结构和非线性结构。线性表 是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。数据元素及其关系在运算机内的储备方式，称为数据的储备结构（物理结构）。数据的储备结构是规律结构用运算机语言的实现，它依靠于运算机语言。 数据的运算 。最常用的检索、插入、删除、更新、

3、排序等。4. 数据的四种基本储备方法:次序储备、链接储备、索引储备、散列储备（ 1）次序储备：通常借助程序设计语言的数组 描述。（ 2）链接储备：通常借助于程序语言的指针来描述。（ 3）索引储备：索引表由如干索引项组成。关键字是能唯独标识一个元素的一个或多个数据项的组合。（ 4）散列储备：该方法的基本思想是：依据元素的关键字直接运算出该元素的储备的址。5. 算法必需满意5 个准就： 输入 ， 0 个或多个数据作为输入。输出 ，产生一个或多个输出。有穷性 ，算法执行有限步后终止。 确定性 ，每一条指令的含义都明确。可行性 ，算法是可行的。算法与程序的区分：程序必需依靠于运算机程序语言，而一个算法

4、可用自然语言、运算机程序语言、数学语言或商定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal 和 类 C 。6. 评判算法的优劣：算法的 正确性 是第一要考虑的。此外，主要考虑如下三点： 执行算法所耗费的时间，即时间复杂性。 执行算法所耗费的储备空间，主要是帮助空间，即空间复杂性。 算法应易于懂得、易于编程，易于调试等，即可读性和可操作性。以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。7. 算法求解问题的输入量 称为问题的规模, 用一个正整数n 表示。23kn8. 常见的时间复杂度按数量级递增排列依次为：常数阶 01 、对数阶 0log 2n 、线性阶 0n 、

5、线性对数阶0nlog 2n 、可编辑资料 - - - 欢迎下载精品名师归纳总结平方阶 0n 立方阶 0n 、 k 次方阶 0n 、指数阶02 和阶乘阶0n.。可编辑资料 - - - 欢迎下载精品名师归纳总结9. 一个算法的空间复杂度Sn 定义为该算法所耗费的储备空间，它是问题规模n 的函数 , 它包括储备算法本身所占的储备空间、算法的输入输出数据所占的储备空间和算法在运行过程中暂时占用的储备空间。其次章线性表1. 数据的运算是定义在规律结构上的，而运算的详细实现是在储备结构上进行的。2. 只要确定了线性表储备的起始位置，线性表中任意一个元素都可随机存取，所以次序表是一种随机存取结构。3. 常见

6、的线性表的基本运算:(1) 置空表 InitList（ L） 构造一个空的线性表L。(2) 求表长 ListLength（ L）求线性表L 中的结点个数，即求表长。(3) GetNode （ L， i ） 取线性表L 中的第 i 个元素。(4) LocateNode（ L，x）在 L 中查找第一个值为x 的元素，并返回该元素在L 中的位置。如L 中没有元素的值为x ，就返回 0 值。(5) InsertList（ L，i ， x ）在线性表L 的第 i 个元素之前插入一个值为x 的新元素，表L 的长度加1。 6DeleteList（ L，i ）删除线性表L 的第 i 个元素，删除后表L 的长度

7、减1。4. 次序储备方法：把线性表的数据元素按规律次序依次存放在一组的址连续的储备单元里的方法。次序表（ SequentialList ）：用次序储备方法储备的线性表称为次序表。次序表 是一种 随机存取结构 , 次序表的特点是规律上相邻的结点其物理位置亦相邻。次序表中结点ai的储备的址 : LOC （ ai ） = LOC（a1 ）+（ i-1 ） *c1i n，可编辑资料 - - - 欢迎下载精品名师归纳总结精品文档学习资料 名师精选 - - - - - - - - - -第 1 页，共 20 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料收集

8、于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结5. 次序表上实现的基本运算：（ 1）插入： 该算法的平均时间复杂度是On ，即在次序表上进行插入运算，平均要移动一半结点（n/2 ）。在第 i 个位置插入一个结点的移动次数为n-i+1（ 2）删除 ：次序表上做删除运算，平均要移动表中约一半的结点（n-1 ） /2 ，平均时间复杂度也是On 。删除第 i 个结点移动次数为n-i6. 采纳链式储备结构可以防止频繁移动大量元素。一个单链表可由头指针唯独确定，因此单链表可以用头指针的名字来命名。生

9、成结点变量的标准函数p=ListNode*mallocsizeofListNode。/函数 malloc安排一个类型为ListNode的结点变量的空间, 并将其首的址放入指针变量p 中释放结点变量空间的标准函数freep。 / 释放 p 所指的结点变量空间结点重量的拜访方法二： p- data 和 p- next指针变量p 和结点变量 *p 的关系 :指针变量p 的值结点的址,结点变量 *p 的值结点内容7. 建立单链表 :（ 1） 头插法建表： 算法： p=ListNode *mallocsizeofListNode; p-data=ch; /将读入的数据放入新结点的数据域中 / 生成新结点

10、p-next=head;head=p;（ 2） 尾插法建表： 算法：p=ListNode *mallocsizeofListNode; / 生成新结点p-data=ch; /将读入的数据放入新结点的数据域中if head=NULLhead=p;/新结点插入空表 else rear-next=p;/ 将新结点插到*r 之后 rear=p; / 尾指针指向新表尾（ 3） 尾插法建带头结点的单链表：头结点及作用：头结点是在链表的开头结点之前附加一个结点。它具有两个优点:由于开头结点的位置被存放在头结点的指针域中, 所以在链表的第一个位置上的操作就和在表的其它位置上操作一样 , 无须进行特殊处理;无论

11、链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。头结点数据域的阴影表示该部分不储备信息。在有的应用中可用于存放表长等附加信息。详细算法： r=head;/尾指针初值也指向头结点whilech=getchar.=ns=ListNode *mallocsizeofListNode;/生成新结点 s-data=ch;/将读入的数据放入新结点的数据域中 r-next=s;r=s;可编辑资料 - - - 欢迎下载精品名师归纳总结精品文档学习资料 名师精选 - - - - - - - - - -第 2 页，共 20 页 - - - - - - -

12、 - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料收集于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结r-next=NULL;/终端结点的指针域置空，或空表的头结点指针域置空以上三个算法的时间复杂度均为On 。8. 单链表上的查找： （带头结点）（ 1）按结点序号查找：序号为0 的是头结点。算法： p=head;j=0;/从头结点开头扫描whilep-next&jnext为 NULL 或 i=j为止p=p-next; j+;ifi=j return p;/找到了第i 个结点e

13、lse return NULL;/当 i0 时，找不到第i 个结点时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=On（ 2）按结点值查找：详细算法： ListNode *p=head-next;/从开头结点比较。表非空，p 初始值指向开头结点whilep&p-data.=key/直到 p 为 NULL或 p-data为 key 为止p=p-next;/扫描下一结点return p;/如 p=NULL，就查找失败，否就p 指向值为 key 的结点时间复杂度为：On9. 插入运算：插入运算是将值为x 的新结点插入到表的第i 个结点的位置上，即插入到ai-1 与 ai 之间。s=ListN

14、ode *mallocsizeofListNode;s-data=x; s-next=p-next; p-next=s;算法的时间主要耗费在查找结点上，故时间复杂度亦为On 。10. 删除运算r=p-next; / 使 r 指向被删除的结点ai p-next=r-next ;/将 ai 从链上摘下freer; / 释放结点ai 的空间给储备池算法的时间复杂度也是O（ n）.p 指向被删除的前一个结点。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。11. 单循环链表 在单链表中，将终端结点的指针域NULL 改为指向表头结点或开头结点即可。判定空链表的条件是 head=head-next

15、;12. 仅设尾指针的单循环链表:用尾指针rear表示的单循环链表对开头结点a1 和终端结点an 查找时间都是O1 。而表的操作常常是在表的首尾位置上进行，因此，有用中多采纳尾指针表示单循环链表。判定空链表的条件为rear=rear-next;13. 循环链表： 循环链表的特点是无须增加储备量，仅对表的链接方式稍作转变，即可使得表处理更加便利敏捷。如在尾指针表示的单循环链表上实现，就只需修改指针，无须遍历，其执行时间是O1 。可编辑资料 - - - 欢迎下载精品名师归纳总结精品文档学习资料 名师精选 - - - - - - - - - -第 3 页，共 20 页 - - - - - - - -

16、 - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料收集于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结详细算法：LinkList ConnectLinkList A,LinkList B/假设 A， B为非空循环链表的尾指针 LinkList p=A-next;/储存 A 表的头结点位置A-next=B-next-next;/ B 表的开头结点链接到A 表尾 freeB-next;/释放 B 表的头结点B-next=p;/return B;/返回新循环链表的尾指针循环链表中没有N

17、ULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p 或 p- next 是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点动身，只能拜访到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点动身都可拜访到表中全部结点，这一优点使某些运算在单循环链表上易于实现。14. 双向链表 :双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点的址外，仍增加一个指向其直接前趋的指针域prior。双链表由头指针head 惟一确定的。带头结点的双链表的某些运算变得便利。将头结点和尾结点链接起来，为双（向）循环链表

18、。15. 双向链表的前插和删除本结点操作双链表的前插操作void DInsertBeforeDListNode *p,DataType x/在带头结点的双链表中，将值为x 的新结点插入*p之前，设pNULLDListNode *s=mallocsizeofDListNode;/s-data=x;/s-prior=p-prior;/s-next=p;/p-prior-next=s;/p-prior=s;/ 双链表上删除结点*p 自身的操作可编辑资料 - - - 欢迎下载精品名师归纳总结精品文档学习资料 名师精选 - - - - - - - - - -第 4 页，共 20 页 - - - - -

19、- - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料收集于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结void DDeleteNodeDListNode *p/在带头结点的双链表中，删除结点*p ，设 *p 为非终端结点p-prior-next=p-next;/p-next-prior=p-prior;/freep; /与单链表上的插入和删除操作不同的是，在双链表中插入和删除必需同时修改两个方向上的指针。上述两个算法的时间复杂度均为O1 。16. 次序表和链表比较时间性

20、能： a、线性表：常常性的查找。b 、链式储备结构：常常插入删除操作。空间性能： a、对数据量大小事先能够知道的用线性表。b 、数据量变化较大的用链式储备结构。储备密度越大，储备空间的利用率越高。明显，次序表的储备密度是1，链表的储备密度确定小于1。第三章栈和队列1. 栈称为 后进先出 （ Last In First Out）的线性表，简称为LIFO 表 。栈是运算受限的线性表，次序栈也是用数组表示的。进栈操作： 进栈时，需要将S- top 加 1， S- top=StackSize-1表示栈满 上溢 现象 - 当栈满时，再做进栈运算产生空间溢出的现象。退栈操作： 退栈时，需将S- top 减

21、 1，S- topfront=Q-rear=0;判队空 :return Q-rear=Q-front;判队满 :return Q-rear+1%QueueSize=Q-front; 入队Q-dataQ-rear=x;/新元素插入队尾Q-rear=Q-rear+1%QueueSize; 出队temp=Q-dataQ-front;Q-front=Q-front+1%QueueSize;/循环意义下的头指针加1 return temp;取队头元素return Q-dataQ-front;6. 队列的链式储备结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。为了简化处理，在队头结点之前附加一个

22、头结点，并设队头指针指向此结点。链队列的基本运算: （带头结点）（ 1） 构造空队： Q-rear=Q-front。Q-rear-next=NULL;（ 2） 判队空： return Q-rear=Q-front;可编辑资料 - - - 欢迎下载精品名师归纳总结精品文档学习资料 名师精选 - - - - - - - - - -第 6 页，共 20 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料收集于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总

23、结（ 3） 入队： QueueNode *p=QueueNode *mallocsizeofQueueNode;/申请新结点p-data=x;p-next=NULL;Q-rear-next=p;/*p链到原队尾结点后Q-rear=p;/队尾指针指向新的尾（ 4） 出队：当队列长度大于1 时，只需修改头结点指针，尾指针不变s=Q-front-next;Q-front-next=s-next; x=s-data;frees; return x;当队列长度等于1 时，不仅要修改头结点指针，仍要修改尾指针s=Q-front-next; Q-front-next=NULL;Q-rear=Q-front;

24、 x=s-data;frees; return x;（ 5） 取队头元素： return Q-front-next-data;由于有头结点，所以用了next和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。7. 用运算机来处理运算算术表达式问题，第一要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。第四章多维数组和广义表1. 数组的次序储备方式: 一般采纳次序储备方法表示数组。（ 1）行优先次序a 11,a 12,a 1n,a 21 ,a 22 ,a 2

25、n,， am1,a m2,， amn（ 2）列优先次序a 11,a 21,a m1,a 12 ,a 22 ,a m2,， a1n,a 2n ,， amn Pascal 和 C 语言是按行优先次序储备的，而Fortran语言是按列优先次序储备的。按行优先次序储备的二维数组Amn的址运算公式LOCaij =LOCa11+i-1 n+j - 1 d 注：此公式下界为1，如下界为0，就公式变为i n+j 按列优先次序储备的二维数组Amn的址运算公式LOCaij =LOCa11+j-1 m+i - 1 d 注：此公式下界为1，如下界为0，就公式变为 j m+i按行优先次序储备的三维数组Amnp的址运算公

26、式LOCaijk =LOCa111+i-1 np+j- 1 p+k - 1 d 注 ： 此 公 式 下 界 为1 ， 如 下 界 为0 ， 就 公 式 变 为i n p+j p+k2. 为了节约储备空间，可以对矩阵中有很多值相同或值为零的元素的矩阵，采纳压缩储备。特殊矩阵是指相同值的元素或零元素在矩阵中的分布有肯定的规律。常见的有对称矩阵、三角矩阵。（ 1）对称矩阵在一个 n 阶方阵 A 中，如元素满意下述性质：a ij =aji0i ，j n-1称为 n 阶对称矩阵，它的元素是关于主对角线对称的，所以只需要储备矩阵上三角或下三角元素即可，让两个对称的元素共享一个储备空间。矩阵元素aij 和数

27、组元素sa 【k】之间的关系是k=i i+1/2+j ij0knn+1 /2-1k=jj+1/2+i i j0knn+1 /2-1对称矩阵的的址运算公式：LOCaij =LOCsa0+II+1/ 2+J d，其中I=maxi,j， J=mini,j（ 2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指它的下三角 不包括主角线中的元素均为常数c 或零。下三角矩阵的主对角线上方均为常数c 或零。一般情形，三角矩阵的常数c 均为零。 三角矩阵的压缩储备：三角矩阵中的重复元素c 可共享一个储备空间，其余的元素正好有nn+1 /2 个，因此，三角矩阵可压缩储备在一维数组sann+

28、1/2+1中，其中 c 存放在数组的最终一个元素中。上三角矩阵中aij 和 sak之间的对应关系k=i 2n -i+1/2+j-i当 i jk=nn+1/2当i j下三角矩阵中aij 和 sak之间的对应关系k=i i+1/2+j当 i jk=nn+1/2当i j三角矩阵的压缩储备结构是随机存取结构。3. 稀疏矩阵 : 设矩阵 Amn中有 s 个非零元素，如s 远远小于矩阵元素的总数，就称A 为稀疏矩阵。为了节约储备单元，可用压缩储备方法只储备非零元素。由于非零元素的分布一般是没有规律的，因此在储备非零元素的同时，仍必需储备非零元素所在的行、列位置，所以可用三元组i ， j ，aij 来确定非

29、零元素。稀疏矩阵进行压缩储备通常有两类方法：次序储备 三元组表 和链式储备 十字链表 。稀疏矩阵的压缩储备会失去随机存取功能。可编辑资料 - - - 欢迎下载精品名师归纳总结精品文档学习资料 名师精选 - - - - - - - - - -第 7 页，共 20 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料收集于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结4. 广义表是线性表的推广, 又称列表。广义表 是 nn 0 个元素a1， a2， a

30、i ， an 的有限序列。其中ai 或者是原子或者是一个广义表。广义表通常用圆括号括起来，用逗号分隔其中的元素。为了区分原子和广义表，书写时用大写字母表示广义表 ，用小写字母表示原子 。如广义表Ls 非空n 1 ，就al 是 LS 的表头，其余元素组成的表a 1， a2， an 称为 Ls 的表尾。广义表具有递归和共享的性质广义表的深度：一个表绽开后所含括号的层数称为广义表的深度。19. 广义表是一种多层次的线性结构，实际上这就是一种树形结构。广义表的两个特殊的基本运算：取表头 headLs和取表尾tailLs.任何一个非空广义表的表头可以是原子，也可以是子表，而其表尾必定是子表。head=a

31、 ， b=a ，taila， b=b对非空表A 和y ，也可连续分解。留意 : 广义表 和不同。前者是长度为0 的空表，对其不能做求表头和表尾的运算。而后者是长度为l 的由空表作元素的广义表，可以分解得到的表头和表尾均是空表 。广义表是一种有层次的非线性结构，通常采纳链式储备结构，每个元素用一个结点表示，结点由3 个域构成，其中一个是 tag 标志位，用来区分结点是原子仍是子表，当 tag 为零时结点是子表，其次个域为 slink ，用以存放子表的的址。当 tag 为 1 时结点是原子，其次个域为 data ，用以存放元素值。第五章树和二叉树1. 树的表示法：最常用的是树形图表示法。仍有3 种

32、嵌套集合、凹形、广义表。树结构的基本术语（ 1）结点的度 Degree树中的一个结点拥有的子树数称为该结点的度Degree 。一棵树的 度是指该树中结点的最大度数。度为零的结点称为叶子 Leaf或终端结点 。度不为零的结点称分支结点 或非终端结点 。除根结点之外的分支结点统称为内部结点 。根结点又称为开头结点 。（ 2） 路径（ path ） 如树中存在一个结点序列k 1，k 2， k i ，使得k i 是 ki+1 的 双亲 1 ij，就称该结点序列是从 kl 到 k j 的一条 路径 Path 。一个结点的祖先是从根结点到该结点路径上所经过的全部结点，而一个结点的子孙就是以该结点为根的子树

33、中的所有结点。结点的层数 Level从根起算：根的层数为1，其余结点的层数等于其双亲结点的层数加1。双亲在同一层的结点互为堂兄弟 。树中结点的最大层数称为树的高度 Height或深度 Depth 。如将树中每个结点的各子树看成是从左到右有次序的 即不能互换 ，就称该树为有序树 OrderedTree。否就称为 无序树 UnoderedTree。如不特殊指明，一般争论的树都是有序树。森林 Forest是 mm0 棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林。反之，加上一个结点作树根，森林就变为一棵树。3. 二叉树与度数为2 的有序树不同：在有序树中，虽然一个结点的孩子

34、之间是有左右次序的，但是如该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。二叉树的性质：可编辑资料 - - - 欢迎下载精品名师归纳总结性质 1 二叉树第i 层上的结点数目最多为2ki-1i 1 。例如5 层的二叉树，第5 层上的结点数目最多为2 =1645可编辑资料 - - - 欢迎下载精品名师归纳总结性质 2 深度为 k 的二叉树至多有2 -1 个结点 k 1 。例如深度为5 的二叉树，至多有2 -1=31 个结点性质 3 在任意 - 棵二叉树中，如终端结点的个数为n0，度为 2 的结点数为n2，就 no=n2+1。例如一棵深度为4 的二叉可编辑资料 -

35、 - - 欢迎下载精品名师归纳总结精品文档学习资料 名师精选 - - - - - - - - - -第 8 页，共 20 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料收集于网络如有侵权请联系网站删除感谢资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结树（ a），其终端结点数n0 为 8, 度为 2 的结点树为7，就 8=7+1， no=n2+1 成立（ b）其终端结点数n0 为 6, 度为 2 的结点树为5，就 6=5+1， no=n2+1 成立可编辑资料 - - - 欢

36、迎下载精品名师归纳总结k叉树。满二叉树的特点：满二叉树：一棵深度为k 且有 2 -1 个结点的二又树称为满二可编辑资料 - - - 欢迎下载精品名师归纳总结（ 1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（ 2）满二叉树中不存在度数为1 的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。完全二叉树：如一棵深度为k 的二叉树，其前k-1层是一棵满二叉树，而最下面一层上的结点都集中在该层最左边的如干位置上，就此二叉树称为完全二叉树。特点：（ 1） 满二叉树是完全二叉树，完全二叉树不肯定是满二叉树。（ 2） 在满二叉树的最下一层上，从最右边开头连续删去如干结点后得到的二叉树仍旧是一棵完全二叉树。67（ 3） 在完全二叉树中，如某个结点没有左孩子，就它肯定没有右孩子，即该结点必是叶结点。性质 4具有 n 个结点的完全二叉树的深度为。.logn .+1 或. logn+1.可编辑资料 -