性质6 设完全二叉树共有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；否则该结点无右子结点。
真题讲解：2005年4月填空题第1题，2005年9月填空题第4题，2006年4月选择题第7题。 4、二叉树的存储结构
在计算机中，二叉树通常采用链式存储结构。
与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。
*：一般二叉树通常采用链式存储结构，对于满二叉树与完全二叉树来说，可以按层序进行顺序存储。
11
5、二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：
（1）前序遍历（DLR）：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
（2）中序遍历（LDR）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
（3）后序遍历（LRD）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
真题讲解：2006年4月选择题第6题，2006年9月选择题第10题。 1.7 查找技术
查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找结果：（查找成功：找到；查找不成功：没找到。）
12
平均查找长度：查找过程中关键字和给定值比较的平均次数。 1、顺序查找
基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。 平均要与表中一半以上元素进行比较，最坏情况下需要比较n次。
下列两种情况下只能采用顺序查找：
（1）如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
真题讲解：2006年9月选择题第8题。 2、二分法查找
思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。
前提：必须在具有顺序存储结构的有序表中进行。 查找过程：
（1）若中间项的值等于x，则说明已查到；
（2）若x小于中间项的值，则在线性表的前半部分查找；
13
（3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。
*：二分法查找只适用于顺序存储的线性表，对于无序线性表和线性表的链式存储结构只能用顺序查找。 例：查找元素22的过程：
真题讲解：2005年9月选择题第2题。 1.8 排序技术
14
1717low17low212318422540656mid（a)初始状态212318mid422540high（b)第一次比较后212318422lowmid（c)第二次比较后540high656766879984108811946567668799841088119476687998410881194high排序是指将一个无序序列整理成按值非递减顺序排列的有序序列，即是将无序的记录序列调整为有序记录序列的一种操作。
1、交换类排序法
基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。 方法：冒泡排序，快速排序。 （1）冒泡排序
基本思想：对存放原始数据的数组，按从后往前的方向进行多次扫描，当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好像气泡向上浮起一样。 性能分析：假设线性表的长度n，则在最坏情况下，需要的比较次数为n(n-1)/2。
【49 13 1313131313【38 49 27 2727 27 27【65 38 49 38 383838【97 65 38 49 494949【76 97 65 49494949【13 76 97 65 656565【27 27 76 97 76 767649】初始序列49】第一趟排序后49】第二趟排序后76 97 97】】】第第第三四五趟趟趟排排排序序序后后后97】第六趟排序后13273849496576【97】第七趟排序后
15