0

我在 BST 中删除节点功能有问题。我测试了所有其他功能都可以正常工作，但是如果我在删除节点后打印树，则会导致分段错误。
这是我的删除代码：

struct Tree * findinorder (struct Tree *t)
{
   while (t->lchild != NULL)
         t=t->lchild;
   return t;       
}

bool deleteNode (struct Tree *t, int fvalue)
{
 bool find = false; //this is to check if node is already found don't go to right sub tree
 struct Tree *inorder;
 if (t==NULL) return find;
 if (t->value == fvalue)
 {
    if (t->lchild == NULL && t->rchild == NULL )
    {
       free(t);
    }
    else {
         if (t->lchild ==NULL)
            t= t->rchild;
         else {
            if (t->rchild ==NULL)
               t= t->lchild;
            else {
                       inorder = findinorder(t->rchild);
                       t->value = inorder->value;
                       free(inorder);
            }
         }
    }
    return true;
 }
 find = deleteNode(t->lchild, fvalue);
 if (!find)
    find = deleteNode(t->rchild, fvalue);
 return find;   
}

这是用于打印的树结构和功能：

struct Tree
{
   int value;
   struct Tree *lchild;
   struct Tree *rchild;       
}*root;

void print (struct Tree *t)
{
    if (!t) return;
    if(t->lchild != NULL)
                 print(t->lchild);  

    printf("%d\n",t->value);             

    if(t->rchild != NULL)
                 print(t->rchild);
}

我的怀疑是节点未设置为 null 导致打印问题并继续存在。
请帮忙。

4

1 回答 1

0

您应该保留指向前一个节点的指针，以便您可以相应地更新对rchild/的新引用lchild：

在此处输入图像描述

假设node是一个指向 5 的指针，删除（在这个具体情况下）应该看起来更像：

if (node->rchild && node->rchild->value == 21) {
    struct Tree *child = node->rchild;
    node->rchild = child->rchild;             // <-- update reference
    free(child);
}

但是看看节点 21 并想一想删除它后会发生什么？...代码应该比free找到节点后仅调用指向节点的指针更复杂:)

在您的情况下发生的事情是您free是适当的节点，但是一旦您在此之后遍历它，就会使用指向先前已freed 的节点的指针，这会产生undefined behavior。

于 2013-09-22T10:23:15.203 回答