1.概念
1.1二叉树的定义
与其他数据结构一样，二叉搜索树也是由一组数据项所构成的集合。二叉搜索树是一种找、插入和删除效率都很好的一种数据结构。首先，判断一个树是否为二叉搜索树应该满足以下几点：
1.该树首先是二叉树。
2.对于任意结点 ，如果该结点的左子树存在，左子树上的点都不比该结点更大，如果右子树存在，右子树上的点都不比该结点小。如图1-1，展示了一棵二叉搜索树。
1.2二叉搜索树访问方式
数据项之间，依赖各自关键码彼此区分，通过查询关键码查找对应的值。我们称这种访问为关键码访问。这种访问方式有一定的条件。关键码之间支持大小比较和相等比较。
template<typename K,typename V> struct Entry
{
K key; V value;//关键码和值
Entry (K k=K(),V v=V()) :key(k) ,value(v){};//默认构造函数
Entry (Entry<K,V> const& e): key(e.key),value(e.value){};//克隆
//
bool operator<(Entry<K,V> const&e){return key<e.key;}//小于
bool operator>(Entry<K,V>const & e){return key>e.key;}//大于
bool operator==(Entry<K,V>const & e){return key==e.key;}//等于
bool operator!=(Entry<K,v>const & e){return key!=e.key;}//不等于
}我们可以看到Entry是一种键–值类型关系。定义了键值比较关系.从函数重载的操作可以看出，Entry<K,V>类型的数据转换成了key关键码之间的比较。
1.3有序性和单调性
有序性
：在局部结点内，BST满足左后代不大于该结点。右后代不小于该结点。
单调性
：对于整个二叉搜索树而言，满足了局部的有序性，在整个数据项中满足单调性。中序遍历情况下正好是一组单调递增的序列。
2.查找
如图2-1所示，以查找数据7为例，根结点先与数据7比较，发现6<7,将比较结点跳转到右子树9，发现7<9,再将控制权交给9的左孩子。访问该结点，发现与所查找等值。我们来看代码：
typedef struct BinNode
{
int data;
struct BinNode *lChild, *rChild;
}BinNode,*BinTree;//定义搜索树
int searchBST(BinTree T,int key,BinTree f,BinTree *p)
{
if(!T)//如果查找失败
{
*p=f;
return false;
}
else if(key==T->data)//查找成功
{
*p=T;
return true;
}
else if(key<T->data)//查找值较小时
searchBST(T->lChild,key,T,p);
else//查找值较大时
searchBST(T->rChild,key,T,p);
}
3.插入
BST的插入操作也比较容易实现，插入操作只需要与键值比较，如果比键值小，就插入到该结点的左孩子，如果比他大，插入右孩子。如图：
从根结点开始，Key与根比较，key<6,此时左孩子结点不为空结点，将控制权交给根结点左孩子。同理，key>2。右孩子结点也不为空结点，又把控制权交给了右孩子。此时需要比较结点为4。key>4，而发现右孩子为空，此时需要把结点插入。
代码：
int insertBST(BinTree* T,int key)
{
BinTree p,s;
if(!searchBST(*T,key,NULL,&p))//如果没找打，应该插入
{
s=(BinNode)malloc(sizeof(BinNode));//建立结点
s->data=key;
s->lChild=s->rChild=NULL;//并把左右孩子设置为空
if(!p)
{
*T=s;
}
else if(key<p->data)//
{
p->lChild=s;
}
else
{
p->rChild=s;
}
}
}
4.删除
删除操作就比较复杂，因为要保证二叉搜索树结构的完整性，删除有可能破坏结构，所以，我们应该分情况考虑删除结点。
下面是三种可能删除的情况：
1.删除叶子结点。
2.删除有一个孩子的结点。
3.删除有两个孩子的结点。
1.叶子结点
删除叶子结点是最容易实现的一种情况，叶子结点没有孩子，删除它时直接删除即可，不会影响到结构。如图4-1所示：
2.有一个孩子
有一个孩子也比较简单，只需要把要删除的结点与孩子结点进行交换，直至删除的结点变为叶子结点，按照删除叶子结点删除该结点。
3.有两个孩子
两个孩子就会比较麻烦，因为删除两个该结点后会形成两棵子树。而我们需要做的就是结构调整。如何调整？化繁为简，只需要将要删除的结点与
直接前驱或后继
交换，将删除该结点转化为删除直接后继，后继结点转化为删除只有一个孩子或者叶子结点的情况。
如图4-3，假设要删除6,6有左右两个孩子。 此时，6结点直接后继是7。我们把6与7交换，此时6变成了叶子结点。然后按照删除叶子结点删除6。
代码如下：
int eraseBST(BinTree * T, int key)
{
if(!*T)//如果未找到该结点
return false;//返回false;
else
{
if(key==(*T)->data)//直接找到
return delete(T);
else if(key<(*T)->data)
return eraseBST(& (*T)->lChild,key);//如果比删除结点值大，进入左孩子
else
return eraseBST(&(*T)->rChild,key);//如果比删除结点值小，进入右孩子
}
}
int delete(BinTree *p)
{
BinTree q,s;
if((*p)->rChild==NULL)//如果删除结点右孩子为空
{
q=*p;
*p=(*p)->lChild;//把左孩子重接到该结点
free(q);
}
else if((*p)->lChild==NULL)//如果删除节点左孩子为空
{
q=*p;
*p=(*p)->rChild;//把右孩子重接到该结点
free(q);
}
else//如果两个都不为空
{
q=*p;
s=(*p)->lChild;
while(s->rChild)//指向直接前驱
{
q=s;
s=s->rChild;
}
(*p)->data=s->data;//交换之间前驱与删除结点的值
if(q!=*p)
q->rChild=s->lChild;//重接q右子树
else
q->lChild=s->lchild;//重接左q子树
free(s);
}
return true;
}