下面的二叉查找树在删除叶子结点时会出问题,为什么呢???
发布网友
发布时间：2022-07-13 04:01
共3个回答
热心网友
时间：2023-10-23 11:29
你要删除27这个节点，它的父节点26的rchild指针其实保存了27的地址，然后当用OrderReverse(t); 进行遍历时，26这个节点判断rchild是否为NULL，由于rchild中是原27的地址，并不为NULL，所以还是要去读原27这个地址中的值，但其实里面的内容都被你用free函数给释放掉了。
解决方法是：
可以在结构体里面增加一个保存 父子针的指针变量，这样就可以只用增加一个查找父节点的函数即可实现将rchild或lchild赋值为NULL。不然的话，你的源代码要做很大的改动才行，因为当在你的查找要删除节点是叶节点的时候，你不能够直接传递该节点指针。
热心网友
时间：2023-10-23 11:30
#include <iostream>
#include <malloc.h>
using namespace std;
typedef int keyType;
typedef int elemType;
typedef struct Node
{
keyType key;
elemType otheItem;
struct Node *lchild,*rchild;
}*nodePtr;
nodePtr BSTSearch(nodePtr t,keyType key)
{
if (t == NULL)
{
return NULL;
}
else if(t->key == key)
{
return t;
}
else if (t->key < key)
{
return (BSTSearch(t->rchild,key));
}
else
{
return (BSTSearch(t->lchild,key));
}
}
nodePtr BSTInsert(nodePtr t,nodePtr s)
{
if (t == NULL)
{
t = s;
return (t);
}
else if (t->key > s->key)
{
t->lchild=BSTInsert(t->lchild,s);
}
else
{
t->rchild=BSTInsert(t->rchild,s);
}
return (t);
}
nodePtr BSTCreat(nodePtr t)
{
nodePtr s;
t = NULL;
int a[21] = {30,22,39,12,26,35,51,11,13,25,27,32,37,50,66,17,45,15,20,40,47};
int i;
for (i = 0; i < 21; i++)
{
s = (nodePtr)malloc(sizeof(Node));
s->key = a[i];
s->lchild = NULL;
s->rchild = NULL;
t = BSTInsert(t,s);
}
return t;
}
void OrderReverse(nodePtr t)
{
if (t != NULL)
{
OrderReverse(t->lchild);
cout<<t->key<<" ";
OrderReverse(t->rchild);
free(t);
}
}
nodePtr BSTDelete(nodePtr t,int key) /*删除叶节点*/
{
if (t==NULL) return NULL;
else if (t->key<key) t->rchild =BSTDelete(t->rchild ,key);
else if (key<t->key ) t->lchild =BSTDelete(t->lchild ,key);
else {
delete t;
t=NULL;
}
return t;
}
int main(void)
{
nodePtr t;
t=BSTCreat(t);
t=BSTDelete(t,27);
OrderReverse(t);
return 0;
}
//---------------------------------------------------------------------------
热心网友
时间：2023-10-23 11:30
