Re: Fwd: Re: HELP ME!

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Alexandre Freire writes:
 > Tiago, tenho uma explicacao sobre o dad[]. Pelo que acho ele marca o pai
 > de um elemento na arvore binaria gerada pelo codigo de huffman.

De fato, o Sedgewick diz: "The tree itself is represented with an
array of "parent" links: dad[t] in the index of the parent of the node
whose weight is in count[t].  The sign of dad[t]..."  (esta outra
frase escrevi em mensagem anterior).  Na figura 22.7 ele tambem dá um
exemplo. 

 > ou seja, vc tem o elemento "a" como folha 3 da arvore, o dad[a] é igual a
 > 1, e se vc tiver o elemento ">" como folha 4 da arvore o dad[>] é -1....
 > (talvez seja -1 e 1 não consegui determinar muito bem...)
 > Quando somamos os count[t]+count[[heap1]]
 > naquele while oque estamos fazendo é montando a arvore de huffman,
 > somando os dois elementos com menor frequencia e criando uma folha ( ou nó
 > se vc preferir) imaginaria que tem como frequencia a soma das frequencias
 > dos dois menores elementos .... entao o dad destes elementos é esse nó que
 > nao tem caractere (acho que por isso usamos numeros depois do 256)...
 > por enquanto é isso que acho...
 > Aproveitando queria saber se alguem pode me explicar efetivamente como
 > funciona o code[] e o len[], eu nao consiguo entender como que o code
 > guarda o percurso a ser percorrido na arvore de modo binario... 

no topo da pagina 329 o Sedgewick explica a tecnica que ele usou.  Yoshi

 >                                                                 alguns
 > exemplos tambem iriam ajudar......
 > Vaelu galera e forca que a ente consegue!
 > @lex
 >  Alexandre Freire      <alex@linux.ime.usp.br>