Rekursiv

[Chrissy_Love]

Hallo zusammen,

ich habe mal wieder ein Problem und komme absolut nicht weiter, habe auch keine idee wie ich genau anfangen soll.

Also es geht um folgendes, aus dem Suchbaum soll eine Liste generiert werden, die für jeden Studierenden nur seine/ihre Matrikelnummer und die Klausurnote enthält. Die Liste soll aufsteigend nach Matrikelnummern sortiert sein.
Zum Füllen der Liste implementieren Sie folgende rekursive Methode:

public static void erstelleNotenliste
(List<NotenInfo> notenliste, Knoten knoten)

.

Beim ersten Aufruf werden der Methode eine leere Notenliste und die Wurzel des nicht leeren Suchbaums übergeben.

Als Hinweis: Die Schnittstelle List<E> besitzt eine Methode boolean add(E elem).


Die als Bild angehängten Klassendiagramme sollen als Implentierung zur verfügung stehen.


Den Suchbaum habe ich auch als Bild angehängt.

public static void erstelleNotenliste(List<NotenInfo> notenliste, Knoten knoten)
{



}

Ich hoffe mir kann jemand weiter helfen.

Liebe Grüße

Chrissy

 

[Akeshihiro]

Also ich hab mich mal grad für paar Minuten rangesetzt und naja, ob es die optimalste Variante ist, weiß ich nicht, aber die Methode macht ihren Job.
Ausgabe:

725000 => 3.0
6875993 => 2.7
6988769 => 1.3
7056128 => 2.0
7169882 => 2.3

Hast du gar keine Idee oder haben die bisherigen Ideen einfach nur nicht funktioniert?

 

[Chrissy_Love]

Also ich habe garkeine Idee. Die Matrikelnummern mit noten sollen ja aufsteigend nach Matrikelnummer sortiert werden. Und das in einer liste. Ich glaube man muss das mit inorder machen aber ich weiß nicht wie das dann mit der liste ist.

 

[Akeshihiro]

Ich habe mich gar nicht auf das Sortieren der Liste konzentriert, dafür gibt es die Methode Collections.sort(). Viel wichtiger ist doch, wie man die Daten in die Liste bekommt. Alles Schritt für Schritt, mehrere Baustellen gleichzeitig sind meist nicht sonderlich vorteilhaft, eine reicht völlig

Ich kann dir ja mal sagen, wie ich das gemacht hab. Da die Methode ja bereits einen Knoten bekommen hat, kann man den ja auch gleich in die Liste einfügen bzw. den Studenten aus dem Knoten holen und somit dann ein NotenInfo erzeugen und dieses dann in die Liste reinschieben. Ja, und als nächstes würd ich sagen, hangelt man sich den Baum entlang. Da die Methode rekursiv sein soll, hab ich einfach die Methode dann zwei mal aufgerufen, nämlich einmal für den linken Knoten und einmal für den rechten Knoten. Dabei tritt ein Problem auf, und zwar kann es ja sein, dass es folgende Situationen gibt:
1. Alle beide Knoten sind gesetzt => kein Problem
2. Nur ein Knoten ist gesetzt => Problem
3. Gar kein Knoten ist gesetzt, also das Ende eines Zweigs ist erreicht => Problem

Wenn man also einfach immer nur die Knoten übergeben würde, dann würde es irgendwann zu einer NullPointerException kommen. Da gibt es zwei Möglichkeiten. Entweder man prüft den entsprechenden Knoten vor dem Aufruf der Methode auf null oder was ich persönlich bevorzuge, man übergibt den Knoten einfach stump an die Methode, egal ob null oder nicht. Und gleich am Anfang der Methode wird dann der Knoten auf null geprüft, wenn knoten == null, dann return. Die Liste prüfe ich übrigens auch auf null, da wenn die Liste null ist, der ganze Vorgang keinen Zweck hat. Das hat den Vorteil, dass man sowohl den Knoten, als auch die Liste nicht vor dem Aufruf explizit auf null prüfen muss, was ja aber zum Teil durch die erste Möglichkeit gegeben wäre, aber eben nur innerhalb der Methode. Der aller erste Aufruf könnte dann aber schon gleich in die Hose gehen, wenn man da nicht dran denkt vorher auf null zu prüfen. Bei der zweiten Möglichkeit ist es egal, denn die Methode prüft selbst die Parameter und wenn was nicht stimmt, dann geht's halt wieder zurück, Pech gehabt.

Und zum Schluss der Methode dann mit Collections.sort() einfach die Liste sortieren lassen und fertig ist die Geschichte.

Wie schon bereits zuvor gesagt, es gibt vielleicht bessere Lösungen, aber so klappts auch.

 

[twagi]

Hi,

da der Suchbaum ja quasi schon sortiert ist, braucht man den Aufruf von Collections.sort() nicht. Der Baum ist so aufgebaut, dass der linke Zweig immer kleiner als der rechte Zweig ist.
Daher muss nur der linke Zweig zuerst in die Liste eingefügt werden.

Ich schätze daher auch, dass bei der Matrikelnummer 725000 eine Ziffer fehlt. Daher liegt diese ganz rechts im Baum, da sie den höchsten Wert hat.

Der Algorithmus könnte also so aussehen:

1. linker Zweig existiert -> rekursiver Aufruf mit linkem Knoten
2. Wert aus aktuellem Knoten einfügen
3. rechter Zweig existiert -> rekursiver Aufruf mit rechtem Knoten

Ich hoffe, dass hilft Dir weiter.

Gruß twagi

 

[Akeshihiro]

Stimmt, hab ich ja noch gar nicht gesehen Aber was ist, wenn das nur Zufalls ist? naja, kann ja jeder halten wie er möchte. Aber ich geb zu, ich hab das echt nicht bemerkt, hab mir darum auch kein Kopf gemacht, da ich grundsätzlich davon ausgehe, dass ich als Input verhunzte Daten rein bekomm. Weiß nicht, ob das PHP-spezifisch ist, aber dadurch hab ich's mir angewöhnt xD

 

[Chrissy_Love]

Hallo danke für die Antworten. Ja es stimmt bei der 7250000 musste noch eine 0 dran. Ich habe das mal ausprobiert was ihr mir gesagt habt, hat aber nicht bei mir geklappt. Ich bin dann auf preorder gestoßen aber das klappt irgendwie auch nicht. Kennt ihr euch damit gut aus?

 

[twagi]

Hi,

kannst Du mal Deinen bisherigen Code zeigen. Vielleicht funktioniert dort noch nicht was richtig.

Pre-Order bedeutet, dass zunächst der aktuelle Knoten (Wurzel) ausgewertet wird und dann die Kinderknoten. Wobei zuerst der linke Kindknoten und dann der rechte Kindknoten ausgewertet werden.

Da im Suchbaum die Elemente so sortiert sind, dass das kleinste Element ganz links im Baum und das größte Element ganz rechts im Baum liegt, wäre in Deinem Fall In-Order die richtige Variante.

Hier wird zuerst der linke (kleinste) Kindknoten ausgewertet, dann die Wurzel und zuletzt der rechte Kindknoten.

Gruß twagi

 

[Chrissy_Love]

Ich habe nur das InOrder hier, welches ich getestet habe.

 public String traversiereInOrder()
{
if (einBaum.getWurzel() != null)
return traversiereInOrder(einBaum.getWurzel());
else return "Kein Baum vorhanden!";
}
private String traversiereInOrder(Knoten einKnoten)
{
String text = "";
if (einKnoten.getKnotenLinks() != null)
{
text += traversiereInOrder(einKnoten.getKnotenLinks());
}
text += einKnoten.getSchluessel();
if (einKnoten.getKnotenRechts() != null)
{
text += traversiereInOrder(einKnoten.getKnotenRechts());
}
return text;
}
}

 

[SE]

Ähm ... ist es richtig das du in

public String traversiereInOrder()

auf eine Instanz-Variable zugreifst ?
Weil dadurch kann es vorkommen das einBaum == null ist. Daher würde ich hier eher sowas nehmen

public String traversiereInOrder(<T> einBaum)

wobei natürlich folgendes erfüllt sein muss

T <T> einBaum != T Knoten einKnoten

oder einfach : der Typ von "einBaum" darf NICHT Knoten sein.