L'utilisation de la référence récursivement renvoyée au nœud dans l'arborescence n'autorise pas les modifications du nœud lui-même.

Question

Ma classe de structures de données fonctionne avec les arborescences. Nous implémentons un arbre 3-aire, contenant 2 valeurs avec une référence à un nœud gauche, moyen et droit (sous-arbre gauche est inférieur à la valeur 1, sous-arbre intermédiaire entre valeur 1 et valeur 2, sous-arbre droit est supérieur à valeur 2). Une interface a été fournie pour la classe Tree, et les méthodes find, insert et delete doivent être récursives. Le code client avec lequel cela va être testé utilise la méthode insert à plusieurs reprises pour créer l'arborescence et la racine commence par null.

J'essaie d'insérer des valeurs dans l'arborescence de manière récursive en trouvant le nœud parent dans une méthode privée distincte, puis en modifiant le nœud retourné comme il convient. Le problème est actuellement que la méthode renvoie le nœud initial, qui est la racine, et crée correctement un nouveau nœud avec la valeur car la racine est null. Cependant, la racine reste nulle.

Je suis assez certain que cela est dû à la façon dont les références et les valeurs fonctionnent en Java (similaire à C# comme décrit dans this article by Jon Skeet); étant donné les contraintes, comment dois-je changer cela pour permettre des insertions dans l'arbre? Vous trouverez ci-dessous la méthode d'insertion actuelle dans la classe arborescente, ainsi que la méthode privée similaire.

public void insert(AnyType newData) 
{ 
    // If insert node is null, make a new node with newData as first key 
    TernaryNode<AnyType> insert_node = findNode(newData, root); 
    if (insert_node == null) 
    { 
     insert_node = new TernaryNode<AnyType>(newData); 
    } 
    else 
    { 
     // Get the key that is equal if the insert node is not null 
     if (insert_node.getKey1() == null) 
     { 
      insert_node.setKey1(newData); 
     } 
     else 
     { 
      insert_node.setKey2(newData); 
     } 
    }// end else 
}// end insert 

private TernaryNode<AnyType> findNode(AnyType item, TernaryNode<AnyType> node) 
{ 
    TernaryNode<AnyType> current_node = node; 
    if (current_node != null) 
    { 
     if (current_node.getKey1() != item && 
       current_node.getKey2() != item) 
     { 
      // Comparator checks left 
      if (compare.compare(current_node.getKey1(), item) <= -1) 
      { 
       return findNode(item, current_node.left); 
      } // Comparator checks right 
      else if (compare.compare(current_node.getKey2(), item) >= 1) 
      { 
       return findNode(item, current_node.right); 
      }// Comparator checks middle 
      else 
      { 
       return findNode(item, current_node.middle); 
      } 
     }// end while 
    }// end if 
    // Return current node even if it is null 
    return current_node; 
}// end findNode 

Answer 1

À moins que vous affectez quelque chose au membre root, il ne sera jamais acquérir une valeur. Vous avez probablement besoin d'une sorte de conteneur externe pour votre arborescence, de la même manière qu'un document XML (qui est également un arbre) a un objet externe Document qui est distinct du nœud racine réel du document.

Answer 2

TernaryNode<AnyType> insert_node = findNode(newData, root); 
    if (insert_node == null) 
    { 
      insert_node = new TernaryNode<AnyType>(newData); 
      root = insert_node; 
    }