1.6.2二叉树及其基本性质
1、二叉树，是一种很有用的非线性结构。二叉树有以下两个特点： （1）非空二叉树只有一个根结点 ；
（2）每一个结点最多有两颗子树，每一个结点的度最大为2。 2、二叉树的基本性质：
（1）在二叉树的第k层上，最多有2的k-1次方（k>=1)个点； （2）深度为m的二叉树最多有2指二叉树共有m层）；
（3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个；
（4）具有n个结点的二叉树，其深度至少为【log2N】+1，其中【log2N】表示取其整数部分。
3、满二叉树与完全二叉树
（1）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
（2）完全二叉树：除最后一层外，每一层上的结点树均达到最大值，在最后一层上只缺少 右边的若干结点。
m?1个结点（深度为m的二叉树是
6
4、完全二叉树的性质：
（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.3二叉树的存储结构
1、计算机中二叉树通常采用链式存储结构。
1.6.4二叉树的遍历
1、二叉树的遍历：是指不重复地访问二叉树中的所有结点。
（1）前序遍历（DLR） 先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左右子树时，仍先访问根结点，然后遍历左子树，最后遍历右子树。 （F C A D B E G H P）
（2）中序遍历（LDR）首先遍历左子树，然后访问根结点，最后遍历右子树；在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 （A C B D F E H G P）
（3）后序遍历 （LRD）首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。 （A B D C H P G E F）
1.7查找技术
1、顺序查找的基本方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等，则表示找到（即查找成功）；若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。
2、二分法查找只适用于顺序存储的有序表。设有序线性表的长度为n，被查元素为x，则对分查找的方法为：将x与线性表的中间项进行比较，若中间项的值等于x，则说明找到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。
3、对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较log2N次，而顺序查找需要比较n次 。
7
1.8排序技术
1、交换类排序法：冒泡排序法、快速排序法。 2、插入类排序法：简单插入排序法、希尔排序法。 3、选择类排序法：简单选择排序法、堆排序法 。
8