Definition - Code eines gepflanzten Baums

• Eigenschaften:
  • Gepflanzte Bäume sind isomorph genau dann, wenn sie den gleichen Code aufweisen
• Hinreichende Aussagen:
  • Der Code eines gepflanzten Baumes ist stets wohlgeklammert
• Involvierte Definitionen:
  • Gepflanzter Baum
  • Alphabet
  • Wort
  • direkter Nachfahre
  • Blatt
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Code eines gepflanzten Baums

Wir codieren gepflanzte Bäume als Wörter (im Folgenden Code) über dem Alphabet .

Für einen gepflanzten Baum definieren wir seinen Code wie folgt:

• Alle Blätter erhalten den Code .
• Ist ein Knoten mit direkten Nachfahren (in dieser Reihenfolge), deren Codes sind, so erhält den Code

Anmerkung

Zeichnen eines gepflanzten Baumes aus einem Code