小的数值放在左边，大的放在右边。
定义
二叉排序树：又称为二叉查找树，或者是一棵空树，或者具有以下性质
- 左子树如果不为空，那么左子树上所有结点的值均小于他的根的值
- 右子树如果不为空，那么右子树上所有结点的值均大于他的根的值
- 他的左右子树也分别为二叉排序树（递归）
查找操作
实现代码如下：
//二叉链表结点结构定义
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode. *BiTree;
//递归查找二叉排序树中T是否存在key，指针f指向T的双亲，其初始调用值为NULL。
//若查找成功，p指向该数据元素结点，并返回TRUE
//否则指针p指向查找路径上访问的最后一个结点，返回FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if(!T)
{
*p = f;
return FALSE;
}
else if(key == T->data)
{
*p = T ;
return TRUE;
}
else if(key < T->data)
{
return SearchBST(T->lchild, key ,T,p);
}
else if(key > T->data)
{
return SearchBST(T->rchild, key ,T,p);
}
}
插入操作
代码实现
//当二叉排序树T中不存在关键字等于key的数据元素时，插入key并返回True
Status InsertBTS(BiTree *T, int key)
{
BiTree p ,s;
//查找不到key
if(!SearchBST(*T, key ,NULL,&p))
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
//注意，p是查找时返回的最后一个结点的位置，也就是最接近s数值的位置
if(!p)
{
*T = s ;//他自己成为了树
}
else if(key < p->data)
{
p->lchild = s; //插入s为左孩子
}
else if(key > p->data)
{
p->rchild = s; //插入s为左孩子
}
return TRUE;
}
else
return FALSE;
}
删除操作
如果要删除叶子结点，那么只需要将叶子删除
如果删除的只有左子树或者右子树，删除后只需要继续接上
但是如果删除的又有左子树又有右子树，比较麻烦。
假如要删除105这个结点
Status DeleteBST(BiTree *T, int key)
{
if(!*T)
{
return FALSE;
}
else
{
if(key == (*T)->data)
{
return Delete(T);
}
else if(key < (*T)->data)
{
return DeleteBST(&(*T)->lchild, key);
}
else
{
return DeleteBST(&(*T)->rchild, key);
}
}
}
Status Delete(BiTree *p)
{
BiTree q,s;
if((*p)->lchild == NULL)
{
q = *p;
*p = (*p)->lchild;
free(q);
}
else if((*p)->rchild == NULL)
{
q = *p;
*p = (*p)->rchild;
free(q);
}
else
{
q = *p ;
s = (*p)->lchild;
//找到p的直接前驱s,也就是左子树的最右子树
while(s->rchild)
{
q =s;
s = s->rchild;
}
(*p)->data = s->data;//数据替换
//没有右子树
if(q != *p)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
free(s);
}
}