动态查找表包括二叉排序树和二叉平衡树。
二叉排序树：也叫二叉搜索树，它或是一颗空树，或是具有以下性质的二叉树：
①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
③它的左右子树也是二叉排序树。
由此可得，对二叉排序树进行中序遍历可以得到一个递增的有序数列。
二叉排序树的查找：将关键字与根结点相比较
typedef struct BiTNode{ //二叉排序树结点结构
int data; //结点数据
struct BiTNode *lchild,*rchild; //指向该结点左右孩子的指针
}BiTNode,*BiTree;
//递归代码
BiTNode *BST_Search(BiTNode *t,ElemType key){
if(t==NULL) return NULL;
else{
if(t->data==key) return t;
else if(key<t->data) return BST_Search(t->lchild,key);
else return BST_Search(t->rchild,key);
}
}
//非递归代码
BiTNode *BST_Search(BiTNode *t,ElemType key){
BiTNode *p=t;
while(p!=NULL&&key!=p->data){
if(key<p->data) p=p->lchild;
else p=p->rchild;
}
return p;
}
二叉排序树的插入思想：
①若树空，直接插入新结点，返回成功。
②树不空，若存在该关键字则插入失败，若不存在该关键字，检查根结点的值和大小关系，递归插入。
int BST_Insert(BiTNode* &t,ElemType key){
if(t==NULL){
t=(BiTNode*)malloc(sizeof(BiTNode));
t->data=key;
t->lchild=t->rchild=NULL;
return ;
}
else if(key==t->data) return ;
else if(key<t->data) return BST_Insert(t->lchild,key);
else return BST_Insert(t->rchild,key);
}
构造二叉排序树：从一颗空树开始，依次插入二叉排序树中的结点。
void BST_Creat(BiTNode* &t,ElemType key[],int n){ //n为关键字数量
t=NULL;
int i=;
while(i<n){
BST_Insert(t,key[i]);
i++;
}
}
二叉排序树删除结点：有以下几种可能
①删除的是叶子结点：直接删除；
②删除的是仅有一个左子树或右子树的结点：子承父业，让那个叶子结点代替根结点；
③删除的是左右子树都有的结点：找到待删除结点的直接前驱或者直接后继结点，用该结点来替换待删除结点。
二叉平衡树：是特殊的二叉排序树，其左右子树高度之差的绝对值不超过1，而且左右子树又是一颗平衡二叉树。