53. Bäume II: Traversierungen

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 Zeit^TM.

Es gibt drei Möglichkeiten:

• preorder – in jedem Teilbaum erst den Wurzel-, dann den linken, dann den rechten Knoten bearbeiten.
• inorder – in jedem Teilbaum erst dann den linken, dann den Wurzel-, schließlich den rechten Knoten bearbeiten.
• postorder – in jedem Teilbaum erst den linken, dann den rechten Knoten, schließlich den Wurzelknoten bearbeiten.

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)