Construction récursive de l’arbre fractal de Huffman

Python Hard recursion

Tâche «Construction récursive de l’arbre fractal de Huffman»

Étant donnée une chaîne de caractères de l’alphabet latin (lettres minuscules). Il faut construire l’arbre fractal de Huffman : pour chaque caractère, calculer sa fréquence, puis construire récursivement un arbre où chaque nœud contient la somme des fréquences des sous-arbres gauche et droit, et les feuilles contiennent les caractères. À chaque étape de récursion, il faut diviser la liste des caractères en deux parties de sorte que la somme des fréquences dans la partie gauche soit la plus proche possible de la somme des fréquences dans la partie droite (algorithme glouton). Renvoyer une chaîne représentant l’arbre sous forme de notation préfixée : pour un nœud — 'F{somme}', pour une feuille — 'L{caractère}'. La récursion est obligatoire.

Format d\ entrée

Une chaîne de caractères composée de lettres latines minuscules (longueur de 1 à 100).

Format de sortie

Une chaîne — la notation préfixée de l’arbre, sans espaces.

Exemples

Exemple 1

ENTRÉE

1
42

SORTIE

L1

Exemple 2

ENTRÉE

nil nil nil

SORTIE

F11F6LnLiF5LlL 

Exemple 3

ENTRÉE

abc

SORTIE

F3LaF2LbLc

Exemple 4

ENTRÉE

0 1 2

SORTIE

F5F3L0L F2L1L2

main.py