Tarea «Construcción recursiva del árbol fractal de Huffman»

Dada una cadena de caracteres del alfabeto latino (minúsculas). Es necesario construir un árbol fractal de Huffman: para cada carácter calcular su frecuencia, luego construir recursivamente un árbol donde cada nodo contenga la suma de las frecuencias de los subárboles izquierdo y derecho, y las hojas contengan los caracteres. En cada paso de la recursión se debe dividir la lista de caracteres en dos partes de modo que la suma de frecuencias en la parte izquierda sea lo más cercana posible a la suma de frecuencias en la parte derecha (algoritmo voraz). Devolver una cadena que represente el árbol en notación prefija: para un nodo — 'F{suma}', para una hoja — 'L{carácter}'. La recursión es obligatoria.

Ejemplo 1

Ejemplo 2

Ejemplo 3

Ejemplo 4