定义一个数组,然后在定义要搜寻,删除的结点的元素值。首先呢,我们定义结构体来定义二叉树:
typedef struct Node{
DataType data;
struct Node *lChild,*rChild;
}BiTreeNode,*BiTree;
typedef struct{
keyType key;
}DataType;
我们利用二叉查找结构体的变量的二级指针来传递地址,在二叉查找树中插入元素: BiTree T=NULL,p;
DataType table[]={37,32,35,62,82,95,73,12,5};
DataType x={73},s={32};//x是要搜寻的结点,s是要删除的结点
int n=sizeof(table)/sizeof(table[0]);
for(int i=0; i<n; i++)
{
BSTInsert(&T,table[i]);
}
看看插入函数的实现:int BSTInsert(BiTree *T,DataType x)
{
BiTree p,cur,parent=NULL;
cur=*T;
while(cur!=NULL)
{
if(cur->data.key==x.key)
return 0;
parent=cur;//找到前驱结点
if(x.key<cur->data.key)//如果关键字小于p所指向的结点的值,则在左子树中查找
cur=cur->lChild;
else
cur=cur->rChild;
}
p=(BiTree)malloc(sizeof(BiTree)*100);
if(!p)
exit(-1);
p->data=x;
p->lChild=NULL;
p->rChild=NULL;
if(!parent)//如果二叉树为空,则第一结点成为根结点
*T=p;
else if(x.key<parent->data.key)
{
parent->lChild=p;
}
else
parent->rChild=p;
}
为什么利用二级指针呢?就是利用二级指针来判断二叉查找树,以便插入。什么时候执行while呢?就是我们执行完一次for循环给二叉查找树安插了第一个结点之后,我们就能进入while了。parent结点指针指向某一元素的双亲结点,我们就是利用while来找到双亲结点,该双亲结点就是我们要插入的结点的双亲结点。在这里,尤其注意:p=(BiTree)malloc(sizeof(BiTree)*100);
在《windows在**.exe中触发了一个断点,其原因可能是堆被损坏,这说明...dll中有bug》一文中,我阐述了这句代码的重要性,如果没有分配足够的内存空间,就会出现那篇文章里的错误!下面,我们看看删除函数:
void DeleteNode(BiTree *s)//删除结点
{
BiTree q,x,y;
if(!(*s)->rChild)//若该结点没有右子树
{
q=*s;
*s=(*s)->lChild;
free(q);
}
else if(!(*s)->lChild)//若该结点没有左子树
{
q=*s;
(*s)=(*s)->rChild;
free(q);
}
else//若该结点既有左结点又有右子树
{
x=*s;
y=(*s)->lChild;
while(y->rChild)
{
x=y;
y=y->rChild;
}
(*s)->data=y->data;
if(x!=*s)//也就是程序进入了while,要删除的结点下的左子树没有右子树
x->rChild=y->lChild;
else
x->lChild=y->lChild;
free(y);
}
}
int BSTDelete(BiTree *T,DataType x)
{
if(!*T)
return 0;
else
{
if(x.key==(*T)->data.key)
DeleteNode(T);
else if(x.key<(*T)->data.key)
BSTDelete(&(*T)->lChild, x);
else
BSTDelete(&(*T)->rChild, x);
return 1;
}
}
在这里,我们主要看看DeleteNode函数,该函数实现的就是删除结点的功能。我们需要为我们所删除的结点考虑三种情况:只有左子树,右子树,既有左子树,右子树。当只有左子树的时候,就直接将该结点的左子树的元素链接到要删除的元素的位置。只有右子树的时候,也是一样的。那么,要是又有右子树,又有左子树呢?我们先这样分析:在用中序遍历输出二叉排序树的所有的元素的时候,该序列是严格的递增的,而我们的序列是这样的:
5 12 32 35 37 62 73 82 95
假设我们删除32,那么删除后的序列是:
5 12 35 37 62 73 82 95
也就是说,我们删除的32的直接前驱元素!那么,怎么找到前驱元素呢?如果我们删除了这个元素之后,根据二叉查找树的结构特点,我们需要找到该结点的左子树中的最大值,那么怎么做呢?很简单:
x=*s;//定义一个结点x,给它赋值为要查找的结点
y=(*s)->lchild;//在要删除的结点中左子树中查找,因此给y赋值第一个左子树
while(y->rChild)
{
x=y;
y=y->rChild;//在y的右子树中查找,直到没有结点了
}
下面看看实现:完整的程序:
#include "stdio.h"
#include "windows.h"
typedef int keyType;
typedef struct{
keyType key;
}DataType;
typedef struct Node{
DataType data;
struct Node *lChild,*rChild;
}BiTreeNode,*BiTree;
int BSTInsert(BiTree *T,DataType x)
{
BiTree p,cur,parent=NULL;
cur=*T;
while(cur!=NULL)
{
if(cur->data.key==x.key)
return 0;
parent=cur;//找到前驱结点
if(x.key<cur->data.key)
cur=cur->lChild;
else
cur=cur->rChild;
}
p=(BiTree)malloc(sizeof(BiTree)*100);
if(!p)
exit(-1);
p->data=x;
p->lChild=NULL;
p->rChild=NULL;
if(!parent)
*T=p;
else if(x.key<parent->data.key)
{
parent->lChild=p;
}
else
parent->rChild=p;
}
void InOrderTraverse(BiTree T)//中序遍历
{
if(T)
{
InOrderTraverse(T->lChild);
printf("%d ",T->data.key);
InOrderTraverse(T->rChild);
}
}
BiTree BSTSearch(BiTree T,DataType x)//查找结点
{
BiTree p;
if(T!=NULL)
{
p=T;
while(p!=NULL)
{
if(p->data.key==x.key)
{
return p;
}
else if(x.key<p->data.key)
p=p->lChild;
else
p=p->rChild;
}
}
return NULL;
}
void DeleteNode(BiTree *s)//删除结点
{
BiTree q,x,y;
if(!(*s)->rChild)//若该结点没有右子树
{
q=*s;
*s=(*s)->lChild;
free(q);
}
else if(!(*s)->lChild)//若该结点没有左子树
{
q=*s;
(*s)=(*s)->rChild;
free(q);
}
else//若该结点既有左结点又有右子树
{
x=*s;
y=(*s)->lChild;
while(y->rChild)
{
x=y;
y=y->rChild;
}
(*s)->data=y->data;
if(x!=*s)
x->rChild=y->lChild;
else
x->lChild=y->lChild;
free(y);
}
}
int BSTDelete(BiTree *T,DataType x)
{
if(!*T)
return 0;
else
{
if(x.key==(*T)->data.key)
DeleteNode(T);
else if(x.key<(*T)->data.key)
BSTDelete(&(*T)->lChild, x);
else
BSTDelete(&(*T)->rChild, x);
return 1;
}
}
int main()
{
BiTree T=NULL,p;
DataType table[]={37,32,35,62,82,95,73,12,5};
DataType x={73},s={32};//x是要搜寻的结点,s是要删除的结点
int n=sizeof(table)/sizeof(table[0]);
for(int i=0; i<n; i++)
{
BSTInsert(&T,table[i]);
}
printf("中序遍历的结果:\n");
InOrderTraverse(T);
p=BSTSearch(T,x);
if(p!=NULL)
printf("\n二叉排序树查找,关键字%d存在\n",x.key);
else
printf("查找失败!\n");
BSTDelete(&T,s);
printf("输出删除结点的元素值为32后的元素:\n");
InOrderTraverse(T);
system("pause");
return 0;
}