Definition - Code eines Wurzelbaums

• Konstrukte:
  • Kanonische Wurzel
  • Codierung eines Baumes
• Generalisierungen:
  • Codierung eines gepflanzten Baums
• Eigenschaften:
  • Wurzelbäume sind isomorph genau dann, wenn sie den gleichen Code aufweisen
• Involvierte Definitionen:
  • Wurzelbaum
  • Alphabet
  • Wort
  • direkter Nachfahre
  • Blatt
  • Permutation
  • Lexikographische Totalordnung
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Code eines Wurzelbaums

Wir codieren Wurzelbäume als Wörter (im Folgenden Code) über dem Alphabet mit der Ordnung:

• “öffnende Klammer ” “schließende Klammer ”, also .

Für einen Wurzelbaum definieren wir seinen Code wie folgt:

• Alle Blätter erhalten den Code .
• Ist ein Knoten mit direkten Nachfahren , deren Codes sind, so
  • sortieren wir zunächst lexikographisch zu .
  • Die Funktion sei eine hierzu passende Permutation.
  • Den Code von erhalten wir dann als

Anmerkung