数据结构小记7查找2

1. 上一篇的折半查找法有递归版本：

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. （1）二叉树左子树不空，那么左子树上所有结点的值小于根结点的值
   

   （2）二叉树右子树不空，那么右子树上所有结点的值大于根结点的值

   （3）左右子树也分别为二叉排序树

2. 二叉排序树的查找算法：

   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;//查找结束

 else if(key<T->data.key) return SearchBST(T->lchild,key);//在左子树中继续查找

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）左子树和右子树也是平衡二叉树。

平衡树调整方法：LL型，RR型，RL型，LR型

散列函数：最常用的构造方法是除留取余法

处理冲突的方法为：开放地址法和链地址法（下一期会细讲）