9.1 静态查找表
仅作查询和检索操作使用
关键字
数据元素中某个数据项的值，用以标识一个数据元素。若用此关键字可以识别唯一的一个数据元素，则称之为“主关键字”。若用此关键字可以识别若干数据元素，则称之为“次关键字”
9.1.1 顺序表的查找
从顺序表中的最后一个数据元素开始，往前逐个进行比较，下标为0的元素充当哨兵
9.1.2 有序表的查找
可使用折半查找法（二分查找法）查找
基本思想
-
首先将查找关键字与有序表的位于中间位置的数据元素的关键字比较，如果两者相等，则查找成功；否则利用中间位置的数据元素将表分成前、后两个子表。如果查找关键字小于中间位置的数据元素的关键字，则应该去前子表查找（仍然采用折半查找）；否则应该去后子表查找（仍然采用折半查找）
-
重复以上过程，直到找到满足条件的数据元素，即查找成功，或直到子表不存在为止，此时查找不成功
1 int Search_Bin ( SSTable ST, KeyType key )
2 { //在有序表ST中，折半查找 关键字 = key的数据元素。
3 //若找到，则函数值为该元素在表中的位置，否则为返回0。
4 low = 1; high = ST.length; //确定查找区间
5 while (low <= high)
6 { mid = (low + high) / 2; //计算中间位置
7 if （ EQ (key , ST.elem[mid].key) )
8 return mid; //找到了待查元素的位置
9 else if ( LT (key , ST.elem[mid].key) )
10 high = mid - 1; //确定在前半区间查找
11 else low = mid + 1; //确定在后半区间查找
12 }
13 return 0; //不存在待查元素
14 }
折半查找法的时间复杂度分析
复杂度为： O(log_2n)
O(1)<O(log_2n)<O(n)<O(n^2)<O(2^n)<O(n!)
9.1.3 静态树表的查找
静态最优查找树：若只考虑查找成功的情况，则查找性能达到最佳的判定树是其所有结点的带权路径长度之和（PH 值）值最小的二叉树
$$PH = \sum_{i=1}^{n}w_ih_i
$$
其中：n 为二叉判定树上的结点个数（= 有序表的长度） h_i 为第 i 个结点在二叉判定树上的层次。 w_i = cp_i (i = 1, 2, …, n)，称w_i 为结点的“权”。 p_i 为结点被查找的概率， c 为某个常量
静态次优查找树的构造方法：近似最优查找树
算法思想
-
首先从序列 (r_l , r_{l+1}, …, r_h) 中选取第 i个(l ≤ i ≤ h) 记录r_i构造根结点： 要求这个作为次优查找树的“根结点” 的第 i (l ≤ i ≤ h) 个记录r_i的\bigtriangleup P_i取最小值。
-
然后分别对子序列 (r_l , r_{l+1}, …, r_{i-1}) 和子序列 (r_{i+1} ,r_{i+2}, …, r_h) 构造两棵次优查找树，并分别设为根结点r_i的左子树和右子树
1 void SecondOpt(BiTree &T, ElemType R[], float sw[], int low, int high)
2 {
3 //由有序表R[low..high]及累计权值表sw(其中sw[0]==0)先序递归构造次优查找树T
4 i=low；min=abs(sw[high]-sw[low]-0-0)；//设初始最小值 min =
5 dw =sw[high] + sw[low-1]；
6 for( j=low+1；j<=high；++j )
7 if (abs(dw-sw[j]-sw[j-1])<min ){ i=j; min = abs(dw-sw[j]-sw[j-1]) }；
8 T=(BiTree)malloc(sizeof(BiTNode)) ；
9 T->data = R[i]； //生成结点
10 if(i==low) T->lchild = NULL； //左子树空
11 else SecondOpt(T->lchild , R, sw, low, i-1 ); //构造左子树
12 if (i==high) T->rchild = NULL； //右子树空
13 else SecondOpt(T->rchild , R, sw, i+1, high); //构造右子树
14 }
9.2 动态查找表
在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者从查找表中删除其“查询”结果为“ 在查找表中”的数据元素
9.2.1 二叉排序树
定义
-
若它的左子树不空，则左子树上所有结点的值均小于根结点的值
-
若它的右子树不空，则右子树上所有结点的值均大于根结点的值
-
它的左、右子树也都分别是二叉排序树
存储结构
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, * BiTree;
查找算法
(a)
1 BiTree SearchBST( BiTree T, KeyType key )
2 { if ( ( !T ) || EQ(key , T->data.key) ) return (T); //查找结束
3 else if LT(key, T->data.key)
4 return ( SearchBST( T->lchild, key ) );
5 else return ( SearchBST( T->rchild, key ) );
6 }
(b)
1 status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p )
2 {/* 在指针T所指二叉排序树中递归查找关键字等于key的结点， 若查找成功，则指针p指向该结点，并返回TRUE，
3 若不成功, 则指针p指向查找的最后一个结点，并返回FALSE。
4 指针f用于指向T的双亲，其初始调用值为NULL */
5
6 if (!T) { p=f; return FALSE; } //未查到，则指针p指向 T 的双亲，以用于插入结点
7 else if EQ( key, T->data.key ) { p=T; return TRUE;}
8 else if LT( key, T->data.key )
9 return SearchBST( T->lchild, key, T, p ); //在左子树中查找
10 else return SearchBST(T->rchild, key, T, p ); //在右子树中查找
11 }
插入算法
1 Status InsertBST( BiTree &T, ElemType e )
2 { /* 当二叉排序树T中不存在关键字等于e.key的数据元素时，
3 插入e并返回TRUE，否则返回FALSE。 */
4 BiTree p, s;
5 if (! SearchBST(T, e.key, NULL, p ) ) //查找不成功才插入
6 { s=( BiTree ) malloc( sizeof( BiTNode ) );
7 s->data=e; s->lchild=s->rchild=NULL;
8 if (!p) T= s; //p==NULL , 被插结点 为空树T的根结点
9 else if LT(e.key, p->data.key ) p->lchild=s; //被插结点为p的左孩子
10 else p->rchild=s; //被插结点为p的右孩子
11 return TRUE;
12 }
13 else return FALSE; //树中已经有关键字相同的结点，不用插入 。
14 }
删除算法
(1) 被删除的结点是叶子结点
算法思想：直接删除叶子结点，并将被删除的叶子结点的双亲结点的相应的指针域的值修改为NULL
(2) 被删除的结点只有左子树，或者只有右子树
算法思想：将被删除的结点的双亲结点的相应指针域的值修改为“指向被删除结点的左子树或右子树”
(3) 被删除的结点既有左子树，也有右子树
算法思想：先将被删结点的值以其前驱结点的值替代，然后再删除其前驱结点
标签：结点,BiTree,右子,关键字,算法,查找,key From： https://www.cnblogs.com/eecsCodeStar/p/16981397.html