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.
Klausur SS14
Hallo alle zusammen ,
bei die Baeume Aufgabe (2) , Teil f) muss die getHeight() Methode gemacht …
ich habe die fast geschafft , aber wenn ich in der Loesungen in forum anschaue sehe ich ein groeser Unterschied zwischen miene Loesung und die Loesung da !! …
[color=deepskyblue]public int getHeight() {
if(left == null && right == null)
return 1;
if(left == null) // bei mir ist if(right!=null)
return 1 + right.getHeight();
if(right == null) // auch an die Stelle if(left!=null)
return 1 + left.getHeight();
return 1 + Math.max(left.getHeight(), right.getHeight());
}
[/color]
macht Sinn was ich gemacht habe ? oder macht mehr Sinn was in der Loesung steht ?
wenn in der Loesung nach eure Meinnung mehr Sinn macht , dann Bitte Erklaerung dazu waere ganz nett .
Überlegen wir doch mal logisch:
Wenn
left != null && right != nullist, was sollte passieren - und was passiert?
wenn left!=null dann gibt noch ein linkes Kind …
und das gilt auch fuer right …
??
vielleicht doch mein Loesung macht gar kein Sinn …!!
da sind nur Basisfaelle … wir gehen mit dem left.getHeight , und right.getHeight alle Konten durch … und wenn ich bis null komme , dann gehe ich die andere Teilbaum weiter !!..
so richtig vestanden ? …
Ja, Whitespace meinte, aber du sollst dir überlegen was sowohl für die Forenlösung, als auch bei deiner Lösung für den Fall
left != null && right != nullpassiert. Und weshalb nun welche der beiden richtig ist. 
Ja, das ist eine rekursive Funktion und ja, wenn einer der beiden Teil-Äste leer ist (null), wird der andere betrachtet. Wenn beide leer sind, dann gibt es keinen anderen Ast zu betrachten und man befindet sich auf der untersten Ebene, auf der eins zurückzugeben ist.
Angenommen wir haben folgenden Baum:
Der erste Basisfall ([m]left == null && right == null[/m]) tritt bei den Knoten A und R auf, da sie keinen linken und keinen rechten Nachfolger haben. Die Höhe dieser Knoten ist damit jeweils 1.
Der zweite Basisfall ([m]left == null && right != null[/m]) soll den Fall abfangen, wenn nur ein rechter Nachfolger existiert. Dieser Fall tritt bei dem Knoten L auf. In dem Fall ist die Höhe immer die Höhe des rechten Nachfolgers + 1, da eben kein linker Teilbaum existiert, welcher größer sein könnte.
Der dritte Basisfall ([m]left != null && right == null[/m]) ist logischerweise ähnlich wie der zweite Basisfall, bloß eben im Fall, dass nur ein linker Nachfolger existiert. Im Beispielbaum tritt dieser Fall nicht auf.
Wenn keiner dieser Fälle zutrifft, muss es logischerweise einen linken und einen rechten Nachfolger geben ([m]left != null && right != null[/m]), weshalb man dann die größere Höhe von beiden Teilbäumen wählen muss ([m]Math.max(left.getHeight(), right.getHeight())[/m]). Dies trifft zum Beispiel beim Wurzelknoten W zu. Dort gibt es sowohl einen linken, als auch einen rechten Nachfolger, weshalb die Höhe beider berechnet wird (2 und 1) und anschließend die größere Höhe (2) + 1 = 3 zurückgegeben wird.
Wenn du jetzt aber bei dem zweiten Basisfall die Bedingung ([m]left == null[/m]) durch ([m]right != null[/m]) ersetzt, geht dein Programm bei dem Knoten W auch in diesen Fall hinein und gibt die Höhe des rechten Teilbaums (1) + 1 = 2 zurück, was jedoch falsch ist, da die richtige Höhe des Knotens 3 wäre.
Danke fuer eure Antwort , habe ich endlich mal verstanden 
:nuts:
weist jemand was linksvollstaendiger Binaerbaum ist ?
kann mir jemand erklaern was ist die ?
Siehe AuD Folie 12-89:
Obiger Beispielbaum wäre kein linksvollständiger Baum, da in der letzten Ebene nicht alle Knoten so weit links wie möglich ausgerichtet sind.
kannst du mir auch mal kurz erklaeren , wenn ich in einer Graphen floyd Algorithmus fuehre …
zum Biespiel bei SS14 Kalusur , Teil d … ich habe zwei Knoten D und B … sind direkt zusammen verbunden , mit Pfadlaenge 7 , aber wenn ich zu B durch A gehe dann bekommen ich 5 …
von D durch B kann ich auch zu C , jetzt meine Frage , wird den weg bis zum C mit der 5 oder 7 betrachtet … angenommen von B zu C ist 4
ist jetzt von D–>C 11 oder 9 ? …
muss ich diese 7 bei Graph auch aendern ? …
Danke im Voraus .
Mit dem Algorithmus von Floyd berechnet man die kürzesten Wege zwischen allen Paaren von Knoten im Graphen. Wenn du durch den Algorithmus beispielsweise herausfindest, dass es einen kürzeren Pfad von X nach Y gibt, dann änderst du die Gewichtung des Pfades von X nach Y auf den neuen Wert. Bei den Iterationen danach beachtest du dann auch diesen geänderten Wert, da du ja die kürzesten Weg zwischen zwei Knoten berechnen möchtest. Und in deinem Fall ist ein Pfad der Länge 9 natürlich kürzer, als ein Pfad der Länge 11 oder 13.
Am Ende sollte dein Hilfsgraph dann so aussehen:
Ab der AuD Folie 14-73 findest du auch nochmal eine genaue Erklärung inkl. umfangreiches Beispiel.
ich hätte noch eine Frage über SS 11 …
in der Wissensfragen , steht in irgendeinen Frage Multi-Mengen …
was sind Multi Mengen ?