Trouver la valeur minimale d'un arbre 2-3-4

Question

Tout d’abord, cette question n’est pas un devoir.Je lis actuellement le livre "Data Structures and Algorithms 2nd Edition" de Robert Lafore.Au chapitre 10, nous avons découvert les arbres 2-3-4 et il nous est ensuite demandé d'écrire une méthode pour trouver la valeur minimale dans ledit arbre.

D'un point de vue conceptuel, je comprends où se situe la valeur minimale.Il s'agit simplement de l'élément de données le plus à gauche d'une feuille.

Du point de vue de la programmation, je ne sais pas trop comment implémenter une méthode pour trouver cet élément de données.J'ai un booléen qui peut dire si le nœud est une feuille.Donc ce que j'ai fait au départ c'est ça :

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

Ce que cela fait (du moins ce que je pense que cela devrait faire, c'est créer un curNode qui commence au nœud racine.Créez ensuite une valeur min qui stocke curNode.getMin.getMin() obtient simplement la valeur du tableau à l'index 0 (où la valeur la plus basse doit être conservée).Ensuite, même si le nœud actuel n’est pas une feuille, nous devons passer au prochain enfant à partir du point minimum.Une fois que le nœud actuel est une feuille, il doit renvoyer la valeur minimale.

Cela ne fonctionne pas cependant.Quelqu'un a-t-il une idée sur la façon de mettre en œuvre cela ?Des conseils, des suggestions ou autre chose ?

Modifier:Pour voir chacune des classes et comment elles interagissent, voici des liens vers chaque classe distincte.J'ai mis la méthode de la valeur minimale dans ma classe Tree234

Élément de données, Nœud, Arbre234, et où le programme est exécuté, Tree234App

Answer 1

Tout d'abord, pour une meilleure aide plus tôt, postez un SSCCE cela nous donne une implémentation minimale de l'ensemble de votre programme - quelque chose que nous pouvons transférer dans notre propre IDE et exécuter nous-mêmes pour voir ce qui se passe.Il est difficile de dire pourquoi « cela ne fonctionne pas » quand nous ne voyons que cette partie de votre code.

Deuxièmement, vous devez expliquer ce que signifie « cela ne fonctionne pas », c'est-à-dire :dites-nous exactement ce qu'il fait ou ne fait pas d'inattendu.Au lieu que vous l'ayez fait, comment pourrions-nous vous dire avec certitude pourquoi il fait cela.

Cependant, une chose saute aux yeux :Vous instanciez min en tant que plus petit enfant (direct) du nœud racine, puis (vraisemblablement) parcourant l'arborescence pour y trouver l'élément le plus à gauche, mais vous renvoyez ensuite le même min valeur que vous avez créée initialement.En d’autres termes, même si votre routine itérative fait exactement ce que vous voulez, vous ne faites rien à la valeur de retour.

Je suppose que vous devez faire quelque chose comme :

  public long minValue() {
      Node curNode = root;
      long min = curNode.getMin();
      while(!curNode.isLeaf()) { // 
           curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here 
       } 
       //curNode is now the leftmost non-leaf element in the tree
       min = curNode.getMin();
       return min;

Notez que le seul changement que j'ai apporté a été d'insérer la ligne au-dessus de l'instruction return, qui réaffecte min à la valeur minimale attachée à l’élément le plus à gauche de l’arborescence.

Answer 2

Pour plus d'efficacité, sachez que vous n'avez pas besoin d'appeler getNextChild(curNode, min), puisque les éléments du nœud sont toujours triés par ordre croissant dans l'arborescence 2-3-4 et que le plus petit élément est toujours à l'index 0.La déclaration du min n’est pas non plus nécessaire au démarrage.Votre programme pourrait donc ressembler à ceci :

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}