我写的二叉查找树可以编译运行，而且除了删除操作外，其他的操作（正文）
其他的操作都能正确执行，删除操作的问题是，在一次执行中，删除操作只能运行一次，第二次执行删除操作时，就会出现“0x00401351”指令引用的“0xdddddde1”内存，该内存不能为“read”
以下是源代码，源代码都有详细注释的：
程序代码：
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
int N; //用来指示输入的数字的个数
typedef struct bstNode
{
int key;
struct bstNode *lchild,*rchild;
}BSTNode,*BSTree;
void CreatTree(BSTree *root,int data[]) //创建二叉查找树
{
BSTree p; //新建结点，用于接收malloc申请地址赋值
BSTree current; //当前结点
BSTree father; //父结点
int i;
for(i=0;i<N;i++)
{ /*创建一个新结点，并指定结点内容，左子树和右子树置空*/
p=(BSTree)malloc(sizeof(BSTNode));
p->key=data[i]; //利用大for循环使主函数中的data数组的序号和创建结点的顺序同步
p->lchild=NULL;
p->rchild=NULL;
if(*root==NULL)
*root=p; //根节点为空
else
{
current=(*root); //目前的位置在根结点
while(current != NULL)
{
father=current; //记录父结点
//当前结点数据大于等于输入数据，则此数据送往左子树
if(current->key >= data[i])
current = current->lchild;
//当前结点数据小于输入数据，则此数据送往右子树
else
current = current->rchild;
}
//连起父与子结点
if(father->key > data[i])
father->lchild = p;
else
father->rchild = p;
}
}
}
BSTree SearchBST(BSTree root,int key)
{
int counter=0; //查询次数计数器
BSTree p;
p=root;
while(p!=NULL)
{
counter++;
if(p->key==key)
{
printf("查找次数为:%d\n",counter);
return p; //查找成功，返回查找到的结点
}
else
{
if(key < p->key)
p=p->lchild; //在左子树中继续查找
else
p=p->rchild;
}
}
printf("查找次数为:%d\n",counter);
return 0; //查找失败
}
void InsertBST(BSTree *root,int key) //二叉排序树的插入
{
BSTree p;
BSTree father;
BSTree current;
p=(BSTree)malloc(sizeof(BSTNode));
p->key=key;
p->lchild=NULL;
p->rchild=NULL;
if(*root==NULL)
*root=p;
else
{
current=(*root);
while(current!=NULL)
{
father=current;
if(key<(current->key))
current=current->lchild;
else
current=current->rchild;
}
if(key<(father->key)) //将current连接到p上
father->lchild=p;
else
father->rchild=p;
}
}
void output(BSTree root) /*中序遍历输出二叉排序树,递归实现*/
{
if(root!=NULL)
{
output(root->lchild);
printf("%d ",root->key);
output(root->rchild);
}
}
int Delete(BSTree p)
{ //若删除的结点是叶子节点，直接根据指向叶子节点的指针变量p，用free(p)来删除叶子节点
//以下用if，else来选择处理删除的结点有一个孩子结点或有2个孩子结点的情况
BSTree q=NULL;
BSTree s=NULL;
if(!p->rchild && !p->lchild)
{
free(p);
p=NULL;
}
else if(!p->rchild) //目标结点右子树为空，只需重接它的左子树
{
q=p;
p=p->lchild;
free(q);
q=NULL;
}
else if(!p->lchild) //目标结点左子树，只需重接他的右子树
{
q=p;
p=p->rchild;
free(q);
q=NULL;
}
else
{
q=p;
s=p->lchild;
while(s->rchild != NULL)
{
q=s;
s=s->rchild;
} //转左，然后向右到尽头
p->key = s->key; //s指向被删结点的中序序列的“前驱”
//根据p的左孩子是否有右孩子来判断的
if(q!=p) //p的左孩子有右孩子，那么q就会从和p指向的同一结点处离开
q->rchild=s->lchild; //重接q的右子树
else
q->lchild=s->lchild;//重接q的左子树
free(s);
s=NULL;
}
return OK;
}
int DeleteBST(BSTree root,int key)
{
if(root==NULL) //树为空返回错误
return ERROR;
else
{
while(root!=NULL)
{
if(key==root->key)
return Delete(root); //找到要删除的元素后，传入指向目标元素的指针调用Delete函数
else if(key<(root->key))
root=root->lchild;
else
root=root->rchild;
}
return ERROR;
}
/*另一种else的写法
else
{
if(key==root->key)
return Dlete(T);
else if(key < root->lchild)
return DeleteBST(root->lchild,key);
else
return DeleteBST(root->rchild,key);
} */
}
main()
{
int key,i,flag=1,select;
int *data;
BSTree root=NULL;
BSTree p;
printf("请输入要输入数据的个数:");
scanf("%d",&N);
data=(int *)malloc(sizeof(int)*N);
printf("输入树的数据(中间用空格隔开):\n");
for(i=0;i<N;i++)
scanf("%d",data+i);
printf("\n");
CreatTree(&root,data); //创建二叉查找树
/*创建的二叉查找树从小到大的排列*/
printf("二叉查找树从小到大的排列:");
output(root);
/*-----------操作说明------------*/
printf("\n1.查询数据");
printf("\n2.插入数据");
printf("\n3.删除数据");
while(flag)
{
printf("输入要操作的序号:\n");
scanf("%d",&select);
printf("\n");
switch(select)
{
case 1:
printf("输入要查的数据值:\n");
scanf("%d",&key);
p=SearchBST(root,key);
if(p)
printf("要查的数据是：%d\n",p->key);
else
printf("查无此数据\n");
break;
case 2:
printf("输入要插入的数据值:\n");
scanf("%d",&key);
InsertBST(&root,key);
/*创建的二叉查找树从小到大的排列*/
printf("插入成功之后二叉查找树从小到大的排列:");
printf("\n");
output(root);
break;
case 3:
printf("\n请输入要删除的数据值：");
scanf("%d",&key);
DeleteBST(root,key);
output(root);
break;
}
}
}
