Binärer Baum

Bekannte Beispiele für Binärbäume sind:

• der Familienbaum (Stammbaum) mit Vater und Mutter einer Person als deren Nachfolger (!)
  
  
  
• ein arithmetischer Ausdruck, wobei jeder Operator eine Verzweigung darstellt mit den zugehörigen Operanden als Teilbäume:
  
  z.B. Ergebnis = Operand1 + Operand2
  
  
  
  oder Ergebnis = (A + B + C / D) * E
  
  
  

Durchlaufen eines binären Baumes

Die Knoten müssen häufig in einer gewissen Reihenfolge abgearbeitet (durchlaufen) werden.

Es gibt im wesentlichen drei Möglichkeiten (sog. Ordnungen), die sich aus der Baumstruktur ergeben, um einen Baum zu durchlaufen:

• Preorder Durchlauf W-L-R
  
  Es wird immer zuerst die Wurzel, dann der linke Teilbaum, danach der rechte Teilbaum abgearbeitet.
  
  Diese Reihenfolge wird auch als Prefix-Notation bezeichnet.
  
  
• Inorder Durchlauf L-W-R
  
  Bei dieser Reihenfolge wandert man immer zuerst den linken Teilbaum bis zum Ende hinunter. Danach wird der direkte Vorgänger (Wurzel) abgearbeitet. Schließlich wird der rechte Teilbaum abgearbeitet.
  
  Diese Durchlaufreihenfolge wird auch als Infix-Notation bezeichnet.
  
  
• Postorder Durchlauf L-R-W
  
  Bei diesem Verfahren wird immer zuerst der linke Teilbaum, dann der rechte Teilbaum und erst am Schluß die Wurzel abgearbeitet.
  
  Dieses Verfahren wird auch als Postfix-Notation bezeichnet.

Das Durchlaufen gemäss der drei oben dargestellten Ordnungen wird anhand des folgenden arithmetischen Ausdrucks erläutert :

(A + B / C) * (D - E * F)

 

Die Sequenzen der gefundenen Zeichen (ohne Klammerung) sehen entsprechend wie folgt aus:

• Preorder Durchlauf: * + A / B C - D * E F
  
• Inorder Durchlauf: A + B / C * D - E * F
  
• Postorder Durchlauf: A B C / + D E F * - *

Aufgaben 

1. Gegeben ist folgender Binärbaum. Geben Sie die Knoten in der Reihenfolge ein, in der sie beim Durchlauf in
   
   
   • Preorder
   • Inorder
   • Postorder
   
   besucht werden.
   
   
   

» drucken: pdf | html