下载文档原格式
第一张概论1.1 引言两项基本任务：数据表示，数据处理软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。
机外表示------逻辑结构------存储结构处理要求-----基本运算和运算-------算法1.2.1 数据，逻辑结构和运算数据：凡是能够被计算机存储，加工的对象通称为数据数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。
又称元素、顶点、结点、记录。
数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当作一个整体对待。
又称字段或域，是数据不可分割的最小标示单位。
1.2.2 数据的逻辑结构逻辑关系：是指数据元素之间的关联方式，又称“邻接关系”逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。
即数据的组织形式。
四种基本逻辑结构：1 集合：任何两个结点间没有逻辑关系，组织形式松散2 线性结构：结点按逻辑关系依次排列成一条“锁链”3 树形结构：具有分支，层次特性，形态像自然界中的树4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。
注意点:1.逻辑结构与数据元素本身的形式，内容无关。
2.逻辑结构与数据元素的相对位置无关3.逻辑结构与所含结点个数无关。
运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。
加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。
引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。
引用：查找，读取加工：插入，删除，更新同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。
假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。
绝密 考试结束前2023年10月高等教育自学考试数据结构导论试题课程代码:021421.请考生按规定用笔将所有试题的答案涂㊁写在答题纸上㊂2.答题前,考生务必将自己的考试课程名称㊁姓名㊁准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上㊂选择题部分注意事项:每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑㊂如需改动,用橡皮擦干净后,再选涂其他答案标号㊂不能答在试题卷上㊂一㊁单项选择题:本大题共15小题,每小题2分,共30分㊂在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出㊂1.时间复杂度的常数阶表示为A.O(1)B.O(n)C.O(n2)D.O(2n)2.下列关于单链表的描述,错误∙∙的是A.所有结点通过指针链接形成链表B.头指针变量不一定非要用h e a d来标识C.尾结点指针域的值N U L L称为空指针D.通常用尾指针来表示一个单链表3.线性表实现顺序存储可使用A.栈B.队列C.数组D.链表4.设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为A.p n e x t=p n e x t n e x tB.p=p n e x tC.p=p n e x t n e x tD.p n e x t=p5.出队列操作使用的赋值语句是A.S Q.r e a r=S Q.r e a r+1B.S Q.r e a r=S Q.r e a r-1C.S Q.f r o n t=S Q.f r o n t+1D.S Q.f r o n t=S Q.f r o n t-16.在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以t o p为栈顶指针,当栈未满时进行进栈操作,此时A.t o p不变B.t o p--C.t o p++D.t o p=07.带头结点链队列的头指针和尾指针分别为f r o n t和r e a r,则判断队列空的条件为A.f r o n t==r e a rB.f r o n t!=N U L LC.r e a r!=N U L LD.f r o n t==N U L L8.深度为k(kȡ1)的二叉树的结点数最多为A.2k-1B.2k-1C.2k+1D.2k+19.下列关于树形结构的描述,正确的是A.树形结构是线性结构B.树中每个结点可以有多个直接前驱结点C.树可以用顺序存储D.树中每个结点只能有一个直接后继结点10.对任何一棵二叉树,若度数为0的结点(叶结点)个数为n0,度数为2的结点个数为n2,则n0等于A.0B.n2-1C.n2 D.n2+111.设有10个顶点的无向图,若它为连通图,则它具有的边数最少为A.9B.10C.11D.1212.设含有n个顶点,e条弧的有向图G采用邻接表存储,则拓扑排序算法的时间复杂度为A.O(n)B.O(n+e)C.O(n2)D.O(nˑe)13.当查找表中有n个数据元素时,假设P i(i=1,2, ,n)为查找第i个元素的概率,在P i等概率的条件下,顺序查找算法的平均查找长度为A.n/2B.(n+1)/2C.nD.n+114.二维数组A以行为主序存储,每个元素占1个存储单元㊂若元素A[1][1]的存储地址是420,A[3][3]的存储地址是446,则A[5][5]的存储地址是A.470B.471C.472D.47315.冒泡排序属于A.插入排序B.归并排序C.选择排序D.交换排序非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上㊂二㊁填空题:本大题共13小题,每小题2分,共26分㊂16.在数据库中数据项又称为字段或 һ ㊂17.在单链表存储结构中,线性表的表长等于单链表中 һ 的结点个数㊂18.二叉树的顺序存储结构可以用 һ 维数组来实现㊂19.在操作系统中,为了保持多个进程P1㊁P2㊁P3和P4按某种次序依次执行,需要一个 һ来实现这个过程㊂20.对称矩阵有近一半元素可以通过其对称元素获得,因此可将含有n2个元素的对称矩阵压缩存储到含有 һ 个元素的一维数组中㊂21.设有一个带头结点的链栈,其头指针为h e a d,现有一个新结点入栈,指向该结点的指针为p,则入栈操作为 һ 和h e a d n e x t=p㊂22.满二叉树一定是 һ 二叉树㊂23.在树形结构中,结点间具有 һ 关系㊂24.在图中,序列中顶点不重复出现的路径称为 һ 路径㊂25.D i j k s t r a算法用于求 һ 问题㊂26.求最小生成树有 һ 方法和K r u s k a l方法㊂27.若在查找过程中,向表中插入不存在的数据元素,或者从表中删除某个数据元素,则称此类表为 һ 查找表㊂28.在二分查找㊁索引顺序查找和散列查找三种查找方法中,平均查找长度与元素个数没有关系的查找方法是 һ ㊂三㊁应用题:本大题共5小题,每小题6分,共30分㊂29.设有一个链栈的输入序列为A㊁B㊁C,当输出序列分别为A B C和B C A时,请写出对应的进栈和出栈过程㊂30.设有一森林F如题30图所示,请分别写出先序遍历和中序遍历的序列㊂题30图31.如题31图所示长度为13的散列表,其散列函数为H(k e y)=k e y m o d13,在表中已填入键值分别为16,30,54的元素㊂(1)现要插入键值为29的元素,应用线性探测法,计算填入散列表中单元的序号㊂(要求给出求解过程)(2)线性探测法中,如何减少堆积的机会?0123456789101112541630题图32.如题32图所示的图结构,请写出以10为源点的广度优先搜索得到的顶点访问序列,并画出搜索过程图㊂(同等情况下,值小的结点优先访问)题32图33.给定有序表D={006,087,155,188,220,465,505,508,511,586,656,670,700,766},用二分查找法在D中查找511,试给出查找过程㊂四㊁算法设计题:本大题共2小题,每小题7分,共14分㊂34.编制函数求1+2+ +n㊂35.已知循环队列的结构类型如下:t y p e d e f s t r u c t c y c q u e u e{D a t a T y p e d a t a m a x s i z ei n t f r o n t r e a r}C y c Q u eC y c Q u e C Q设计入队列的算法㊂绝密 启用前2023年10月高等教育自学考试全国统一命题考试数据结构导论试题答案及评分参考(课程代码 02142)一㊁单项选择题:本大题共15小题,每小题2分,共30分㊂1.A2.D3.C4.A5.C6.C7.B8.B9.C10.D11.A 12.B 13.B 14.C 15.D 二㊁填空题:本大题共13小题,每小题2分,共26分㊂16.域17.数据元素18.一19.队列20.n (n +1)/221.pn e x t =h e adn e x t22.完全23.层次24.简单25.单源最短路径26.P r i m27.动态28.散列查找三㊁应用题:本大题共5小题,每小题6分,共30分㊂29.输出A B C :A 进,A 出,B 进,B 出,C 进,C 出;(3分)输出B C A :A 进,B 进,B 出,C 进,C 出,A 出㊂(3分)30.先序序列为A B C D E F G H J I ;(3分)中序序列为B C D A F E J H I G ㊂(3分)31.(1)散列函数求出其散列地址为3,在地址3上面已有元素16,发生冲突㊂(1分)应用线性探测法,得到下一个地址为d +1=4,仍冲突,(1分)则再求下一个地址d +2=5,这个位置上没有元素,将元素填入散列表中序号为5的单元㊂(2分)(2)应设法使后继散列地址尽量均匀地分散在整个散列表中㊂(2分)32.序列:10,20,30,50,40,60(3分)答32图(3分)33.01(1)006 02087 03155 04188 05220 06465 07505 08508 09511 10586 11656 12670 13700 14766ʏl o wʏm i dʏh i gh (2分)(2)006 087 155 188 220 465 505 508 511 586 656 670 700 766ʏʏʏl o w m i d h i gh (2分)(3)006 087 155 188 220 465 505 508 511 586 656 670 700 766ʏʏʏl o w m i d h i gh (2分)四㊁算法设计题:本大题共2小题,每小题7分,共14分㊂34.i n t f a c t 1(i n t n ){ i n t i ,j ,t e m p ,s ; s =0;(2分) f o r (i =1;i <=n ;i ++) {t e m p =1;(3分)f o r (j =1;j <=i ;j ++) t e m p =t e m p *j; s =s +t e m p ;}r e t u r n s ;}(2分)(注:答案不唯一,正确即可)35.i n tE n Q u e u e (C y c Q u eC Q ,D a t a T y pex ){i f ((C Q.r e a r +1)%m a x s i z e ==C Q.f r o n t ) {e r r o r ( 队列满 );r e t u r n0;}(3分)e l s e { C Q.r e a r=(C Q.r e a r +1)%m a x s i z e ; C Q.d a t a [C Q.r e a r ]=x ;(3分)r e t u r n 1; }分)。
自考02142《数据结构导论》真题及（2022.4）自考02142《数据结构导论》真题及答案解析（2022.4）1.[单选题] 下列几种时间复杂度中，阶数最小的是（）A.O(log2n)B.O(n)C.O(n2)D.O(1)2.[单选题] 栈和队列的共同特点是（）A.都是线性表B.先进先出C.后进先出D.只能插入操作3.[单选题] 假设一个10x 10的上三角矩阵A按照列优先顺序压缩在一维数组B中，则B数组的大小应为（）A.50B.55C.100D.1014.[单选题] 一个栈的入栈序列是a，b，c，d，e，则栈可能的输出序列是（）A.edcabC.abcdeD.dceab5.[单选题] 假定一个顺序存储的循环队列的队头和队尾指针分别为f 和r，则判断队空的条件为（）A.f==NULLB.f==rC.r+1==fD.f+1== r6.[单选题] 如果结点A有2个兄弟结点，结点B为A的双亲，则结点B的度为（）A.2B.3C.4D.57.[单选题] 二叉树的中序遍历中，结点P排在结点Q之前的条件是在二叉树中（）A.P在Q的左边B.P在Q的右边C.P是Q的祖先D.P是Q的子孙8.[单选题] 二又树的第k层的结点数最多为（）B.2k+1C.2k-1D.2k+19.[单选题] A是7X4的二维数组，按行优先方式顺序存储元素A[0][0]的存储地址为1000，若每个元素占2个字节，则元素A[3][3]的存储地址为（）A.1026B.1028C.1030D.103210.[单选题] 在表长为n的顺序表上做删除运算，其平均时间复杂度为（）A.O(1)B.O(n)C.O(nlog2n)D.O(n/2)11.[单选题] 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A.eB.2eC.n2-e12.[单选题] 设顺序表的长度为n，则插入算法的平均移动次数约为（）A.nB.n/2C.n-1D.(n-1)/213.[单选题] 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134)，则用二分查找算法查找关键字90需要比较的关键字个数为（）A.1B.2C.3D.414.[单选题] 以下排序方法中，稳定的是（）A.直接插入排序和快速排序B.快速排序和冒泡排序C.直接选择排序和冒泡排序D.冒泡排序和直接插入排序15.[单选题] 对n个记录的文件进行快速排序，所需要的辅助存储空间的空间复杂度为（）A.O(1)B.O(n)C.O(1og2n)D.O(n2)16.[填空题] 1976年瑞士计算机科学家Niklaus Wirth 曾提出一个著名公式：程序=数据结构+____。
第一章概论第二章线性表第三章栈和队列第四章串第五章多维数组第六章树第七章图第八章排序第九章查找第一章概论1.数据：信息的载体,能被计算机识别、存储和加工处理。
2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。
3.数据结构：数据之间的相互关系，即数据的组织形式。
它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。
3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。
常用的运算：检索/插入/删除/更新/排序。
4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
数据的存储结构是逻辑结构用计算机语言的实现。
5.数据类型：一个值的集合及在值上定义的一组操作的总称。
分为：原子类型和结构类型。
6.抽象数据类型：抽象数据的组织和与之相关的操作。
优点：将数据和操作封装在一起实现了信息隐藏。
7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。
8.数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。
（2）非线性结构，一个结点可能有多个直接前趋和后继。
9.数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。
2）链接存储，结点间的逻辑关系由附加指针字段表示。
3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。
4）散列存储，按结点的关键字直接计算出存储地址。
10.评价算法的质量：1正确性；算法应能正确地事先预定的功能。
2易读性；算法应易于阅读和理解，以便于调试和扩充。
3健壮性；当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。
4高效率；即达到所需的时间和空间性能。
11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。
全国自学考试数据结构导论试题及答案4套第一套试题一、选择题（每题4分，共40分）1. 下列哪个数据结构是一种非线性结构？A. 数组B. 栈C. 队列D. 树2. 下列哪种算法不适用于解决排序问题？A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序3. 在数据结构中，堆的底层实现通常采用哪种数据结构？A. 数组B. 栈C. 链表D. 队列4. 下列哪个选项是描述图结构的准确说法？A. 图结构是一种线性结构B. 图结构由节点和指向节点的边构成C. 图结构不能存储数据D. 图结构不支持插入和删除操作5. 下列哪个排序算法具有最坏时间复杂度为O(nlogn)？A. 冒泡排序B. 插入排序C. 选择排序D. 希尔排序二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。
2. 图的两个顶点之间的路径长度是指连接这两个顶点所需的____数。
3. 链表是一种____结构。
4. 快速排序算法的核心思想是____。
5. 栈和队列都属于线性结构，其主要区别在于____操作的限制。
三、简答题（每题10分，共30分）1. 请简要描述栈的特点以及栈的应用场景。
2. 请简要介绍图的基本概念，并说明图的应用领域。
3. 请解释递归算法的原理，并给出一个使用递归算法解决问题的例子。
四、编程题（共30分）请使用任意编程语言实现一个简单的栈数据结构，并编写测试代码进行验证。
第二套试题一、选择题（每题4分，共40分）1. 在二叉搜索树中，中序遍历的结果是____。
A. 升序排列B. 降序排列C. 随机排序D. 不确定的排序2. 在哈希表结构中，解决冲突问题的常用方法是____。
A. 线性探测B. 链地址法C. 开放地址法D. 扩容法3. AVL树是一种____。
A. 二叉搜索树B. 哈希表C. B树D. 红黑树4. 以下哪个算法不是用于解决查找问题？A. 二分查找B. 深度优先搜索C. 广度优先搜索D. 哈希查找5. 以下哪个数据结构不支持随机访问元素？A. 数组B. 栈C. 链表D. 哈希表二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。
全国自考（数据结构）模拟试卷4(题后含答案及解析)题型有：1. 单项选择题 2. 填空题 3. 解答题 4. 算法阅读题 5. 算法设计题单项选择题1．对文件进行直接存取的是根据( )A．逻辑记录号去存取某个记录B．逻辑记录的关键字去存取某个记录C．逻辑记录的结构去存取某个记录D．逻辑记录的具体内容去存取某个记录正确答案：A2．一个栈的人栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )A．e d c b aB．d e c b aC．d c e a bD．a b c d e正确答案：C3．带头结点的单链表head为空的判断条件是( )A．head=NULLB．head—＞next=NULLC．head—＞next=headD．head!=NULL正确答案：B4．非空的单循环链表L的尾结点P↑，满足( )A．P↑.next=NULL;B．P=NULL;C．P↑.next=L;D．P=L正确答案：C5．在下面的排序方法中，不需要通过比较关键字就能进行排序的是( ) A．箱排序B．快速排序C．插入排序D．希尔排序正确答案：A6．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等正确答案：B7．从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
A．nB．n/2C．(n-1)/2D．(n+1)/2正确答案：D8．在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )A．f—＞next=c;f=s;B．r—＞next=s;r=s;C．s—＞next=r;r= sD．s—＞next=f,f=s;正确答案：B9．设散列函数为H(k)=k mod7，一组关键码为23,14,9,6,30,12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为( )A． B． C． D． 正确答案：B10．邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( ) A．先序遍历B．中序遍历C．后序遍历D．按层遍历正确答案：A11．线索二叉树是一种( )结构。
自考02142《数据结构导论》真题及（2022.10）自考02142《数据结构导论》真题及答案解析（2022.10）1.[单选题] 设输入序列为ABC，输出为ABC,则经过的栈操作为（）。
A.push，pop，push，push，pop，popB.push，push，pop，pop，push，popC.push，push，push，pop，pop，popD.push，pop，push，pop，push，pop2.[单选题] 设有一循环队列CQ，队列的长度为maxsize，则该循环队列满的条件为（）。
A.（CQ.rear+1)%maxsize==CQ.frontB.CQ.rear==CQ.frontC.（CQ.rear+1)%maxsize==CQ.rearD.CQ.rear==NULL3.[单选题] 树的相关术语中，兄弟指（）。
A.祖先相同的结点B.根相同的结点C.度数相同的结点D.父结点相同的结点4.[单选题] 执行进栈操作，在元素X进栈前需要进行的操作是（）。
A.判断栈是否满，若栈未满，top值加1B.判断栈是否空，若栈未空，top值加1C.判断栈是否满，若栈未满，top值减1D.判断栈是否空，若栈未空，top值减15.[单选题] 森林有两种遍历方法，分别是（）。
A.先序遍历森林和中序遍历森林B.先序遍历森林和后序遍历森林C.中序遍历森林和层次遍历森林D.后序遍历森林和层次遍历森林6.[单选题] 有向图中某顶点v的入度为2，出度为3，则该顶点的度为（）。
A.3B.4C.5D.67.[单选题] 无向图的邻接矩阵为（）。
A.对角矩阵B.对称矩阵C.稀疏矩阵D.一般矩阵8.[单选题] 对升序表进行二分查找，用给定值key与处在中间位置的数据元素T.elem[mid]的键值T.elem[mid].key进行比较，当key 32.[问答题] 给定数据序列{46，25，78，62，12，80}，试按元素在序列中的次序将它们依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。
第 4 章 树打印本页 通过本章的学习，要了解树的基本概念，熟悉二叉树的基本概念；了解树和二叉树的存储，重点掌握二叉树的二叉链表表示；熟悉二叉树的性质；掌握二叉树的遍历及其应用；了解树的遍历；熟悉树与林和二叉树之间的相互转换。
学习中概念要很好地掌握，二叉树的遍历算法也必须很好地掌握。
要把精力多放些在二叉树的性质和二叉树的遍历算法上。
4.1 树的基本概念 4.1.1 基本概念 （1）树的定义 树是n（n>0）个结点的有穷集合，满足： 1）有且仅有一个称为根的结点； 2）其余结点分成m（m≥0）个互不相交的非空集合T1，T2，…，Tm，这些集合中的每一个都是一棵树，称为根的子树。
（2）一些基本概念 树上结点的度：树上任一结点所拥有的子树的数目称为该结点的度； 树的度：树上所有结点中，结点度的最大值称为该树的度； 根结点：树上没有直接前趋的唯一结点称为该树的根结点； 叶子或终端结点：度为0的结点称为叶子或终端结点； 非终端结点或分枝结点：度大于0的结点称为非终端结点或分枝结点； 双亲或父结点：树中某结点的直接前趋结点称为该结点的双亲或父结点； 孩子或子结点：树中某结点的直接后继结点称为该结点的孩子或子结点； 兄弟：树中具有共同双亲或父结点的结点互为兄弟； 子孙和祖先：一棵树上的任何结点（不包括根结点自身）称为根的子孙，根结点是它们的祖先。
推而广之，树上某结点的后继结点被称为该结点的子孙，而树上某结点的前趋结点被称为该结点的祖先； 结点的层数：从根结点算起，根结点的层数为1，其它结点的层数是其双亲结点的层数加1； 树的高度或深度：树上所有结点层数的最大值称为该树的高度或深度。
4.1.2 树的基本运算 求根ROOT（T）：取树T的根结点； 求双亲PARENT（T，X）：取树T中结点X的双亲结点； 求孩子CHILD（T，X，i）：取树T中结点X的第i个孩子结点； 建树CREATE（X，T1，…，T k）：建立一棵以结点X为根，以T1，…，T k为第1，2，…，k棵子树的树； 剪枝DELETE（T，X，i）：删除树T上结点X的第i棵子树。
4.2 二叉树的基本概念 4.2.1 基本概念 （1）二叉树的定义： 二叉树是结点的有穷集合，它或是空集，或同时满足如下两个条件： 1）有且仅有一个称为根的结点； 2）其余结点分为两个互不相交的集合T1、T2，T1、T2都是二叉树，并且T1与T2有顺序关系（即T1在T2之前），它们分别称为根的左子树和右子树。
（2）一些基本概念 左子树：二叉树上任何结点的左子集称为该结点的左子树； 右子树：二叉树上任何结点的右子集称为该结点的右子树； 空二叉树：不含任何结点的二叉树称为空二叉树； 左孩子：二叉树上任何结点的左子树的根称为该结点的左孩子； 右孩子：二叉树上任何结点的右子树的根称为该结点的右孩子； 二叉树结点的度：二叉树上任一结点的孩子数为该结点的度； 二叉树的五种形态：二叉树具有五种基本形态，即：空树、单结点树、只有左子树的树、只有右子树的树和既有左子树又有右子树的树，如下： 4.2.2 二叉树的基本运算 求根ROOT（BT）：取二叉树BT的根； 求双亲PARENT（BT，X）：取二叉树BT中结点X的双亲； 求孩子CHILD（BT，X）：取二叉树BT中结点X的孩子； 建树CREATE（X，LBT，RBT）：建立以结点X为根，LBT为左子树，RBT为右子树的二叉树； 剪枝DELETE（BT，X）：删除二叉树BT上以结点X为根的子树； 初始化INITIATE（BT）:设置一棵空二叉树。
4.3 二叉树的性质 4.3.1 二叉树的共性 性质1：二叉树上每层的最大结点数：第i层的最大结点数是2（i-1）（i≥1）； 性质2：已知二叉树的层数后，二叉树上的最大结点数：深度为k（ｋ≥1）的二叉树，最多有2k－1个结点； 性质3：二叉树上，叶结点数（n0）与具有两个分枝的结点数（n2）间的关系：一棵二叉树的叶结点数是具有两个分枝的结点数加一（即：n0 = n2 + 1）。
4.3.2 完全二叉树的性质 （1）满二叉树和完全二叉树 在讨论完全二叉树的性质之前必须先搞清何为完全二叉树？这需先了解满二叉树。
满二叉树：具有2 k - 1个结点且深度为 k（k≥1）的二叉树。
完全二叉树：具有n（n≥1）个结点且深度为k（k≥1）的二叉树，其结点从上至下，从左到右顺序编号，与深度为k（k≥1）的满二叉树上的n个结点的编号相同时，称该二叉树为完全二叉树。
注意： ①只要结点之间的排列不连续，就不是完全二叉树。
②深度为k（k≥1）的完全二叉树比深度为k（k≥1）的满二叉树缺少的那部分结点都分布在第k层上，而且都在该层的左部。
③满二叉树是完全二叉树，而且是一种特殊的完全二叉树。
（a）满二叉树 （b） 完全二叉树 （2）完全二叉树的性质 性质4：完全二叉树的高度与它的结点数之间的关系：对于含有n个结点的二叉树,其高度（或深度）为log2（n）向下取整后加1； 性质5：顺序编号，顺序存储的完全二叉树的双亲结点和孩子结点间的编号（位置）关系：对于编号为i的结点,其双亲结点的编号为；左孩子的编号为2i（≤n）；右孩子的编号为2i+1（≤n）。
注意：对于C语言，因为顺序存储的完全二叉树的下标从0开始，即根结点的编号为0，所以性质5应该作些修改，即：对于编号为i的结点,其双亲结点的编号为；左孩子的编号为2i+1（<n）；右孩子的编号为2（i+1）（<n）。
由性质3和满二叉树的定义，可以计算一棵已知深度的满二叉树中，其非叶结点的个数是多少个。
例如设二叉树的根结点的层次为1，满二叉树中的深度为5，则由满二叉树的性质可知，深度为5的满二叉树上的最大结点数是25－1个，即为32－1＝31个。
满二叉树上只有两种结点，度为0的叶结点和度为2的分枝结点。
设叶结点树为n0，度为2的分枝结点数为n2，由性质3可知n0=n2+1，而满二叉树上的结点总数为n0+n2=n2+1+n2=2*n2+1=31，由此2*n2=31-1=30，所以n2=15。
即非叶结点数为15个。
4.4 二叉树的存储 4.4.1 二叉树的链式存储 链式存储分为二指针式存储和三指针式存储两种.二指针式存储时，链表结点由三个域构成，即存储信息的数据域和指向左孩子的左指针和指向右孩子的右指针；三指针式存储时，除与二指针存储相同的三个域外，附加一个指向双亲结点的指针。
一般情况下，二叉树都以两个指针的结点的链表形式存储，而且所有算法也是以此种存储为基础给出。
只有在需要经常访问结点的双亲的情况，使用三指针结点的链表存储二叉树才更合适。
（1）双指针存储的结点形式 lchild data rchild 二叉链表的类型定义如下： typedef struct btnode *bitreptr; struct btnode { datatype data; bitreptr lchild,rchild; }； bitreptr root; 最好改为如下定义，因为上述定义在C语言中申请内存空间时，认为结构btnode未定义，无法分配空间。
struct node { datatype data; struct node *lchild,*rchild; } btnode； typedef btnode *bitreptr; bitreptr root; 若二叉树为空，则root=NULL。
若某个结点的某个孩子不存在，则相应的指针为空。
具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余n+1个指针域为NULL（空）。
（2）三指针存储的结点形式lchild data parent rchild 三叉链表的类型定义如下： typedef struct ttnode *ttnodeptr; struct ttnode { datatype data; ttnodeptr lchild,rchild,parent; } ttnodeptr root; 同样，若二叉树为空，则root=NULL。
若某个结点的某个孩子不存在，则相应的指针为空。
但对于双亲指针而言，只有根结点的双亲指针为空，因为只有它无双亲。
具有n个结点的二叉树中，一共有3n个指针域，其中有n-1个用来指向结点的左右孩子，有n-1个用来指向结点的双亲，其余n+2个指针域为NULL（空）。
4.4.2 二叉树的顺序存储 顺序存储时，二叉树存放在一维数组中，关键问题是如何保持各结点之间的关系，即各个结点与它们的双亲结点和左、右孩子间的相对位置。
二叉树的性质5给定了这种关系。
完全二叉树的顺序存储可以既节约存储空间（每个数组元素中都存有树结点），又可以保证二叉树信息的完整性（由性质五）。
而非完全二叉树二者不能都得，即：要保证信息的完整性，就不能节约存储空间（可能要浪费大量空间）；若要节约存储空间就不能保证信息的完整性（不适用性质五）。
例如：下图的二叉树，如要节约空间，只能存储如下，但不能用“性质五”来决定结点间的亲子关系。
A B C 若要能用“性质五”来决定结点间的亲子关系，就要浪费空间，如下所示：A B C 4.5 二叉树的遍历 遍历二叉树实际上就是按一定的顺序“访问”二叉树上的各结点,使每个结点恰好被“访问”一次。
所谓“访问”一个结点，是指对该结点的数据域进行某种处理，而处理的内容依具体问题而定。
若“访问”时，对无孩子的结点计数，则遍历二叉树的结果就是统计二叉树的叶结点数；若“访问”时，对二叉树的层数计数，则遍历二叉树的结果就是计算二叉树的树深。
由二叉树的定义，一棵二叉树由三部分组成：根、左子树和右子树。
因此，对二叉树的遍历也分成三个子任务： （1）访问根结点； （2）遍历左子树（即依次访问左子树上的全部结点）； （3）遍历右子树（即依次访问右子树上的全部结点）。
由于左子树和右子树也是二叉树，所以对它们的遍历也可继续分解，直到都为空二叉树为止。
可见上述三个子任务的排列次序就决定了二叉树的遍历次序。
若分别以N代表访问根结点、L 代表遍历左子树、R代表遍历右子树，则可以有NLR、LNR、LRN和NRL、RNL、RLN等六种遍历二叉树的次序。
前三种遍历二叉树次序的特点是左先右后，后三种遍历二叉树次序的特点是右先左后。
通常，不是任何遍历次序都被允许的，一般限定正确的遍历次序是“先左后右”，即先遍历左子树，后遍历右子树。
因此，只有NLR、LNR和LRN等三种遍历二叉树的次序。
它们定义如下： 先根遍历：若需遍历的二叉树是空树，则执行空操作；否则，依次执行如下操作： 1）处理根结点； 2）先根遍历左子树； 3）先根遍历右子树。
