求助!写二叉排序树的时候写了个删除节点算法,运行到后面总是崩溃,我是试验叶子节点能否删除,请大佬帮忙指正下错误
#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;
typedef struct BSNode{
KeyType key;
struct BSNode *lchild, *rchild;
}BSNode, *BiTree;
//54,20,66,40,28,79,52
int BST_Insert(BiTree &T, KeyType k)
{
//如果树空,创建树根
if(NULL == T)
{
T = (BiTree)malloc(sizeof(BSNode));
T->key = k;
T->lchild = T->rchild = NULL;
return 1;
}
//如果插入的元素在树中已有,则不插入
else if(k == T->key)
{
return 0;
}
//若左子树非空,则左子树上的值均小于根节点的值
else if(k<T->key)
{
return BST_Insert(T->lchild, k);
}
//若右子树非空,则右子树上的值均大于根节点的值
else
{
return BST_Insert(T->rchild, k);
}
}
//创建二叉排序树
void Creat_BST(BiTree &T, KeyType str[], int n)
{
int i = 0;
T = NULL;
while(i<n)
{
//将数组中的元素依次插入
BST_Insert(T, str[i]);
i++;
}
}
//递归实现,但时间复杂度大,效率低
BSNode *BST_Search(BiTree &T, KeyType key)
{
if(T == NULL) return NULL;
if(key < T->key)
{
return BST_Search(T->lchild, key);
}
else if(key > T->key)
{
return BST_Search(T->rchild, key);
}
else if(T->key = key)
{
return T;
}
}
//用循环实现查找
BSNode * BST_Search(BiTree T, KeyType key, BiTree &p)
{
p = NULL;
while(T!=NULL && T->key!=key)
{
p = T;
if(key < T->key) T = T->lchild;
else T = T->rchild;
}
return T;
}
bool DeleteNode(BiTree &T, KeyType key)
{
if(T!=NULL)
{
//如果查找的值比根节点小,就查找左子树,如果比根节点大,就查找右子树
if(key < T->key) DeleteNode(T->lchild, key);
else if(key > T->key) DeleteNode(T->rchild, key);
//如果相等,若左右节点为空,直接释放节点资源(删除节点)
else
{
if(T->lchild == NULL && T->rchild == NULL)
{
free(T);
T == NULL;
return true;
}
}
}
return false;
}
void InOrder(BiTree &T)
{
if(T!=NULL)
{
InOrder(T->lchild);
printf("%4d", T->key);
InOrder(T->rchild);
}
}
int main()
{
BiTree T;
//用来存储父亲的地址值
BiTree parent;
BiTree search;
KeyType str[] = {10,5,15,6,4,16}; //将要进入二叉树的元素值
Creat_BST(T, str, 6); //左子节点比parent小,右子节点比parent大
//printf("aaa\n");
InOrder(T);
printf("\n");
//递归查找
// search = BST_Search(T, 20);
//if(search) printf("%d\n", search->key);
//else printf("未查找到\n");
//循环查找
//search = BST_Serach(T, 41, search);
if(DeleteNode(T, 4))
{
printf("删除成功\n");
}
else
{
printf("失败!\n");
}
InOrder(T);
printf("\n");
system("pause");
return 0;
}