Suppression d'un objet à partir d'un arbre

Question

J'ai une fonction de recherche pour trouver un élément d'un BST

private Node Find(ref Node n, int e) 
     { 
      if (n == null) 
       return null; 

      if (n.Element == e) 
       return n; 
      if (e > n.Element) 
       return Find(ref n.Right, e); 
      else 
       return Find(ref n.Left, e); 
     } 

et j'utiliser le code ci-dessous pour obtenir un nœud puis définissez ce nœud à null. Supposément, ce nœud devrait être supprimé de Tree car il est défini sur null mais il existe toujours dans l'arborescence.

Je l'avais fait avant mais cette fois-ci il manque quelque chose et je ne sais pas quoi.

Answer 1

vous devez obtenir en quelque sorte le nœud parent de celui que vous voulez supprimer. Ensuite, si le nœud à supprimer est celui de gauche vous

parent.Left = null 

si c'est le droit:

parent.Right = null 

Avec cette méthode, vous devez savoir que vous allez supprimer le nœud de l'arbre, mais aussi tous ses descendants

Answer 2

Vous initialisez la variable x pour référencer le résultat de l'appel de Find, puis vous réattribuez la même variable à null. Tu n'as rien fait à l'arbre.

Pour supprimer réellement l'élément, vous devez écrire du code qui manipule l'arbre lui-même. Sans savoir quel type d'arbre vous avez (rouge-noir, AVL, etc.), il est difficile de deviner à quoi devrait ressembler ce code.

Answer 3

Modifié:

Ce code supprime le nœud de l'arbre, mais ne retourne pas:

private void Remove(Node n, int e) 
    { 
     if (n == null) 
      return; 

     if (e > n.Element) { 
      if (e == n.Right.Element) 
       n.Right = null; 
      else 
       Remove(n.Right, e); 
     } else { 
      if (e == n.Left.Element) 
       n.Left = null; 
      else 
       Remove(n.Left, e); 
     } 
    } 

Ce code renvoie également le nœud:

private Node Remove(Node n, int e) 
    { 
     if (n == null) 
      return null; 

     if (e > n.Element) { 
      if (e == n.Right.Element) { 
       Node res = n.Right; 
       n.Right = null; 
       return res; 
      } else 
       return Remove(n.Right, e); 
     } else { 
      if (e == n.Left.Element) { 
       Node res = n.Left; 
       n.Left = null; 
       return res; 
      } else 
       return Remove(n.Left, e); 
     } 
    } 

Quel était le problème avec le code d'origine:

Imaginez que les points de bsTree à l'arbre suivant:

5 

1  7 

Nous maintenant nommer les nœuds a, b, et c, de sorte qu'ils contiennent les valeurs 5, 1 et 7, respe ctively, comme

a 

b  c 

a.Left pointe maintenant à b et a.Right des points à c.

Désormais, nous souhaitons supprimer le noeud contenant 1, c'est-à-dire le noeud b. Pour ce faire, il faut changer l'arbre, de sorte que a.Left est null et l'arbre ressemblera à ceci:

5 

     7 

Maintenant, nous passons par l'étape de code d'origine par étape.Tout d'abord:

Node x = bsTree.Find(1); 

x est déclarée et pointe désormais au nœud b. L'arbre est inchangé.

x = null; 

x est maintenant définie sur null, mais a.Left pointe encore des points à b. L'arbre est toujours inchangé.

bsTree.Print(); 

Nous avons maintenant imprimé l'arbre.

Answer 4

Supprimer un nœud d'un arbre est un peu difficile. J'ai déjà écrit un code de suppression d'un arbre de recherche binaire. Le code est en C, mais il donne clairement l'idée.

delete_tree void (noeud ** racine, int val) {

node *del = search_tree(root, val); 

node *suc; 

if (del == NULL) { 
    printf("The value does NOT exist\n"); 
    return; 
} 

if (del->left == NULL || del->right == NULL) { 
    bst_replace(root, del); 
    return; 
} 

suc = del->right; 

while (suc->left != NULL) 
    suc = suc->left; 

del->val = suc->val; 

bst_replace(root, suc); 

return; 

}

de bst_replace vide (noeud ** racine, noeud * del) {

node *child; 
if (del->left == NULL) 
    child = del->right; 
else 
    child = del->left; 

if (*root == del) 
    if (child != NULL) { 
     child->sup = NULL; 
     *root = child; 
     return; 
    } 
    else { 
     free(del); 
     *root = NULL; 
     return; 
    } 



if (del->sup->left == del) 
    del->sup->left = child; 
else 
    del->sup->right = child; 

if (child != NULL) 
    child->sup = del->sup; 

free(del); 

return; 

}

nœud * search_tree (nœud ** racine, int val) {

node *temp = *root; 

while (temp != NULL) 
    if (val < temp->val) 
     temp = temp->left; 
    else if (val > temp->val) 
      temp = temp->right; 
    else return temp; 



return NULL; 

}