數(shù)據(jù)結(jié)構(gòu)小記7查找2
上一篇的折半查找法有遞歸版本：
int BinarySearch(SSTable ST,int low,int high,KeyType key)
{low=1;high=ST.length;
mid=(low+high)/2;
if(ST.R[mid]==key) return mid;//找到
else if(key<ST.R[mid])
? return BinarySearch(ST.R,?low,mid-1,key);
else
??return BinarySearch(ST.R, mid+1,high,key);
}
二叉排序樹
（1）二叉樹左子樹不空，那么左子樹上所有結(jié)點的值小于根結(jié)點的值
（2）二叉樹右子樹不空，那么右子樹上所有結(jié)點的值大于根結(jié)點的值
（3）左右子樹也分別為二叉排序樹
二叉排序樹的查找算法：
ElemType與上一期的一樣故不再贅述
typedef struct BSTNode
{Elem data;
?struct? BSTNode *lchild,*rchild;//左右孩子指針
}BSTNode,*BSTree;
【算法描述】
遞歸算法：
BSTree SearchBST(BSTree T,KeyType)
{if((!T)||key==T->data.key)? return T;//查找結(jié)束
?else if(key<T->data.key) return SearchBST(T->lchild,key);//在左子樹中繼續(xù)查找
else??return SearchBST(T->rchild,key);
}
非遞歸算法：
BSTree SearchBST(BSTree T,KeyType)
{b=T;
while(p){
if(p->data.key==key) return p;
else if(key<p->data.key)
p=p->lchild;
else
p=p->rchild;
}
return NULL;//查找失敗
}
平衡二叉樹
（1）左子樹和右子樹的深度之差（即平衡因子）的絕對值不超過1
（2）左子樹和右子樹也是平衡二叉樹。
平衡樹調(diào)整方法：LL型，RR型，RL型，LR型
散列函數(shù)：最常用的構(gòu)造方法是除留取余法
處理沖突的方法為：開放地址法和鏈地址法（下一期會細(xì)講）
