Als erstes wollen wir uns Bäume per print ansehen können:
def __str__(self): nodeStrs = [] def visitFun(node, depth, nodeStrs=nodeStrs): nodeStrs.append(" "*depth+ repr(node.getValue())) self.traversePreorder(visitFun) return "\n".join(nodeStrs)
Was passiert in __str__? Eine Traversierung ist ein systematisches Laufen durch den Baum. Zur Repräsentation des Baums als String müssen wir genau das tun, und für jeden Knoten eine Funktion aufrufen, und zwar zur richtigen ZeitTM.
Es gibt drei Möglichkeiten:
Bestimmte Algorithmen brauchen auch noch die level order-Traversierung. Dabei arbeitet man immer Ebene um Ebene (also Knoten gleicher Tiefe) ab. Das passt allerdings nicht ganz in dieses Schema.
Preorder und postorder gehen offenbar auch für nicht-binäre Bäume, inorder hat nur für Binärbäume Sinn.
Welche Sorte von Traversierung gewählt wird, hängt davon ab, was man wie gemacht haben möchte. Im Beispiel möchten wir, dass die Eltern schließlich vor den Kindern stehen.
Eine Methode zur Präorder-Traversierung könnte so aussehen:
def traversePreorder(self, visitFun, depth=0): visitFun(self, depth) for node in [self.left, self.right]: if not node is None: node.traversePreorder(visitFun, depth+1)
Ihr solltet euch wenigstens an den rötlich unterlegten Aufgaben versuchen
(1)
Implementiert noch die Methoden traversePostorder und traverseInorder. Probiert, was passiert, wenn ihr __str__ mit diesen Methoden baut.