Arbre de recherche binaire: Supprimer TreeNode avec une valeur donnée x non récursivement en utilisant Java

Question

J'essaye d'écrire une méthode non-récursive qui supprime un noeud dans un arbre de recherche binaire s'il contient la valeur d'entrée donnée int x en Java. J'ai pensé que je devais utiliser une pile, mais je n'arrive pas à comprendre comment supprimer le nœud sans appeler la fonction sur lui-même.

Ceci est ma classe TreeNode à partir de maintenant. J'ai essayé cela mais je ne peux pas le faire fonctionner.

public TreeNode removeB(int x){ 
    if (this == externalnode) return externalnode; 
    TreeNode one = new TreeNode(this.data); 
    System.out.println(this); 
    Stack<TreeNode> s = new Stack();  
    s.push(one); 
    //System.out.println(s); 
    boolean check; 
    boolean check1; 
    while(check = true){ 
     if(x == one.left.data){ 
      System.out.println(one.left.data); 
      check = false; 
      return one.left; 
     } 


     if(x == one.right.data){ 
      System.out.println(one.right.data); 
      check1 = false; 
      return one.right; 
    } 
    } 

Answer 1

Votre code doit d'abord effectuer une recherche binaire pour trouver le noeud à supprimer. En pseudo-code, il ressemble à:

while (currentNode != null && currentNode.value != target) { 
    if (currentNode.value > target) { 
    currentNode = currentNode.left; 
    } else if (currentNode.value < target) { 
    currentNode = currentNode.right; 
    } 
} 

Une fois que vous avez ciblé ce nœud, vous le remplacer par un de ses enfants, puis la greffe dans l'autre enfant orphelin en dessous, tout comme vous ajouteriez n'importe quel noeud.