如何设置指针无效？

Question

我编写了一个二叉搜索树，并创建了一个删除节点的函数。 通常它有两个输入参数，第一个是指向需要删除的对象的指针，第二个指向二叉搜索树根。

基本上，我所有的情况下工作，除了“最简单”的节点是叶。

我的代码将应该删除的节点的内容设置为0，但是仍然有对此的引用，并且它显示在树中。

* p是应该被删除的元素。

* pBaum指向树的根部。

* p-> right和* p-> left指向* p的右和左子树。

* p-> conten是* p的值。

我的代码在叶案：

struct tnode *deletenode(struct tnode *p, struct tnode *pBaum) 
{ 
    if (p !=NULL) 
    { 

     if ((p->left == NULL) && (p->right == NULL)) 
     { 
     printf("%d Ist Blatt \n", p->content); 
     free(p); 
     return pBaum; 
     } 

Basicly我“只”需要告诉指针* P，它从现在起无效。但我无法找到一个合适的解决方案。也许你们可以帮忙。

编辑：好吧，我已经尝试过，我自己将父指针设置为NULL。

struct tnode* danglingPointerFix (struct tnode *p, int nodtodelete) 
{ 
if((p->right)->content = nodtodelete) 
    { 
     p->right = NULL; 
     return 0; 
    } 
    if((p->left)->content = nodtodelete) 
    { 
     p->left = NULL; 
     return 0; 
    } 
} 

struct tnode *searchnode(struct tnode *p, int nodtodelete) 
{ 
if (p == NULL) 
{ 
    printf("Baum ist leer oder Element nicht vorhanden \n"); 
    return 0; 
} 
if (p -> content == nodtodelete) 
{ 
    return p; 
} 
if (p->content < nodtodelete) 
{ 
    danglingPointerFix(p, nodtodelete); 
    return searchnode (p->right, nodtodelete); 
} 
if (p->content > nodtodelete) 
{ 
    danglingPointerFix(p, nodtodelete); 
    return searchnode(p->left, nodtodelete); 
} 
} 

但即时segfaulting，也许某处可以看到哪里，因为在我看来这个解决方案应该工作。

Answer 1

你必须找到指向你想要删除的叶父节点。找到后，应将父指针对应的left或right指针设置为NULL。

所以你删除应该像：

struct tnode *deletenode(struct tnode *p, struct tnode *pBaum) 
{ 
    if (p !=NULL) 
    { 

     if ((p->left == NULL) && (p->right == NULL)) 
     { 
      // This is a leaf --> It may be deleted 
      deleteNodeInParent(pBaum, p); 

      printf("%d Ist Blatt \n", p->content); 
      free(p); 
      return pBaum; 
     } 

然后，你需要实现deleteNodeInParent。它与您当前的搜索功能非常相似，只不过您会检查是否left == p或right == p以及 - 如果是 - 将值设置为NULL并返回。

喜欢的东西：

void deleteNodeInParent(struct tnode *p, struct tnode *pDeleted) 
{ 
    if (p == NULL) 
    { 
     printf("Baum ist leer oder Element nicht vorhanden \n"); 
     return; 
    } 
    if (p->left == pDeleted) 
    { 
     p->left = NULL; 
     return; 
    } 
    if (p->rigth == pDeleted) 
    { 
     p->rigth = NULL; 
     return; 
    } 

    if (p -> content == pDeleted->content) 
    { 
     // Can only happen for head - just return 
     return; 
    } 
    if (p->content < pDeleted->content) 
    { 
     deleteNodeInParent(p->right, pDeleted); 
     return; 
    } 
    if (p->content > pDeleted->content) 
    { 
     deleteNodeInParent(p->left, pDeleted); 
     return; 
    } 
} 

这么说，我认为这将是容易得多，如果你扩展了一个指向父结构TNODE。

Answer 2

尽管您已经释放了叶节点，但父节点仍然保留悬挂指针。解决它的

一种方法是增加以下功能：

struct tnode *deleteLeftNode(struct tnode *parent, struct tnode *pBaum) { 

    if (parent) { 
     deletenode(parent->left, pBaum); 
     parent->left = NULL; 
    } 
    return pBaum; 
} 

struct tnode *deleteRightNode(struct tnode *parent, struct tnode *pBaum) { 

    if (parent) { 
     deletenode(parent->right, pBaum); 
     parent->right = NULL; 
    } 
    return pBaum; 
}