十八.二叉树的遍历

就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。一般先左后右。

1.前序遍历DLR 首先访问根结点，然后遍历左子树，最后遍历右子树。

2.中序遍历LDR 首先遍历左子树，然后根结点，最后右子树

3.后序遍历LRD 首先遍历左子树，然后遍历右子树，最后访问根结点。

十九.顺序查找与二分查找

1.顺序查找 在两种情况下只能用顺序查找：线性表为无序表、链式存储结构的有序表

2.二分查找 只适用于顺序存储的有序表（从小到大）。

对于长度为N的有序线性表，在最坏情况下，二分查找只需要比较log2N次，而顺序查找要比较N次。 排序：指将一个无序序列整理成按值非递减顺序排列的有序序列。

二十.交换类排序法

冒泡排序与快速排序法属于交换类的排序方法

1.冒泡排序法 假设线性表的长度为N，则在最坏的情况下，冒跑排序需要经过N/2遍的从前往后的扫描和N/2遍的从后往前的扫描，需要的比较次数为N（N-1）/2

2.快速排序法

二十一.选择类排序法 1.简单选择排序法 2.堆排序法

二十三.插入类排序法 1.简单插入排序法2.希尔排序法

           最坏情况下      最好情况下      说明
交换排序      冒泡排序      n(n-1)/2            最简单的交换排序。在待排序的元素序列基本有序的前提下，效率最高
     快速排序      n(n-1)/2      O(Nlog2 N)     

插入排序      简单插入排序      n(n-1)/2            每个元素距其最终位置不远时适用
     希尔排序      O(n1.5)           

选择排序      简单选择排序      n(n-1)/2           
     堆排序      O(nlog2n)            适用于较大规模的线性表