Erreur de dépassement de pile lors de la suppression du noeud BST dans C

Question

Je rencontre actuellement un problème que je n'arrive pas à résoudre. Le but est d'essayer de supprimer un noeud d'un arbre de recherche binaire. Pour une raison quelconque, je continue à courir dans un débordement de pile à cause de cette fonction. Y a-t-il quelque chose qui me manque?

int delete(struct node * n,int value) { 
//if there is no bst 
if (n == NULL || head == NULL) { 
    return 0; 
} 

//if head node is the node that has to be deleted 
if (head->value == value) { 
    if (head->left != NULL && head->right == NULL) { 
     head = head->left; 
    } else if (head->left == NULL && head->right != NULL) { 
     head = head->right; 
    } else if (head->left != NULL && head->right != NULL) { 
     int temp = leftOfRight(head); 
     head->value = temp; 
     delete(head->right,temp); 
    } else { 
     head = NULL; 
    } 
} 

if (n->left != NULL && n->left->value == value) { //if left node is the one that has to be deleted 
    if (n->left->left != NULL && n->left->right != NULL) { 
     int temp = leftOfRight(n->left); 
     n->value = temp; 
     delete(n->right,temp); 
    } else if (n->left->left != NULL) { 
     n->left = n->left->left; 
    } else if (n->left->right != NULL) { 
     n->right = n->right->right; 
    } else { 
     n->left = NULL; 
    } 
} else if (n->right != NULL && n->right->value == value) { 
    if (n->right->left != NULL && n->right->right != NULL) { //if right node is that one that has to be deleted 
     int temp = leftOfRight(n->right); 
     n->value = temp; 
     delete(n->right,temp); 
    } else if (n->right->left != NULL) { 
     n->right = n->right->left; 
    } else if (n->right->right != NULL) { 
     n->right = n->right->right; 
    } else { 
     n->right = NULL; 
    } 
} else if (value < n->value) { 
    return delete(n->left,value); 
} else if (value > n->value) { 
    return delete(n->right,value); 
} 
return 1; } 

Answer 1

Le principal problème est que vous ne définissez pas vos pointeurs vers nullptr après avoir appelé delete. Cela conduit à un comportement indéfini.

Permettez-moi de démontrer:

//Create ptr & set to nullptr 
Node* p_node = nullptr; 
std::cout << "ptr: " << p_node << std::endl; 

//Create new node on heap and point to it 
Node* n = new Node(11); 
p_node = n; 
std::cout << "ptr: " << p_node << " node val: " << p_node->value << std::endl; 

//Delete pointed-to object 
delete p_node; 
std::cout << "ptr: " << p_node << " node val: " << p_node->value << std::endl; 

//Set both ptrs back to nullptr 
p_node = nullptr; 
n = nullptr; 
std::cout << "ptr: " << p_node << std::endl; 

sortie:

ptr: 0 
ptr: 0x8c7de0 node val: 11 
ptr: 0x8c7de0 node val: 3504064 
ptr: 0 

Supprimer ne supprime pas le pointeur, mais appelle la destructor du pointé à l'objet et Libère la mémoire. Après cela, nous allons accéder à la mémoire aléatoire.

Quelques autres points:

• Il est difficile de savoir l'ensemble du contexte, mais votre méthode de traverser l'arbre semble un peu confus. La plupart des implémentations BST utilisent une boucle while avec un Node* current que vous utilisez pour parcourir la liste de façon récursive jusqu'à atteindre la valeur à supprimer, ou devient nullptr - while (current != nullptr) ... if (current->value == value) break; puis vous vérifiez si le noeud a 0,1 ou 2 enfants - et agissez en conséquence . C'est beaucoup plus simple à lire de cette façon. Si vous voulez l'abstraire, vous pouvez écrire une fonction find_node qui renvoie simplement un ptr à un nœud trouvé.
• Use nullptr plutôt que NULL.