二叉查找树是一种特殊的二叉树，一般数据域都是数值类型的元素，原因是二叉查找树基本性质决定了，在二叉查找树中的任意结点，其数据域的数值一定大于它的左子树的所有结点，也小于它的右子树的所有结点！！！所以，是可以比较的数据域才是二叉查找树的存在意义！
这里我写了几个二叉查找树的方法，前几个比较简单，唯一有点难度的是删除结点的操作！
如果待删除的结点是叶子结点，非常好办，删之即可！
如果待删除的结点是非叶子结点，就稍微麻烦一点。非叶子结点也分为两种：有一个子结点和有两个子结点的情况，她们也要分开讨论：
我直接用a代表待删除的结点，这样减少了很多文字叙述，还容易理解！
1、待删除的结点有一个子结点： 这个还是比较容易，用a的双亲结点直接指向a的子结点，然后释放a即可；
2、待删除的结点有两个子结点： 也就是左孩子和右孩子均存在，这才是比较麻烦的，一般的策略是：将a的数据域 = 右子树中的最小数据结点的数据域（设 b），
然后删除这个b结点，由于b是a右子树中的最小数据结点，所以b不可能有左孩子，只可能是有一个右孩子（利用1删之）或者b就是一片叶子，删之十分轻松加愉快，哈哈语病。
好了，上代码，删除结点的操作我会好好注释一下：
#include <stdio.h>
#include <stdlib.h>
/*数据域类型*/
typedef int ElemType;
/*二叉树的结点结构*/
typedef struct _TreeNode
{
ElemType data;
struct _TreeNode * lchild;
struct _TreeNode * rchild;
}TreeNode,*PTree;
/*构造一颗空树*/
void MakeEmpty(PTree * T)
{
if(*T != NULL)
{
MakeEmpty(&(*T)->lchild);
MakeEmpty(&(*T)->rchild);
free(*T);
}
*T = NULL;
}
/*查找结点*/
PTree Find(PTree T,ElemType e)
{
if (T->data == e)
{
return T;
}
else if (T->data > e)
{
return Find(T->lchild,e);
}
else if(T->data < e)
{
return Find(T->rchild,e);
}
}
/*非递归查找最大的结点*/
PTree FindMax(PTree T)
{
if (!T)
{
return NULL;
}
while (T->rchild)
{
T = T->rchild;
}
return T;
}
/*递归查找最小结点*/
PTree FindMin(PTree T)
{
if( !T )
{
return NULL;
}
if(T->lchild == NULL)
{
return T;
}
else
{
return FindMin(T->lchild);
}
}
/*插入结点*/
PTree InsertNode(PTree T, ElemType e)
{
if (!T)
{
T = (PTree)malloc(sizeof(TreeNode));
if(!T)abort();
T->data = e;
T->lchild = NULL;
T->rchild = NULL;
}
if(e < T->data)
{
T->lchild = InsertNode(T->lchild,e);
}
else if(e > T->data)
{
T->rchild = InsertNode(T->rchild,e);
}
return T;
}
/*删除结点*/
PTree DeleteNode(PTree T, ElemType e)
{
PTree tmp;
if(!T)
{
exit(-1); /*空树删个JB*/
}
else if (e<T->data)
{
T->lchild = DeleteNode(T->lchild,e); /*递归左子树*/
}
else if(e>T->data)
{
T->rchild = DeleteNode(T->rchild,e); /*递归右子树*/
}
else if(T->lchild && T->rchild) /*如果待删除的结点左右孩子均存在*/
{
tmp = FindMin(T->rchild); /*找到其右子树中的最小结点*/
T->data = tmp->data;
T->rchild = DeleteNode(T->rchild,T->data); /*删除这个最小数据结点*/
}
else
{/*这个条件里说明是只有一个结点的情况*/
tmp = T; /*临时变量用于释放结点*/
if (T->lchild == NULL) /*只有左孩子*/
{
T = T->rchild;
}
else if( T->rchild == NULL) /*只有右孩子*/
{
T = T->lchild;
}
free(tmp);
}
return T;
}