Hiho!
Ich hänge seit gestern Abend an einer kleinen Aufgabe, welche ich im Rahmen einer Klausurvorbereitung machen wollte.
Vielleicht könnt ihr mir ein wenig weiterhelfen.
Aufgabe:
Und zwar geht es darum, dass ein binärer Suchbaum gegeben ist auf dem gearbeitet werden soll. Die Aufgabenstellung lautet nun, eine Methode zu schreiben, welche die Gesamtzahl der Knoten des Baumes ausgeben soll, falls sich für jeden einzelnen Knoten die Anzahl der Knoten im linken und rechten Teilbaum höchstens um den Wert 1 unterscheiden.
Wenn es mind. einen Knoten gibt, dessen Unterbäume einen größeren Unterschied aufweisen, dann soll der Wert -1 zurückgegeben werden.
Meine Lösung:
Mein Problem:
Meine Lösung funktioniert soweit prima, allerdings immer nur für die jeweiligen Teilbäume. Heißt, dass wenn er im rechten Teilbaum einen größeren unterschied feststellt, dann hört er da auf und gibt -1 zurück, allerdings läuft es im linken Teilbaum weiter. Ich hoffe ihr versteht mich^^
Mein Lösungsansatz bzw. meine Frage:
Im Endeffekt müsste man alle anderen rekursiven Aufrufe einfach überschreiben oder anhalten, falls er einen größeren Unterschied irgendwo feststellt. Allerdings darf ich laut Aufgabenstellung keine neuen Methoden zur Überprüfung anlegen und darf meinen Code nur in den "Else-Block" schreiben. Nun bin ich ein wenig überfragt^^
Ich würde mich sehr über ein paar Antworten freuen.
mfg
Barny
Ich hänge seit gestern Abend an einer kleinen Aufgabe, welche ich im Rahmen einer Klausurvorbereitung machen wollte.
Vielleicht könnt ihr mir ein wenig weiterhelfen.
Aufgabe:
Und zwar geht es darum, dass ein binärer Suchbaum gegeben ist auf dem gearbeitet werden soll. Die Aufgabenstellung lautet nun, eine Methode zu schreiben, welche die Gesamtzahl der Knoten des Baumes ausgeben soll, falls sich für jeden einzelnen Knoten die Anzahl der Knoten im linken und rechten Teilbaum höchstens um den Wert 1 unterscheiden.
Wenn es mind. einen Knoten gibt, dessen Unterbäume einen größeren Unterschied aufweisen, dann soll der Wert -1 zurückgegeben werden.
Meine Lösung:
Java:
public int sizeIfBalanced() {
if(isEmpty()) {
return(0);
}else {
int difference = 0;
if((!leftChild.isEmpty() && !rightChild.isEmpty())) {
difference = (rightChild.content.getContent() - leftChild.content.getContent());
}
if(difference > 1) {
return(-1);
}else {
return(leftChild.sizeIfBalanced() + rightChild.sizeIfBalanced()+1);
}
}
}
Mein Problem:
Meine Lösung funktioniert soweit prima, allerdings immer nur für die jeweiligen Teilbäume. Heißt, dass wenn er im rechten Teilbaum einen größeren unterschied feststellt, dann hört er da auf und gibt -1 zurück, allerdings läuft es im linken Teilbaum weiter. Ich hoffe ihr versteht mich^^
Mein Lösungsansatz bzw. meine Frage:
Im Endeffekt müsste man alle anderen rekursiven Aufrufe einfach überschreiben oder anhalten, falls er einen größeren Unterschied irgendwo feststellt. Allerdings darf ich laut Aufgabenstellung keine neuen Methoden zur Überprüfung anlegen und darf meinen Code nur in den "Else-Block" schreiben. Nun bin ich ein wenig überfragt^^
Ich würde mich sehr über ein paar Antworten freuen.
mfg
Barny