程序代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTree
{
int elem;
struct BiTree *Lchild;
struct BiTree *Rchild;
}BiNode;
void BiT_Create(BiNode *T,int x)
{
BiNode *Temp;
BiNode *New;
Temp=T;
if(T->elem==-1)
{
T->elem=x;
T->Lchild=NULL;
T->Rchild=NULL;
return;
}
else if(Temp->elem>=x)
{
if(Temp->Lchild==NULL)
{
if((New=(BiNode*)malloc(sizeof(BiNode)))!=NULL)
{
New->elem=x;
New->Lchild=NULL;
New->Rchild=NULL;
Temp->Lchild=New;
}
}
else
BiT_Create(Temp->Lchild,x);
}
else
{
if(Temp->Rchild==NULL)
{
if((New=(BiNode*)malloc(sizeof(BiNode)))!=NULL)
{
New->elem=x;
New->Lchild=NULL;
New->Rchild=NULL;
Temp->Rchild=New;
}
}
else
BiT_Create(Temp->Rchild,x);
}
}
void BiT_Init(BiNode *T,int array[],int size)
{
int i;
for(i=0;i<size;i++)
BiT_Create(T,array[i]);
}
void BiT_Print(BiNode *T)
{
BiNode *Temp;
Temp=T;
if(!Temp)
return;
BiT_Print(Temp->Lchild);
printf("%d ",Temp->elem);
BiT_Print(Temp->Rchild);
}
int BiT_Search(BiNode *T,int x,int size)
{
int i=0;
BiNode *Temp;
Temp=T;
if(i<size)
{
if(Temp->elem==x)
return 1;
else if(Temp->elem>=x&&Temp->Lchild!=NULL)
BiT_Search(Temp->Lchild,x,size);
else if(Temp->elem<x&&Temp->Rchild!=NULL)
BiT_Search(Temp->Rchild,x,size);
else
return 0;
}
}
void BiT_Delete(BiNode *pre,BiNode *T)
{
BiNode *Temp;
BiNode *Trans;
Temp=T;
if(Temp->Lchild==NULL) //判断当前结点左孩子是否为零
{
if(Temp==pre->Lchild) //判断前驱结点
{
pre->Lchild=Temp->Rchild;
}
else
if(Temp==pre->Rchild)
{
pre->Rchild=Temp->Rchild;
}
// free(Temp); //就算没有这个不影响结果
}
else if(Temp->Rchild==NULL)
{
if(Temp==pre->Lchild) //判断前驱结点
{
pre->Lchild=Temp->Lchild;
}
else
if(Temp==pre->Rchild)
{
pre->Rchild=Temp->Lchild;
}
//free(Temp); //就算没有这个不影响结果
}
else
{
Trans=T->Lchild;
while(Trans->Rchild)
{
Temp=Trans;
Trans=Trans->Rchild;
}
T->elem=Trans->elem;
if(Temp!=T)
Temp->Rchild=Trans->Rchild;
else
Temp->Lchild=Trans->Lchild;
// free(Trans); //就算没有这个不影响结果
}
}
int BiT_Delenode(BiNode *pre,BiNode *T,int x)
{
BiNode *Temp;
Temp=T;
if(!Temp)
return 0;
else
{
if(Temp->elem==x)
{
BiT_Delete(pre,Temp);
return 1;
}
else if(Temp->elem>x)
BiT_Delenode(T,Temp->Lchild,x);
else
BiT_Delenode(T,Temp->Rchild,x);
}
}
int main()
{
BiNode *T;
int *array;
int size;
int i;
printf("Input the size of the ARRAY:");
scanf("%d",&size);
array=(int*)malloc(size*sizeof(int));
for(i=0;i<size;i++)
{
printf("Input the elem of No.%d in the ARRAY:",i);
scanf("%d",&array[i]);
}
T=(BiNode*)malloc(sizeof(BiNode));
T->elem=-1;
T->Lchild=NULL;
T->Rchild=NULL;
BiT_Init(T,array,size);
BiT_Print(T);
putchar('\n');
BiT_Delenode(T,T,3);
BiT_Print(T);
getchar();
getchar();
free(T);
return 1;
}
不过如果连续输入3 3 3 3结果不正常
或者第一个是3时候
[
本帖最后由 点线面 于 2011-2-13 17:56 编辑 ]