Как удалить поддерево в языке BST C?

Question

Я хочу сделать функцию pop для удаления узла и поддерева узла. Вот мой код

void pop(struct data *node,int num) 
{ 
    if(node) 
    { 
     if(node->num==num) 
     { 
      pop(node->left,num); 
      pop(node->right,num); 
      free(node); 
      node=NULL; 
     } 
     else 
     { 
      if(num> node->num) 
       pop(node->right,num); 
      else if (num< node->num) 
       pop(node->left,num); 
     } 
    } 
} 
void pre(struct data *node) 
{ 
    if(node) 
    { 
     printf("%d ",node->num); 
     pre(node->left); 
     pre(node->right); 
    } 
} 
void main() 
{ 
    push(&root,37); 
    push(&root,20); 
    push(&root,45); 
    push(&root,5); 
    push(&root,15); 
    push(&root,40); 
    push(&root,50); 
    pre(root); 
    pop(root,5); 
    pre(root); 
    getchar(); 
} 

Предварительная функция работает задолго до того, как я использую pop. Но после того, как я использовал функцию pop, это перерыв. Может ли кто-нибудь знать, где ошибка?

Answer 1

В pop вы делаете: node=NULL; - но это влияет только на копию указателя, переданного функции, а не указателя в исходном дереве. Ваше дерево сохраняет указатель на данные, которые вы сейчас освободили. В следующий раз, когда вы многое сделаете с деревом, вы попытаетесь разыменовать этот указатель, и все упадет и начнет бум (по крайней мере, вы надеетесь, что они это сделают - еще хуже, иногда они могут показаться сработавшими).

Один из способов исправить это передать двойной указатель на pop:

void pop(struct data **node, int num) { 

    if ((*node)->num == num) 
     // ... 
     free(*node); 
     *node = NULL; 
    } 
} 

Теперь вы меняете курсор в дереве вместо изменения копию этого ваша функция получила.

Это все еще не работает, но в зависимости от pop(child, num); для уничтожения поддеревьев текущего узла, но если их num не установлено ни на что, просто пройдите по дереву, ища узел с подходящим num.

Возможно, вам нужна одна функция для поиска дерева, в котором находится интересующий вас узел, а затем второй, который проходит дерево, начинающееся с назначенного узла, и (безоговорочно) уничтожает этот узел и его поддеревья.

Answer 2

Ну ваша функция поп должна быть так:

struct data* pop(struct data *node,int num) 
{ 
    struct data* temp=null; 
if(node) 
{ 
    if(node->num==num) 
    { 
     if(node->left) 
     pop(node->left,node->left->num); 
     if(node->right) 
     pop(node->right,node->right->num); 
     free(node); 
    } 
    else 
    { 
     if(num> node->num) 
      temp=pop(node->right,num); 
     else if (num< node->num) 
      temp=pop(node->left,num); 

     if(node->right==temp) 
     node->right=null; 
     else if(node->left==temp) 
     node->left=null; 
     return temp; 
    } 
} 
return node; 
} 

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