Suppression de l'arbre de recherche binaire (Méthode Inorder Pred) C++

Question

Ok, donc je pensais que c'était corrigé, mais je reçois des résultats totalement incohérents. Je l'ai réécrit à partir de rien pour repartir à zéro et voici mes résultats. Je n'ai pas d'erreur, je ne plante pas, ça ne les supprime pas. Cela ne fait que salir complètement l'arbre et me donne une tonne de feuilles de plus, et ça mélange tout. Je ne sais pas où aller

template <class T> 
void BST<T>::remove(struct Node<T>*& root, const T& x) 
{ 
    Node<T>* ptr = root; 
    bool found = false; 
    Node<T>* parent; 


    while (ptr != NULL && !found) 
    { 
     if (x < ptr->data) 
     { 
      parent = ptr; 
      ptr = ptr->left; 
     } 
     else if (x > ptr->data) 
     { 
      parent = ptr; 
      ptr = ptr->right; 
     } 
     else 
      found = true; 
    } 

    if (found == false) 
     return; 
    else 
    { 
     if(ptr->left != NULL && ptr->right != NULL) 
     { 
      Node<T>* inOrderPtr = ptr->left; 
      parent = ptr; 
      while (inOrderPtr->right != NULL) 
      { 
       parent = inOrderPtr; 
       inOrderPtr = inOrderPtr->right; 
      } 

      ptr->data = inOrderPtr->data; 
      ptr = inOrderPtr; 
     } 
    Node<T>* subPtr = ptr->left; 
    if (subPtr == NULL) 
     subPtr = ptr->right; 

    else if (parent->left == ptr) 
     parent->left = subPtr; 

    else 
     parent->right = subPtr; 

    delete ptr; 
    } 

Answer 1

sont chacun T trouvé dans l'arbre unique? On dirait qu'ils sont de votre code ...

On dirait que cela devrait fonctionner:

Dans le cas d'autre suppression du nœud racine:

Node<T> *tmp_r = root->left; 
Node<T> *parent = root; 
while (tmp_r->right != NULL) 
{ 
    parent = tmp_r; 
    tmp_r = tmp_r->right; 
} 
Node<T> *tmp_l = tmp_r; 
while (tmp_l->left != NULL) 
    tmp_l = tmp_l->left; 

tmp_l->left = root->left; 
tmp_r->right = root->right; 
parent->right = NULL; 

parent = root; 
root = tmp_r; 
delete parent; 

Answer 2

Vous ne devriez pas appellerez remove() récursive dans le troisième cas (où votre « ne sais pas si cela est juste » commentaire est). Dans le cas où le nœud à supprimer a deux enfants, ce que vous voulez faire est de trouver l'enfant le plus à droite de l'enfant gauche (comme vous le faites, le nœud résultant est stocké dans parent). Ce noeud n'a pas d'enfant droit - faites en sorte que son enfant droit soit le bon enfant du noeud à supprimer. Il suffit ensuite de changer la variable root pour qu'elle soit l'enfant de gauche; pas besoin de changer le membre data dans les nœuds ou d'appeler remove récursivement.

En images:

 
Before: 
     r <- root points here 
    /\ 
    / \ 
    a  b 
    /\ /\ 
    x c y y 
    /\ 
    x d 
     /
     x 

After: 
     a <-- root points here 
    /\ 
    x c 
    /\ 
     x d 
     /\ 
     x b 
     /\ 
      y y 

Answer 3

Qu'est-ce qui se passait vraiment est que cela pourrait recherches ont été inversés, donc ça continuerait juste à aller droit mais les données ne correspondaient pas vraiment correctement et donc ça frapperait un mur.

if (root->data < x) 
     remove(root->left, x); 
    else 
     remove(root->right, x); 

aurait dû être

if(x < root->data) 
remove(root->left, x); 
else 
remove(root->right, x);