Definition - Code eines Baumes

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

⠀

Definition: Code eines Baumes

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

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

Um den Code eines Baumes zu bestimmen, ermitteln wir zunächst die kanonische Basis des Baums.

Anschließend codieren wir als Wurzelbaum .

Anmerkung

Konkatenieren von und

Natürlich müssen wir nicht erneut den gesamten Baum als Wurzelbaum codieren.

Wir können auch und konkatenieren. Dabei müssen wir jedoch darauf achten, dass die äußeren Klammern anders gesetzt werden müssen. Die kanonische Wurzel “verliert” ihre unmittelbaren Klammern. Diese umschließen jetzt nämlich den gesamten Code des Baums.

Sei .
Da die kanonische Wurzel ist, verliert sie ihre äußerste Klammer. Sei die Codierung von ohne die äußerste Klammer.

Um die Reihenfolge von und zu entscheiden, müssen wir jetzt noch einmal die lexikographische Ordnung prüfen. Ist , so erhalten wir: