Удалить узел в BST

Question

У меня проблема с функцией удаления узла в 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);
}

Я подозреваю, что как узел не установлен в нуль, что вызывает проблемы при печати, и это продолжается.
Пожалуйста помоги.

Answer 1

Вы должны сохранить указатель на предыдущий узел, чтобы вы могли обновить новые ссылки на 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 соответствующий узел, но после того, как вы пройдете его после этого, указатель на узел, который был ранее freeИспользуется d, что приводит к неопределенному поведению.