Eu já fiz a árvore de Huffman o único problema que eu não consigo nem imaginar como resolver é gerar as palavras-código. Essa palavra é gerada da seguinte forma:
Cada folha representa um símbolo do alfabeto de entrada
O caminho percorrido entre o nó da árvore de Huffman e a folha é a palavra-código daquela folha
Pegando uma aresta para esquerda adiciona-se um 0 a palavra-código , indo para a direita adiciona-se um 1 a concatenação desses bits dá a palavra código da folha.
O que eu não sei é justamente fazer um algoritmo que gere o código de todas as folhas…
primeiramente vc pegara todos os caracteres do arquivo e convertera um a um em binário, certo?
depois vc criara uma arvore digital(arvore cujas arestas sao 0 ou 1). Por exemplo o caractere A que corresponde a 01000001 em binario será inserido na sua arvore. Assim se um outro A aparecer vc percorerá a arvore digital e incrementara sua frequencia. Assim esta feita a arvore de frequencias.
Depois disso vc criará um heap(lista de prioridades) com os valores de frequencia da arvore de frequencia. Depois siga o seguinte procedimento: Tire dois nos do heap e coloque de volta o valor da soma dos dois que sairam e o faça apontar para os seus filhos(os dois q o originaram) e em cada um dos filhos(os q sairam) faça os apontar para o seu pai(o novo no q foi inserido com sua soma). Assim a cada iteração vc retirara 2 nos e coloca um novo. quando esse heap tiver somente um elemento, esse seu elemento será a raiz da arvore de huffman.
Agora vc tem uma nova arvore de huffman!!
Agora vc le o arquivo da mesma forma q vc leu para criar a arvore de freq. So que qdo vc chegar num no que é folha ele tambem será folha da arvore de hufman. Agora eh so percorrer de baixo para cima na arvore de huffman assim vc tera o novo valor para o caractere …
caso vc tenha duvidas ainda vc pode mandar um email pra mim q te mando o codigo em C q fiz…
espero ter ajudado
Olá
Qdo vc le um caractere vc tera q encontrar seu valor em binario e pegar cada bit. Em C isso nao eh facil, vc tem q usar operadores bit a bit e o operador de deslocamento, por exemplo,
char a=‘A’;
int deslocamento=7;
int binario = (a>>i)&1;
esse codigo acima pega o valor do primeiro bit do caractere ‘A’ convertido em binario. Axo q em java deve haver uma maneira mais facil de fazer isso. Depois disso vc criara a arvore. O no da arvore so deve ter o campo frequencia visto q outros campos sao desnecessarios. Por exemplo se vc pegou um valor um do caractere vc deverá descer para a esquerda ou seja vc deve ir para a subarvore esquerda do no q vc esta no momento. Lembre-se que a arvore é uma arvore digital. Se vc encontra um zero ou um para percorrer o caractere isso significa somente q vc deverá descer para esquerda ou para a direita…
vlw
allberson! poderia me enviar o código em C que você fez
a teoria eu já entendi e seria bem mais fácil fazer em java mas estou fazendo como trabalho e o professor pediu que fosse implementado em C
estou com dificuldade em fazer algumas partes principalmente a parte de percorrer a árvore e fazer akela movimentação bit a bit.