笔者对于这部分的总结并不完全，选择了一些基础知识进行总结。（如平衡二叉树，B树，B+树，红黑树等更复杂的知识均未涉及）
查找
查找基本概念
- 在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为静态查找表；反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为动态查找表。
- 平均查找长度：把平均需要和给定值k进行比较的关键字此数称为平均查找长度（ASL）
线性表的查找
用于查找的顺序表用数组表示，该数组元素的类型声明如下：
typedef int KeyType; //关键字类型
typedef struct
{
KeyType key; //关键字项
InfoType data; //其他数据项
} RecType; //查找元素的类型顺序查找
静态查找表用顺序存储结构表示时，顺序查找的查找过程为：从表中的最后一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。
int SeqSearch(RecType R[], int n, KeyType k)
{
int i = 0;
while (i < n && R[i].key != k) //从表头往后找
i++;
if (i >= n) //若没有找到返回0
return 0;
else
return i + 1; //找到就返回i+1
}可以在上述算法中加入一个关键字为k的记录，这样查找时不用再判断i是否越界，提高了查找速度。对应算法如下：
int SeqSearch1(RecType R[], int n, KeyType k)
{
int i = 0;
R[n].key = k; //在R的末尾增加了一个关键字为k的记录
while (R[i].key != k) //从表头往后找
i++;
if (i == n) //若没有找到返回0
return 0;
else
return i + 1; //找到就返回i+1
}Tips
平均查找长度：(n+1)/2
时间复杂度：O(n) (n为查找表中元素的个数)
优点：
- 算法简单
- 对表的结构没有要求，对关键字是否有序没有要求
缺点：
当n较大时查找效率低
折半查找
折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。
int BinSearch(RecType R[], int n, KeyType k)
{
int low = 0, high = n - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (k == R[mid].key) //查找成功直接返回mid+1
return mid + 1;
if (k < R[mid].key) //在R[low..mid-1]中查找
high = mid - 1;
else //在R[mid+1..high]中查找
low = mid + 1;
}
return 0; //查找失败，返回0
}Tips
平均查找长度：log2(n+1)-1
时间复杂度：O(log2n) (n为查找表中元素的个数)
优点：
查找效率高
缺点：
- 要求关键字有序
- 要求存储结构具有随机存取的特征，只适用于顺序表，不适用于链式存储结构。
树表的查找
二叉排序树
二叉排序树要么是空二叉树，要么具有如下特点：
二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
二叉排序树的左右子树也要求都是二叉排序树。
因此二叉排序树的中序序列是一个递增的有序序列。
二叉排序树的结点类型声明如下：
typedef struct node //元素类型
{
KeyType key; //关键字项
InfoType data; //其他数据项
struct node *lchild, *rchild; //左、右孩子指针
} BSTNode;二叉排序树的插入和创建
插入对应算法：
bool InsertBST(BSTNode *&bt, KeyType k)
{
if (bt == NULL) //如果原树为空，新插入的结点为根节点，返回true
{
bt = (BSTNode *)malloc(sizeof(BSTNode));
bt->key = k;
bt->lchild = bt->rchild = NULL;
return true;
}
else if (k == bt->key) //如果存在相同的关键字的结点，返回false
return false;
else if (k < bt->key)
return InsertBST(bt->lchild, k); //插入到左子树中
else
return InsertBST(bt->rchild, k); //插入到右子树中
}创建对应算法：
BSTNode *CreateBST(KeyType a[], int n)
{
BSTNode *bt = NULL; //初始时bt是空树
int i = 0;
while (i < n)
{
InsertBST(bt, a[i]); //调用插入函数将a[i]插入到bt中
i++;
}
return bt; //返回排序二叉树的根指针
}二叉排序树的查找
二叉排序树中查找某关键字时在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：
- 如果相等，查找成功；
- 如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；
- 如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中。查找实现算法如下：
BSTNode *SearchBST(BSTNode *bt, KeyType k)
{
//如果递归过程中bt为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针
if (bt == NULL || k == bt->key)
{
return bt;
}
else if (k < bt->key)
{
//递归遍历其左孩子
return SearchBST(bt->lchild, k);
}
else
{
//递归遍历其右孩子
return SearchBST(bt->rchild, k);
}
}Tips
- n个不同关键字构成的不同的二叉排序树有C(n,2n)/n+1。
- 二叉树排序树中的结点作为内部结点，可以添加相应的外部结点。具有n个结点的二叉排序树，其外部结点的个数为n+1。查找失败一定是落在外部结点上。
- 它的时间复杂度也是O(log2n)
- 二叉树查找效率和二叉排序树的高度有关
- 二叉排序树中插入一个结点所需的关键字比较次数最多是树的高度。
- 向一棵二叉排序树中插入一个结点均是以叶子结点插入的。
对于给定的二叉排序树结点p，找出其左子树中最大结点和右子树中最小结点
void maxminnode(BSTNode *p)
{
if (p != NULL)
{
if (p->lchild != NULL)
printf("左子树的最大结点为：%d\n", maxnode(p->lchild));
if (p->rchild != NULL)
printf("右子树的最小结点为：%d\n", minnode(p->rchild));
}
}
KeyType maxnode(BSTNode *p)
{ //返回二叉排序树最大结点关键字的方法
while (p->rchild != NULL)
{
p = p->rchild;
return (p->data);
}
}
KeyType minnode(BSTNode *p)
{ //返回二叉排序树最小结点关键字的方法
while (p->lchild != NULL)
{
p = p->lchild;
return (p->data);
}
}二叉排序树的删除
假设要删除的为结点 p，则对于二叉排序树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：
1、结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可； 2、结点 p 只有左子树或者只有右子树，如果 p 是其双亲节点的左孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的左子树；反之也是如此，如果 p 是其双亲节点的右孩子，则直接将 p 节点的左子树或右子树作为其双亲节点的右子树； 3、结点 p 左右子树都有，可以从其左子树中选择关键字最大的结点r，用结点r的值代替结点p的值，并删除结点r。
删除排序二叉树bt中关键字为k的结点的算法如下：
bool DeleteBST(BSTNode *&bt, KeyType k)
{
if (bt == NULL) //bt是空树，删除失败
{
return false;
}
else
{
if (k < bt->key)
return DeleteBST(bt->lchild, k); //递归在左子树中删除为k的结点
else if (k > bt->key)
return DeleteBST(bt->rchild, k); //递归在右子树中删除为k的结点
else //如果找到了要删除的结点bt
{
Delete(bt); //调用Delete函数删除结点bt
return true;
}
}
}
void Delete(BSTNode *&p)
{
BSTNode *q;
if (p->rchild == NULL) //结点没有右子树(含为叶子节点的情况)
{
q = p;
p = p->lchild; //用p的左孩子代替它
free(q);
}
else if (p->lchild == NULL) //结点没有左子树
{
q = p;
p = p->lchild; //用p的右孩子代替它
free(q);
}
else
Delete1(p, p->lchild); //p既有左子树又有右子树的情况调用Delete1函数
}
void Delete1(BSTNode *p, BSTNode *&r) //p有左右子树，且r是p的左孩子
{
BSTNode *q;
if (r->rchild != NULL) //递归寻找r的最右下结点
Delete1(p, r->rchild);
else
{
p->key = r->key; //将结点r的值存放到结点p中
p->data = r->data;
q = r; //将r赋给q
r = r->lchild; //用r的左孩子代替r
free(q); //释放结点q的空间
}
}注意：若先删除二叉排序树中的某个结点，再重新插入该结点，不一定得到原来的二叉排序树。
Comments NOTHING