удалить узел в 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, что дает неопределенное поведение.