我正在将这本电话簿写在安排在BST的结构上 . 它由两个结构组成:
-数据结构:
typedef struct note
{
char name[LENGHT];
char surname[LENGHT];
int tel;
}data;
- 结构:
typedef struct junction
{
data entry;
struct junction* left;
struct junction* right;
}node;
我正在尝试编写一个删除给定节点的函数,但不是通过赋予它root和seek值作为参数,而是通过给它指向要删除的节点 . 最简单的情况是,当节点是叶子时,如下所示:
void mDestroy(node **dNode)
{
if((*dNode)->left==NULL&&(*dNode)->right==NULL)
{
free(*dNode);
*dNode=NULL;
return;
}
}
我已经删除了关于其他情况的其余代码,并搜索节点以替换它,如果它不是叶子 . 问题是,当我运行创建root和2个额外节点的测试代码时,从键盘获取输入,按顺序显示它们(按字母顺序),删除其中一个非根节点并再次显示它们 . 遍历树的功能:
void fDisplay(node *root)
{
if(root->left!=NULL)
fDisplay(root->left);
display(root->entry);
printf("\n\n");
if(root->right!=NULL)
fDisplay(root->right);
return;
}
并且功能ACTUALLY显示数据:
void display(data entry)
{
puts(entry.name);
puts(entry.surname);
printf("%d\n", entry.tel);
return;
}
输出实际上看起来像这样:
name1
surname1
11111111111
name2
surname2
2222222222
name3
surname3
3333333333
name1
surname1
11111111111
name2
surname2
2222222222
/*some gibberish*/
surname3
3333333333
假设我们删除了第三个条目,并且两者都直接链接到root . 它显示第三个节点,即使它在函数中已设置为NULL . 起初我传递 *node
作为参数,然后我切换到 **node
并且我调用这样的函数: mDestroy(&node1);
为什么不设置从父到NULL的链接?甚至可以在没有将父节点作为参数给出的情况下完成它(删除节点)还是不用root调用它并让它在树中搜索给定值?
1 回答
首先,我假设你正在调用这样的东西:
这是指向
aNode
的指针的地址并将其传递给destroy函数 . 然后在函数中取消引用该地址,以便您访问指针 . 然后释放指针并将其设置为NULL
. 现在aNode
指针是NULL
但是parent.right
指针没有指向NULL
,它仍然指向aNode
的旧位置 .因此,为了从树中删除节点,您必须能够访问指向该节点的树中的指针 . 然后,您必须删除该节点并将树中的指针设置为
NULL
.