Ermitteln des Mindestwerts eines 2-3-4-Baums

Question

Zunächst einmal ist diese Frage keine Hausaufgabe.Ich lese gerade das Buch „Data Structures and Algorithms 2nd Edition“ von Robert Lafore.In Kapitel 10 haben wir etwas über 2-3-4-Bäume gelernt und werden dann gebeten, eine Methode zu schreiben, um den Mindestwert in diesem Baum zu finden.

Vom Konzept her verstehe ich, wo der Mindestwert liegt.Es handelt sich lediglich um das am weitesten links stehende Datenelement in einem Blatt.

Aus programmtechnischer Sicht bin ich etwas verwirrt darüber, wie ich eine Methode implementieren soll, um dieses Datenelement zu finden.Ich habe einen booleschen Wert, der erkennen kann, ob der Knoten ein Blatt ist.Was ich also ursprünglich gemacht habe, war Folgendes:

  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()

Was dies bewirkt (zumindest denke ich, dass es tun sollte), ist die Erstellung eines curNode, der am Wurzelknoten beginnt.Erstellen Sie dann einen Mindestwert, der curNode.getMin speichert.getMin() ruft einfach den Wert im Array bei Index 0 ab (wo der niedrigste Wert gehalten werden sollte).Während der aktuelle Knoten kein Blatt ist, sollten wir dann vom Minimalpunkt zum nächsten untergeordneten Knoten übergehen.Sobald der aktuelle Knoten ein Blatt ist, sollte er den Mindestwert zurückgeben.

Das funktioniert allerdings nicht.Hat jemand eine Idee, wie man das umsetzen kann?Hinweise, Vorschläge oder sonstiges?

Bearbeiten:Um die einzelnen Klassen und ihre Interaktion zu sehen, finden Sie hier Links zu den einzelnen Klassen.Ich habe die Minimalwertmethode in meine Tree234-Klasse eingefügt

Datenelement, Knoten, Baum234, und wo das Programm ausgeführt wird, Tree234App

Answer 1

Um früher bessere Hilfe zu erhalten, posten Sie zunächst eine SSCCE Das gibt uns eine minimale Implementierung Ihres gesamten Programms – etwas, das wir in unsere eigene IDE integrieren und selbst ausführen können, um zu sehen, was los ist.Es ist schwer zu sagen, warum „das nicht funktioniert“, wenn wir nur diesen Teil Ihres Codes sehen.

Zweitens müssen Sie näher erläutern, was „das funktioniert nicht“ bedeutet – d. h.Sagen Sie uns genau, was es tut oder nicht tut, was unerwartet ist.Wie könnten wir Ihnen, anstatt dass Sie es getan hätten, mit einiger Sicherheit sagen, warum es das tut?

Eines fällt jedoch auf:Sie instanziieren min als kleinstes (direktes) untergeordnetes Element des Wurzelknotens, dann (vermutlich) durch den Baum iterieren, um das Element ganz links darin zu finden, aber dann geben Sie dasselbe zurück min Wert, den Sie ursprünglich geschaffen haben.Mit anderen Worten: Während Ihre iterative Routine möglicherweise genau das tut, was Sie möchten, haben Sie dadurch keine Auswirkung auf den Rückgabewert.

Ich vermute, Sie müssen so etwas tun:

  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;

Beachten Sie, dass die einzige Änderung, die ich vorgenommen habe, das Einfügen der Zeile über der Return-Anweisung war, die eine Neuzuweisung bewirkt min auf den Mindestwert, der dem Element ganz links im Baum zugeordnet ist.

Answer 2

für mehr Effizienz, Beachten Sie, dass Sie nicht generakodicetagcode anrufen müssen, da die Elemente in Knoten immer in aufsteigender Reihenfolge in einem 2-3-4-Baum sortiert sind, und der kleinste Artikel ist immer am Indexgenera getNextChild(curNode, min).MIN-Erklärung ist auch nicht notwendig.Ihr Programm könnte also so sein:

generasacodicetagpre.