完全二叉树还具有以下两个性质：了解，不讲了 ①具有n个结点的完全二叉树深度为?log2n?+1。
②如果对一棵有n个结点的完全二叉树的结点按层编号，则对于编号为k(1≦k≦n)的结点有以下结论。
? 如果k=1，则结点k没有父结点，是二叉树的根；如果k>1，则该结点的父结点编号为INT(k/2)。 ? 如果k≦n，则结点k左子结点编号为2k；否则该结点没有左子结点（显然也没有右子结点）。
? 如果2i+1≦n，则结点k左子结点编号为2k+1；否则该结点没有右子结点。
考点17 二叉树的存储结构 了解
在计算机中，二叉树通常采用链式存储结构。
用于存储二叉树中各元素的存储结点也由两部分组成：
数据域和指针域。
由于每一个元素可以有两个后件（即两个子结点），因此用
于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指抽该结点的右子结点的存储地址，称为右指针域。如下图所示。
其中，L( i )为结点i的左指针域，即L( i )为结点i的左子结点的存储地址；R( i )为结点i的右指针域，即R( i )为结点i的右子结点的存储地址，V( i )为数据域。
由于二叉树的存储结构中每一个存储结点有两个指针，因此二叉树的链式存储结构也称为二叉链表。
对于满二叉树与完全二叉树来说，根据完全二叉树的性质②，可以按层序进行顺序存储，这样不仅可以节省存储空间，也可以方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储对于一般的二叉树不适用。
*考点18 二叉树的遍历 重点
二叉树的遍历是指不重复地访问二叉树中的所有结点。
由于二叉树是一种非线性结构，因此对二叉树的遍历要比遍历线性表复杂得多。
在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问要结点的次序，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。
1、前序遍历（DLR）
所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后访问右子树。
若二叉树为空，则结束返回，否则： a.访问根结点。
b.前序遍历左子树。
c.前序遍历右子树。 一句话：根左右
2、中序遍历（LDR）
所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后访问右子树。
若二叉树为空，则结束返回，否则： a.中序遍历左子树。 b.访问根结点。 c.中序遍历右子树。 一句话：左根右
3、后序遍历（LRD）
所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点；并且遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
若二叉树为空，则结束返回，否则： a.后序遍历左子树。 b.后序遍历右子树。 c.访问根结点。 一句话：左右根
重要的例子：
例1：对下图二叉树进行前序遍历，结果为：FCADBEGHP 中序遍历，其结果为：ACBDFEHGP 称为该二叉树的中序序列。 后序遍历，其结果为：ABDCHPGEF 称为该二叉树的后序序列。
例2：已知一棵二叉树的前序遍历结果为：FCADBEGHP，中序遍历结果为：ACBDFEHGP，画出这棵二叉树，并写出后序遍历结果。
解：根据前序和中序遍历结果，构造出这棵二叉树如上图所示，则后序遍历结果为：ABDCHPGEF
七、查找技术
*考点19 顺序查找 重点
顺序查找又称顺序搜索。它一般是指在线性表中查找指定的元素，其基本方法如下：
从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等，则表示找到（即查找成功）；若线性表中所有的元素都与被查元素不相等，则表示线性表中没有要找的元素（即查找失败）。
在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。
在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。
由此可以看出，对于大的线性表来说，顺序查找的效率很低。虽然顺序查找的效率不高，但在下列两种情况下，也只能采用顺序查找：
? 如果线性表是无序的（却表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能顺序查找。 ? 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
*考点20 二分查找 重点
二分查找只适用于顺序存储的有序表。
在此所说的有序表是指线性表中的元素按值非递减排列，即从小到大，但允许相邻元素值相等。
设有序线性表的长度为n，被查元素为x，则二分查找的方法如下：
①将x与线性表的中间项进行比较。
②若中间项的值等于x，则说明查到，查找结束。
③若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找。
④若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。
此过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
显然，当有序线性表为顺序存储时才可能采用二分法查找，并且二分法查找的效率要比顺序查找高得多。
重点：
对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较
logn
2
次，而顺序查找则需要比较n次。
八、排序技术
排序也是数据处理的重要内容。
排序是指将一个无序序列整理成按值非递减顺序排列的有