性质2：深度为m的二叉树最多有2m-1个结点。
性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。 性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分。
3. 满二叉树与完全二叉树
满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。
完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现：对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1。
完全二叉树具有以下两个性质：
性质1：具有n个结点的完全二叉树的深度为[log2n]+1。
性质2：设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1，2，……，n给结点进行编号，则对于编号为k（k=1，2，……，n）的结点有以下结论：
① 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT（k/2）； ② 若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）；
③ 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
1.6.2 二叉树的遍历
在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。
（1）前序遍历
先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍需先访问根结点，然后遍历左子树，最后遍历右子树。例如，对图1-1中的二叉树进行前序遍历的结果（或称为该二叉树的前序序列）为：A，B，D，E，C，F。
（2）中序遍历
先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先
遍历左子树，然后访问根结点，最后遍历右子树。例如，对图1-1中的二叉树进行中序遍历的结果（或称为该二叉树的中序序列）为： D，B，E， A，C，F。
（3）后序遍历
先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。例如，对图1-1中的二叉树进行后序遍历的结果（或称为该二叉树的后序序列）为： D， E，B， F，C，A。
1.7 查找
1.7.1 顺序查找
查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等，则表示查找失败。
例如，在一维数组[21，46，24，99，57，77，86]中，查找数据元素99，首先从第1个元素21开始进行比较，比较结果与要查找的数据不相等，接着与第2个元素46进行比较，以此类推，当进行到与第4个元素比较时，它们相等，所以查找成功。如果查找数据元素100，则整个线性表扫描完毕，仍未找到与100相等的元素，表示线性表中没有要查找的元素。
在下列两种情况下也只能采用顺序查找：
①如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找； ②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 1.7.2 二分法查找
二分法查找，也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件。
“有序”是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。下一节排序中，有序的含义也是如此。
对于长度为n的有序线性表，利用二分法查找元素X的过程如下： 步骤1：将X与线性表的中间项比较；
步骤2：如果X的值与中间项的值相等，则查找成功，结束查找；
步骤3：如果X小于中间项的值，则在线性表的前半部分以二分法继续查找； 步骤4：如果X大于中间项的值，则在线性表的后半部分以二分法继续查找。
例如，长度为8的线性表关键码序列为：[6，13，27，30，38，46，47，70]，被查元素为
38，首先将与线性表的中间项比较，即与第4个数据元素30相比较，38大于中间项30的值，则在线性表[38，46，47，70]中继续查找；接着与中间项比较，即与第2个元素46相比较，38小于46，则在线性表[38]中继续查找，最后一次比较相等，查找成功。
顺序查找法每一次比较，只将查找范围减少1，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。
对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。
1.8 排序
1. 交换类排序法 （1）冒泡排序法
首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大小，若前面的元素大于后面的元素，则将它们互换，不断地将两个相邻元素中的大者往后移动，最后最大者到了线性表的最后。
然后，从后到前扫描剩下的线性表，逐次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，不断地将两个相邻元素中的小者往前移动，最后最小者到了线性表的最前面。
对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时已经排好序。 在最坏的情况下，冒泡排序需要比较次数为n(n-1)/2。 （2）快速排序法
任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一次排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。
2. 插入类排序法
① 简单插入排序法，最坏情况需要n(n-1)/2次比较； ② 希尔排序法，最坏情况需要O(n1.5)次比较。 3. 选择类排序法
① 简单选择排序法，最坏情况需要n(n-1)/2次比较； ② 堆排序法，最坏情况需要O(nlog2n)次比较。
相比以上几种（除希尔排序法外），堆排序法的时间复杂度最小。
第2章程序设计基础
2.1 程序设计的方法与风格
养成良好的程序设计风格，主要考虑下述因素： （1）源程序文档化
①符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解； ②程序注释：在源程序中添加正确的注释可帮助人们理解程序。程序注释可分为序言性注释和功能性注释。语句结构清晰第一、效率第二；
③视觉组织：通过在程序中添加一些空格、空行和缩进等，使人们在视觉上对程序的结构一目了然。
（2）数据说明的方法
为使程序中的数据说明易于理解和维护，可采用下列数据说明的风格，见表2-1。
表2-1 数据说明风格数据说明风格
次序应规范化 详细说明 使数据说明次序固定，使数据的属性容易查找，也有利于测试、排错和维护 变量安排有序化 当多个变量出现在同一个说明语句中时，变量名应按字母顺序排序，以便于查找 使用注释 在定义一个复杂的数据结构时，应通过注解来说明该数据结构的特点 （3）语句的结构程序
语句的结构程序应该简单易懂，语句构造应该简单直接。 （4）输入和输出
输入输出比较简单，这里就不作介绍。
2.2 结构化程序设计
1. 结构化程序设计的原则
结构化程序设计方法引入了工程思想和结构化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。
① 自顶向上：先考虑整体，再考虑细节；先考虑全局目标，再考虑局部目标； ② 逐步求精：对复杂问题应设计一些子目标作为过渡，逐步细化；
③ 模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。
限制使用goto语句：在程序开发过程中要限制使用goto语句。 2. 结构化程序的基本结构
结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。
① 顺序结构：是最基本、最普通的结构形式，按照程序中的语句行的先后顺序逐条执行； ② 选择结构：又称为分支结构，它包括简单选择和多分支选择结构；
③ 循环结构：根据给定的条件，判断是否要重复执行某一相同的或类似的程序段。循环结构对应两类循环语句：先判断后执行的循环体称为当型循环结构；先执行循环体后判断的称为直到型循环结构。
2.3 面向对象方法
面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 1. 对象
通常把对象的操作也称为方法或服务。
属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。属性值应该指的是纯粹的数据值，而不能指对象。
操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。
对象具有如下特征：标识惟一性、分类性、多态性、封装性、模块独立性。 2. 类和实例
类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。
类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。 3. 消息
消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。
一个消息由三部分组成：接收消息的对象的名称、消息标识符（消息名）和零个或多个参数。
4. 继承
广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。
继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。