Definition - Gepflanzter Baum

• Konstrukte:
  • Code eines gepflanzten Baums
  • Isomorphie von gepflanzten Bäumen
• Generalisierungen:
  • Wurzelbaum
• Eigenschaften:
  • Der Code eines gepflanzten Baumes ist stets wohlgeklammert
• Involvierte Definitionen:
  • Wurzelbaum
  • Alphabet
  • Leeres Wort
  • Kleenesche Hülle
  • direkter Nachfahre
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Gepflanzter Baum

Sei ein Wurzelbaum.

Ist außerdem die Reihenfolge der direkten Nachfahren durch eine Funktion vorgegeben, so bezeichnen wir auch als gepflanzten Baum.

Die Reihenfolge-Abbildung

Diese Reihenfolge definieren wir allgemein als Abbildung.
Dabei interpretieren wir als Alphabet und als Menge aller “Wörter” aus dem Alphabet .

Die Reihenfolge ist dann vorgegeben durch

Wobei gelte:

• Ist , so gibt die direkten Nachfolger von in korrekter Reihenfolge als Wort an.
• Für ein Blatt ist das leere Wort über dem Alphabet .

Anmerkung

Interpretation

Die Reihenfolge-Abbildung gibt uns eine strukturelle Vorgabe für die Zeichnung des Graphen.