ich habe am Ende des Monats eine Klausur in Info 1 und bin gerade dabei dafür zu lernen.
Wir hatten eine Probeklausur in der es eine Aufgabe gibt, wo ich einfach nicht darauf komme, wie man die lösen könnte.
Die Aufgabe selber lautet:
Im Folgenden gehen wir davon aus, dass die Knoten eines Binärbaumes als Tupel (left, label, right) repräsentiert werden, wobei left der linke Teilbaum, label die Makierung und right der Rechte Teilbaum ist.
Der leer Baum wird durch None repräsentiert.
Schreiben Sie die Funktion inner_nodes(tree), die für einen übergebenen Binärbaum tree die Anzahl der inneren Knoten zählt und zurück gibt.
Ich wollte es zunächst mit der mit vertrauteren Definition [label, left, right] versuchen und dachte
vielleicht kanne ich die Preorder traversierung irgendwie verändern, die Knoten die es findet in eine Liste schreiben, das klappt jedoch alles nicht, da die rekursion dabei Probleme macht.
Code: Alles auswählen
def preorder(node):
if node is not None:
print(node[0])
preorder(node[1])
preorder(node[2])
Ich habe wenig hilfreiches im Internet gefunden, da dort alles mit Klassen gelöst worden ist, was jedoch in dieser Aufgabe nicht gefragt ist, da es ja nur eine einzelen aufgabe ist zu dem thema, die genau so heißt wie oben geschrieben. Der b) Teil in dem soll man nur einen test schreiben.
Es sollte auch relativ wenig Code genügen da es ja eine Klausuraufgabe ist (und auch relativ wenig Platz zum Lösung hinschreiben gegeben wurde).
Ich dachte man müsste irgendwie überprüfen können ob ein Knoten ein Blatt ist und wenn nicht ihn dann in eine Liste schreiben und dann die elemente der liste zählen.
Aber wie gesagt durch die wenige Hilfestellung aus der Vorlesung habe ich keine Ahnung wie ich das anstellen könnte. Ich hatte ja den Ansatz ob man z.B. die obige preorder-funktion umschreiben könnte, meine Versuche scheiterten. Geht das überhaupt als Ansatz oder ist das totaler Mist?
Ich hab 3 verschiedene Bücher hier zu Python, aber in keinem wird auch nur Bäume erwähnt. :/
Kann mir jemand helfen? Bin etwas verzweifelt und hab auch ganz schön angst vor der klausur.