10.3 BinTreeNode

Methode nextNode

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

10.3 BinTreeNode
Hi,

kann mir jemand erklären was bei der nextNode Methode verlangt ist. Habe jetzt mehrere Sachen implementiert und alle sind leider falsch. Am besten mit einem kleinen Beispiel, wie die Methode funktionieren soll.

Hier der Text der Aufgabe:

Searches the entire tree to which this node belongs to (i.e. also traversing in parent direction!) for the node containing the smallest value greater than the value of the current node.
@return the node containing the smallest value greater than the value of this node if any, {@code null} otherwise

zB bekomme als Fehlermeldung:

ava.lang.AssertionError: BinTreeNode.nextNode failed expected same:<((-1042)-78(253))> was not:
Expected :((-1042)-78(253))
Actual :null

moechte die Methode auch mehr als nur einen Knotenwert. Expected siehst so aus als wäre der Wert des ganzen Teilbaums.


Die Methode möchte halt den Knoten (nicht nur den Wert) mit dem nächsthöheren Wert haben und um den zu finden wird auch in “Elternrichtung” durchsucht, also nicht nur nach unten. Beispielsweise wenn die Methode auf einem Knoten aufgerufen wurde der den Wert 18 hat und der nächsthöhere Knoten im Baum den Wert 20 hat, dann soll er diesen finden und ausgeben, dazu kann man sich überlegen wie man vorgehen muss, also wo dieser Wert in einem sortierten Baum sein muss, wenn man zB keinen rechten Knoten hat, oder keinen Elternknoten etc.

1 „Gefällt mir“

Die Suchbaumeigenschaft der Binären Suchbäumen besagt, dass der linker Knoten stets kleiner als der Wurzel ist und der rechter Knoten stets größer als der Wurzel ist.

Jetzt überleg dir mal, was sind die vier Fälle, die es geben können?

Der Ausgangsknoten ist dabei der Knoten, worauf wir die nextNode Methode aufrufen.

1.) Der Ausgangsknoten ist ein innerer Knoten
2.) Der Ausgangsknoten ist ein innerer Knoten mit nur einem Kind
3.) Der Ausgangsknoten ist ein Blattknoten aber nicht die Wurzel
4.) Der Ausgangsknoten ist die Wurzel des gesamten Baums.

Jetzt solltest du anhand dieser Information einen Algorithmus dafür entwerfen können. (Schlüsselwort → Suchbaumeigenschaft)

1 „Gefällt mir“

Und je nachdem ob der Ausgangsknoten der rechte oder der linke Kind des jeweiligen Elternknotens ist, kann der Elternknoten größer oder kleiner sein als dem Kind.

1 „Gefällt mir“

DANKE AN ALLE :slight_smile:

1 „Gefällt mir“

Oder man benutzt einfach die zuvor implementierte Inorder Ausgabe…


Nein, dann stimmt die Laufzeit nicht mehr.


Bei mir hat alles problemlos funktioniert und ich habe auch die volle Punktzahl angerechnet bekommen.