Rekursiver Aufbau eines fraktalen Huffman-Baums

Python Hard recursion

Aufgabe «Rekursiver Aufbau eines fraktalen Huffman-Baums»

Gegeben ist eine Zeichenkette aus lateinischen Buchstaben (Kleinbuchstaben). Es ist ein fraktaler Huffman-Baum zu erstellen: Für jedes Zeichen wird seine Häufigkeit berechnet, dann wird rekursiv ein Baum aufgebaut, wobei jeder Knoten die Summe der Häufigkeiten des linken und rechten Teilbaums enthält und die Blätter die Zeichen enthalten. In jedem Rekursionsschritt muss die Liste der Zeichen so in zwei Teile geteilt werden, dass die Summe der Häufigkeiten im linken Teil möglichst nahe an der Summe der Häufigkeiten im rechten Teil liegt (gieriger Algorithmus). Es ist eine Zeichenkette zurückzugeben, die den Baum in Präfixnotation darstellt: für einen Knoten — 'F{Summe}', für ein Blatt — 'L{Zeichen}'. Rekursion ist zwingend erforderlich.

Eingabeformat

Eine Zeichenkette, bestehend aus lateinischen Kleinbuchstaben (Länge von 1 bis 100).

Ausgabeformat

Eine Zeichenkette – die Präfixnotation des Baums ohne Leerzeichen.

Beispiele

Beispiel 1

EINGABE

1
42

AUSGABE

L1

Beispiel 2

EINGABE

nil nil nil

AUSGABE

F11F6LnLiF5LlL 

Beispiel 3

EINGABE

abc

AUSGABE

F3LaF2LbLc

Beispiel 4

EINGABE

0 1 2

AUSGABE

F5F3L0L F2L1L2

main.py