Tarefa «Construção recursiva da árvore fractal de Huffman»

Dada uma string de caracteres do alfabeto latino (letras minúsculas). É necessário construir a árvore fractal de Huffman: para cada caractere, calcular sua frequência, então construir recursivamente uma árvore onde cada nó contém a soma das frequências das subárvores esquerda e direita, e as folhas contêm os caracteres. Em cada passo da recursão, deve-se dividir a lista de caracteres em duas partes de modo que a soma das frequências na parte esquerda seja o mais próxima possível da soma das frequências na parte direita (algoritmo guloso). Retornar uma string representando a árvore em notação prefixada: para um nó — 'F{soma}', para uma folha — 'L{caractere}'. A recursão é obrigatória.

Exemplo 1

Exemplo 2

Exemplo 3

Exemplo 4