第一章数据结构与算法
第二章程序设计基础
第三章软件工程基础
第四章数据库设计基础
第一章数据结构与算法
1.2数据结构的1.1算法
基本概念
1.3线性表及其顺序存储结构
1.4栈和队列
1.5线性链表
1.6树与二叉树
1.7查找技术
1.8排序技术
考试大纲
1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。
2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。
4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
5.线性单链表、双向链表与循环链表的结构及其基本运算。
6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。

1.1算法
1.1.1 算法的基本概念
算法：是指解题方案的准确而完整的描述。       算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。1、算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
1.1算法
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
1.1算法
2、算法的基本要素：
一是对数据对象的运算和操作；
二是算法的控制结构。
（1）算法中对数据的运算和操作
指令系统：一个计算机系统能执行的所有指令的集合。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
1.1算法
（2）算法的控制结构：
一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
1.1算法
3、算法设计基本方法
（1）列举法：根据提出的问题，列举所有可能的情况，并用问题 中给定的条件检验哪 些 是需要的，哪 些是不需要的。
（2）归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。
（3）递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
（4）递归：将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决当最后那些最简单的总是后，再沿着原来分解的逆过程逐步进行综合，
（5）减半递推技术：所谓“减半”，是指将问题材的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。
（6）回溯法：通过对问题的分析，找出一个解决总是的线索，然后沿着这个线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。
1.1算法
1.1.2算法的复杂度算法复杂度：算法时间复杂和算法空间复杂度。1.算法的时间复杂度
算法时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
        算法的工作量=f(n)
1.1算法
(1)平均性态： 是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
算法的平均性态定义：

(2)最坏情况复杂性：是指在规模为n时，算法所执行的基本运算的最大次数。

1.1算法
2.算法空间复杂度
算法空间复杂度是指执行这个算法所需要的内存空间。
 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

1.2数据结构的基本概念
数据结构研究的三个方面：（1）数据集合中和数元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
讨论以上问题的主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。

1.2.1什么是数据结构
数据结构是指相互有关联的数据元素的集合。
1、数据的逻辑结构
数据的逻辑结构包含：
（1）表示数据元素的信息；
（2）表示各数据元素之间的前后件关系。

2、数据的存储结构
        数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。
        数据的存储结构有顺序、链接、索引等。

1.2.2数据结构的图形表示
例如：一年四季的数据结构可以用图形来表示。

用图形表示数据结构B=（D，R），其中
    D={di|1<=i<7}={d1，d2，d3，d4，d5，d6，d7}
    R={（ d1 ， d3 ），（ d1 ， d7 ），（ d2 ， d4 ），（ d3 ， d6 ），（ d4 ， d5 ）}

应用举例——制定教学计划
       在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：

 

1.2.3 线性结构与非线性结构
 线性结构条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构
1.3.1 线性表的基本概念线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

　　　　　　　学生情登记表　　　　　　　

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
非空线性表的结构特征：
（1）且只有一个根结点a1，它无前件；
（2）有且只有一个终端结点an，它无后件；
（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。

1.3.2 线性表的顺序存储结构
线性表的顺序存储结构具有以下两个基本特点：
（1）线性表中所有元素的所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。

一般来说，长度为n的线性表
（a1，a2，…，ai，…,an）

1、在线性表的指定位置处加入一个新的元素（即线性表的插入）
2、在线性表中删除指定的元素（即线性表的删除）
3、在线性表中查找某个 （或某些）特定的元素（即线性表的查找）
4、对线性表中的整序（即线性的排序）；
5、按要求将一个线性表分解成多个线性表（即线性表的分解）
6、按要求将多个线性表合并成一个线性表（即线性表的合并）
7、复制一个线性表（即线性表的复制）
8、逆转一个线性表（即线性表的逆转）

1.3.3 顺序表的插入运算

例：下图为一个长度为８的线性表顺序存储在长度为１０的存储空间中。现在要求在第二个元素之前插入一个新元素87。在插入14。

在线性表L中第i个数据元素之前插入数据元素e
步骤：
    1、检查插入要求的有关参数的合理性
    2、把原来第n个数据元素至第I个元素
          （共n-i+1)依次后移一个叔祖元素的位置。
    3、把新数据元素放在第I个位置上
    4、修正线性表的数据元素个数。

现在分析插入算法的复杂度。
   
      这里的问题规模是表的长度，设它的值为n。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1 。由此可看出，所需移动结点的次数不仅依赖于表的长度n，而且还与插入位置i有关。
    当n=i时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；
    O（n）。
     当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为

            由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度
             在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。 pi 是在第i 个元素之前插入一个元素的概率，
          故  Eis(n)=  pi(n-i+1)
           不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则
           p1=p2=p3=…=p n+1=1/(n+1)
     因此，在等概率插入的情况下，  
               Eis(n)=  ( n -i+1)/(n+1)

 

线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：

 

也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。

1.3.4 顺序表的删除运算

算法思想：删除第i个元素时，需要将n至i+1个（共n-I）个元素向前移动一个位置。步骤：
 1、检查删除要求的有关参数的合理性
 2、把原来的第I+1个数据元素至第n个（共n-I）个元素依次向前移动一个位置
 3、修正线性表的数据元素个数。

 

删除算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i  决定。
若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；
若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。
删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故
               Ede(n)=   pi(n-i)
     式中， pi表示删除表中第i个结点的概率。在等概率的假设下，
           p1=p2=p3=…=pn=1/n

 

在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：

 

    分析结论
 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。平均时间复杂度也是O(n)。
当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。
算法复杂性分析
顺序表的基础要点
1、线性表是具有n个数据元素的有限序列。
2、线性表的顺序存储结构具有三个弱点：
①在插入和删除时，需移动大量元素
②由于难以估计，必须预先分配较大的空间
③表的容量难以扩充 (如何解决？）
3、顺序存储结构通过元素的相对存储地址来表示元素之间的关系
4、线性表顺序存储的优点是可随机存取元素。
5、顺序表中逻辑上相邻的元素的物理位置必定紧邻。
6、顺序表是一种随机存取的存储结构。
7、在顺序表中插入或删除一个元素时，需要平均移动表的一半元素，具有移动的元素个数与该元素的位置有关。
8、在长度为n的顺序表中插入一个元素的时间复杂度为O(n)，删除一个元素的时间复杂度为O(n)。

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示：
 
            进行插入和删除的表尾端是浮动端，通常被称为栈顶， an   为栈顶元素， 并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底， a1  为栈底元素，。我们经常将栈用下图的形式描述：

 

栈的基本运算：
（1）插入元素称为入栈运算；
（2）删除元素称为退栈运算；
（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化

                                                            

 

 

 

                              栈顶指针和栈中元素之间的关系

1.4.2 队列及其基本运算
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。
　　  例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。
　　  当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。

下图是队列的示意图：
　　　　　
　　　　　　 a1　a2　…　an
　　
　　　　　

               插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。
            结论：先进先出（First In First Out），简称为FIFO线性表。

队列的顺序存储结构
实现：用一维数组实现sq[M]

存在问题
设数组维数为M，则：
当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出
当front-1,rear=M-1时，再有元素入队发生溢出——假溢出
解决方案
队首固定，每次出队剩余元素向下移动——浪费时间
循环队列
基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;

队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。
队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。
队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。
循环队列：s=0表示队列空，s=1且front=rear表示队列满
1.5 线性链表
1.5.1 线性链表的基本概念
线性表顺序存储结构的特点
它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。
暴露的问题
在做插入或删除元素的操作时，会产生大量的数据元素移动；
对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；
线性表的容量难以扩充。

    线性表的链式存储结构
            线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：
    

例如 ：线性表 （a, b,c,d)

          

术语
表示每个数据元素的两部分信息组合在一起被称为结点；
其中表示数据元素内容的部分被称为数据域（data）；
表示直接后继元素存储地址的部分被称为指针或指针域（next）。
           

其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（^）符号表示。
带头结点的单链表
为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示：

 

链式存储结构的特点
（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；
（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。

循环链表(circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表构成环状
特点：从表中任一结点出发均可找到表中其他结点，提高查找效率
操作与单链表基本一致,循环条件不同
单链表p或p->link=NULL
循环链表p或p->link=H

双向链表（double linked list）
单链表具有单向性的缺点

数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式即可用于表示线性结构，也可用于表示非线性结构。

栈的链式存储
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。
由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。

 

十进制数值转换成二进制
             使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。
            比如：(692)10 = (1010110100)2，其展转相除的过程

链队列
      队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一确定。添加头节点。和顺序队列类似，我们也是将这两个指针封装在一起，

1.5.2 线性链表的基本运算
1、在线性链表中查找指定元素
　　　在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，要线性链表中指定值的前一个结点。

单链表的基本运算
查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL

1．6 树与二叉树
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。
 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。

 

结点：  数据元素的内容及其指向其子树根的分支统称为结点。
结点的度 （Degree): 结点的分支数，即结点拥有的子树数。
终端结点（叶子leaf）:  度为0的结点。
非终端结点:  度不为0的结点。
结点的层次:  树中根结点的层次为1，根结点子树的根为第2  层，以此类推。
树的度:  树中所有结点度的最大值。
树的深度:  树中所有结点层次的最大值。
有序树、无序树:  如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。
1.6.2二叉数及其基本性质
1. 定义
             定义：二叉树是另一种树形结构。它与树形结构的区别是：
           （1）每个结点最多有两棵子树；
           （2）子树有左右之分。
             二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。

 

 二叉树的特点：
（1）非空二叉树只有一个根结点；
（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

二叉树的5种形态：

    2．二叉树的性质
二叉树具有下列5个重要的性质。
【性质1】 在二叉树的第i层上最多有2i-1个结点（i≥1）。
 二叉树的第1层只有一个根结点，所以，i=1时，
       2i-1=21-1=20=1成立。
假设对所有的j，1≤j<i成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。

【性质2】 深度为K的二叉树最多有2K-1个结点(K≥1）。
由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,...,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：

其中 a1为第一项，an为第k项，q为比值。可以得到，该数列前K项之和为：

【性质3】 对于任意一棵二叉树BT，如果度为0的结点（叶子）个数为n0，度为2的结点个数为n2，则n0=n2+1。
证明：
1. 假设度为1的结点个数为n1，结点总数为n。 因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：
n=n0+n1+n2      （1）
2. 设B为二叉树中的分支数
从入支的角度看，即前驱结点的角度看，二叉树中，除根结点之外，其余每个结点都有一个且只有一个前驱结点，即有一个从上向下的分支指向(即占有一个分支)，所以，总的结点个数n与分支数B之间的关系为：
                                          n=B+1。         （2）

 从出支的角度看，即后继结点的角度看，因为在二叉树中，度为0的结点没有后继结点，即不占分支，度为1的结点有一个后继结点，产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：
                    B=n1+2n2。       （3）
将此式代入上式，得：
n=n1+2n2+1     （4）
用（1）式减去（4）式，并经过调整后得到：n0=n2+1。
      满二叉树：
如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。

完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。

完全二叉树的特点：
    （1）叶子结点只可能在层次最大的两层上出现
   （2）对任意结点，若其右分支下的子孙的最大层次是l ，则其左分支下的子孙的最大层次必是l 或l+1

 

【性质4】 具有n个结点的完全二叉树的深度为  log2n+1。其中，log2n 的结果是不大于log2n的最大整数。
证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：
                    2K-1-1<n≤2K-1
将不等式两端加1得到：
                    2K-1≤n<2K
将不等式中的三项同取以2为底的对数，并经过化简后得到：
                    K-1≤log2n<K
            由此可以得到：log2n =K-1。
          整理后得到：K= log2n+1。

【性质5】 对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1≤i≤n），都有：
（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；如果i > 1其双亲结点的编号为 i/2。
（2）如果2i>n，则结点i没有左孩子（结点i为叶子结点）；否则其左孩子结点的编号为2i。
（3）如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。
      
      

证明：下面我们利用数学归纳法证明这个性质。我们首先证明（2）和（3）。
当i=1时，其左孩子结点编号应该是２，其右孩子结点编号应该是3 。若n<2，则根将没有左、右孩子；若n≥3，则根的左、右孩子的编号分别是2，3；若n<3，则根没有右孩子；以上对于（2）和（3）均成立。
假设：对于所有的1≤j≤i 结论成立。即：结点j的左孩子编号为2j；右孩子编号为2j+1。

 

            由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。
            可以看出，i+1的左、右孩子紧邻在结点i　的孩子后面，由于结点i 的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。
            又因为二叉树由n个结点组成，所以，当2(i+1)+1>n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)>n，结点i+1既没有左孩子也没有右孩子。

           以上证明得到（2）和（3）成立。
            下面利用上面的结论证明（1）。
            对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而 2i/2=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而 (2i+1)/2 =i，由此可以得出（1）成立。
二叉树的基本性质：
（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；
（2）深度为m的二叉树最多有2m-1个结点；
（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；
（5）具有n个结点的完全二叉树的深度为[log2n]+1；

满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。

 （6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：
 ①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)；
 ②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；
 ③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。

1.6.3二叉树的存储结构
            二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。
1. 顺序存储结构
            这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元依次自上而下、自左至右存储完全二叉树的结点元素，即 ：按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。

 

 

 

 

 

 

 

最坏情况下，一个深度为k且只有k个结点的单支树，需要长度为2k-1的一维数组。

 

这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。

1.6.4二叉的遍历
             二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。
            二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。

1.  按根、左子树和右子树三部分进行遍历
           遍历二叉树的顺序存在下面6种可能：
            TLR（根左右）,  TRL（根右左） 
            LTR（左根右）,  RTL（右根左）
            LRT（左右根）,  RLT（右左根）
            其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。

（1）先序遍历
若二叉树为空，则结束遍历操作；否则
访问根结点；
先序遍历左子树；
先序遍历右子树。
（2）中序遍历
若二叉树为空，则结束遍历操作；否则
中序遍历左子树；
访问根结点；
中序遍历右子树。

（3）后序遍历
若二叉树为空，则结束遍历操作；否则
后序遍历左子树；
后序遍历右子树；
访问根结点。
下面是一棵二叉树及其经过三种遍历得到的相应序列。

            下面我们再给出两种遍历二叉树的方法：
          （1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。

 

          （2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。
1．7 查找技术
 1.7.1顺序查找
顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。
顺序查找的使用情况：
（1）线性表为无序表；
（2）表采用链式存储结构。

1.7.2二公法查找
二分法查找只适用于顺序存储的有序表。
对于长度为n的有序线性表，最坏情况只需比较log2n次。

假设查找表存放在数组a的a[1]~a[n]中，且升序，查找关键字值为k。
           折半查找的主要步骤为：
          （1）置初始查找范围：low=1，high=n;
          （2）求查找范围中间项：mid=(low+high)/2
          （3）将指定的关键字值k与中间项a[mid].key比较
          若相等，查找成功，找到的数据元素为此时mid 指向的位置；

若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1;
  若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1;
（4）重复步骤（2）、（3）直到查找成功或查找范围空（low>high），即查找失败为止。
（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。

1.8排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
1.8.1交换排序
所谓交换类排序法是指借助数据元素之间的互相交换进行的排序的一种方法。

1.冒泡排序
冒泡排序是一种最简单的交换类排序方法,它是通过相邻数据元素的交换逐步将线性表变成有序。
冒泡排序法，需要比较的次数为n(n-1)/2；
２.块速排序

１.8.2插入排序
１．简单插入排序法
最坏情况需要n(n-1)/2次比较；
２.希尔排序法
最坏情况需要O(n1.5)次比较。

１.８.３选择类排序法
（1）简单选择排序法最坏情况需要n(n-1)/2次比较；
（2）堆排序法
最坏情况需要O(nlog2n)次比较。