Hola, que tal.
Llevo un par de dias intentando implementar el algoritmo de huffman ( solo por aprender un poco más ), y a pesar de haber leido varios textos todavía tengo algunas dudas que no consigo resolver, a ver si alguien puede echarme una mano.
De momento tengo hecho:
- Tabla con valor-frequencia.
- Lista enlazada con los valores de la tabla ordenada de menor a mayor.
Es decir, teniendo la frase: "hola papa":
hola papa
Table [ 0 ] Char: Freq: 1
Table [ 1 ] Char: o Freq: 1
Table [ 2 ] Char: h Freq: 1
Table [ 3 ] Char: l Freq: 1
Table [ 4 ] Char: p Freq: 2
Table [ 5 ] Char: a Freq: 3
Total r 6
List: Char: Freq: 1
List: Char: o Freq: 1
List: Char: h Freq: 1
List: Char: l Freq: 1
List: Char: p Freq: 2
List: Char: a Freq: 3Segun lo leido, el arbol huffman se forma así:
Teniendo eso: [espacio](1) - o(1) - h(1) - l(1) - p(2) - a(3)
- Se toman los dos valores con menos frequencia, por ejemplo: ( [espacio] y o ) y se forma un arbol:
( 2 )
/ \
" "[1 peso] o[1 peso]
Y seguimos, ahora nos quedan: h(1) - l(1) - 2 - p(2) - a(3)
Así que cogemos "h" y "l".
Mi duda es que, a mi parecer, h y l deberían quedar asi:
( 4 )
/ \
( 2 ) ( 2 )
/ \ / \
" "[1] o[1] h(1) l(1)
Y nos queda: p(2) - a(3) - 4
Cogemos p( 2 ) y a(3):
( 9 )
/ \
( 4 ) ( 5 )
/ \ / \
( 2 ) ( 2 ) p(2) a(3)
/ \ / \
" "[1] o[1] h(1) l(1)
Y nos queda: 4:
( 14 )
/ \
( 9 ) ( 4 )
/ \
( 4 ) ( 5 )
/ \ / \
( 2 ) ( 2 ) p(2) a(3)
/ \ / \
" "[1] o[1] h(1) l(1)
Así que de esta forma quedaría el arbol, pero creo que no es correcto.
A ver si me podéis decir donde me voy del plano y me pierdo.
Gracias de antemano
