二叉排序树的特点
- 若左子树不空，则左子树所有结点值均小于根结点
- 若右子树不空，则右子树所有结点值均大于根结点
- 二叉树排序树的中序遍历结果即为元素的升序序列
插入操作（构造排序树）
Status InsertBST(BiTree *T,TElemType e)
{
if((*T)==NULL)
{
(*T)=(BiTree)malloc(sizeof(BiTNode));
(*T)->lchild=(*T)->rchild=NULL;
(*T)->data=e;
return TRUE;
}
if(e<(*T)->data)//小于根结点时，插入到左子树
InsertBST(&(*T)->lchild, e);
else//大于根结点时，插入到右子树
InsertBST(&(*T)->rchild, e);
return FALSE;
}
通过插入构造二叉排序的过程，就相当于递归方式先序遍历二叉树的过程；
查找
指针p返回指向元素所在结点的指针，指针f始终指向*p的双亲结点
Status SearchBST(BiTree T,TElemType key,BiTree f ,BiTree *p)
{
if(!T)
{
*p=f;
printf("查找失败\n");
return FALSE;
}
else if(T->data==key)
{
*p=T;
printf("查找成功\n");
return TRUE;
}
else if(T->data>key)
return SearchBST(T->lchild, key,T, p);
else
return SearchBST(T->rchild, key,T, p);
}
删除结点
所要删除的结点有三种情况
- 该结点只有左子树
- 该结点只有右子树
- 该结点即有左子树又有右子树
//假设要删除结点10
第一种：
100
/ \
10 200
/
8
只需将结点8替换10，并释放10所在结点的存储空间即可
第二种：
100
/ \
10 200
\
20
将右子树20重接到10的位置，并释放10所在结点的存储空间
第三种：
100
/ \
10 200
/ \
4 20
/ \
3 7
/ \
6 9
/
8
根据中序遍历的性质，8所在结点为9所在结点的“前驱”，对于上图，只需，10所在结点的指针域用9替换，结点8接到7的右子树；
如图所示
100
/ \
9 200
/ \
4 20
/ \
3 7
/ \
6 8
第三种情况的另外一种形式为
100
/ \
10 200
/ \
4 20
/
3
此时直接结点10用其左子树替换即可
变为
100
/ \
4 200
/ \
3 20
Status DeleteBST(BiTree *T,TElemType key)
{
if(!T)
return FALSE;
else
{
if(key==(*T)->data)
return Delete(T);
else if(key<(*T)->data)
DeleteBST(&(*T)->lchild, key);
else
DeleteBST(&(*T)->rchild, key);
return TRUE;
}
}
Status Delete(BiTree *p)
{
BiTree q,s;
if(!(*p)->rchild)//右子树为空
{
q=(*p); (*p)=(*p)->lchild;free(q);
}
else if(!(*p)->lchild)//左子树为空
{
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->rchild;
else
q->lchild=s->lchild;
free(s);
}
return TRUE;
}
完整代码：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//查找(指针p返回结点指针)
Status SearchBST(BiTree T,TElemType key,BiTree f ,BiTree *p)
{
if(!T)
{
*p=f;
printf("查找失败\n");
return FALSE;
}
else if(T->data==key)
{
*p=T;
printf("查找成功\n");
return TRUE;
}
else if(T->data>key)
return SearchBST(T->lchild, key,T, p);
else
return SearchBST(T->rchild, key,T, p);
}
//插入(不要输入相同元素)
Status InsertBST(BiTree *T,TElemType e)
{
if((*T)==NULL)
{
(*T)=(BiTree)malloc(sizeof(BiTNode));
(*T)->lchild=(*T)->rchild=NULL;
(*T)->data=e;
return TRUE;
}
if(e<(*T)->data)
InsertBST(&(*T)->lchild, e);
else
InsertBST(&(*T)->rchild, e);
return FALSE;
}
//删除结点过程
Status Delete(BiTree *p)
{
BiTree q,s;
if(!(*p)->rchild)//右子树为空
{
q=(*p); (*p)=(*p)->lchild;free(q);
}
else if(!(*p)->lchild)//左子树为空
{
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->rchild;
else
q->lchild=s->lchild;
free(s);
}
return TRUE;
}
//删除指定结点
Status DeleteBST(BiTree *T,TElemType key)
{
if(!T)
return FALSE;
else
{
if(key==(*T)->data)
return Delete(T);
else if(key<(*T)->data)
DeleteBST(&(*T)->lchild, key);
else
DeleteBST(&(*T)->rchild, key);
return TRUE;
}
}
//中序遍历输出
void InOrderTraverse(BiTree T)
{
if (T)
{
InOrderTraverse(T->lchild);
printf("%d ",T->data);
InOrderTraverse(T->rchild);
}
}
int main()
{
printf("sfd\n");
BiTree T = NULL,P=NULL;
for(int i=0;i<5;i++)
{
int e;
scanf("%d",&e);
InsertBST(&T, e);
}
printf("中序遍历结果：");
InOrderTraverse(T);
printf("\n");
printf("查找元素6的结果：");
SearchBST(T, 6, NULL, &P);
DeleteBST(&T, 5);
printf("删除元素5的中序遍历结果:");
InOrderTraverse(T);
return 0;
}
/* 测试
5 4 3 2 1
中序遍历结果：1 2 3 4 5
查找元素6的结果：查找失败
删除元素5的中序遍历结果:1 2 3 4
*/