森林转化为二叉树：
将每棵树分别转换成二叉树 将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
二叉树转化为森林： 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树
堆排序
查找表的基本操作
1）查询某个数据元素是否在查找表中； 2）检索某个数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。
查找表的分类 静态查找：
仅作查询和检索操作的查找表 动态查找表
进行了插入和删除
顺序表的查找 顺序查找
一个一个查找，找到则查找成功，没找到则查找失败
空间复杂度：需要一个辅助存储单元空间R[0] ，因此，顺序查找的空间复杂度为O(1)
时间复杂度：查找算法的基本运算是给定值与顺序表中记录关键字值的比较。 最好情况：第一次比较就成功找到所需数据，这时，时间复杂度为O(1)。
最坏情况：所查找的记录不在顺序表中，这时，需要和整个顺序表的记录进行比较，比较的次数为n，时间复杂度为O(n)。 平均情况：需要和顺序表中大约一半的记录进行比较，即比较次数为n/2，因而，时间复杂度为O(n)。
优点：算法简单，适用面广 缺点：平均查找长度较大。
折半查找
查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现
设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若k
重复上述操作，直至low>high时，查找失败 折半查找算法：
int BinarySearch(DataType SL[], KeyType key, int n){
//在长度为n的有序表SL中折半查找其关键字等于key的数据元素 //查找成功返回其在有序表中的位置，查找失败否返回0 int low=1; int high=n; while(low<=high){ mid=(low+high)/2; if(key = = SL[mid].key) {return mid;} else if( key>SL[mid].key) low=mid+1; else high=mid-1; } return 0; }
? 算法评价
? 判定树：描述查找过程的二叉树叫~ ? 有n个结点的判定树的深度为?log2n?+1
? 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 ? 折半查找的ASL
? 折半查找特点
? 折半查找的查找效率高；
? 平均查找性能和最坏性能相当接近； ? 折半查找要求查找表为有序表；
? 并且，折半查找只适用于顺序存储结构。
哈希表查找
? 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对
应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 ? 定义
? 哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~
– 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象
– 哈希函数可写成：addr(ai)=H(ki)
? ai是表中的一个元素 ? addr(ai)是ai的存储地址 ? ki是ai的关键字
? 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~
? 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~
? 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可
? 冲突：key1?key2，但H(key1)=H(key2)的现象叫~ ? 同义词：具有相同函数值的两个关键字，叫该哈希函数的~
? 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法
? 哈希函数的构造方法
? 直接哈希函数法
– 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b
? 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 ? 实际中能用这种哈希函数的情况很少
? 数字分析法
– 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址
– 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况
平方取中法
取关键字平方后的中间几位作为哈希地址，即哈希函数为： H（key）=“key2的中间几位”，
其中，所取的位数由哈希表的大小确定
折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类
移位叠加：将分割后的几部分低位对齐相加
间界叠加：从一端沿分割界来回折送，然后对齐相加
适于关键字位数很多，且每一位上数字分布大致均匀情况
? 除留余数法
? 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数
作哈希地址，即H(key)=key MOD p，p?m