Huffmanovo kódování

[1Pupik1989]

Zdravím všechny.

Může mi někdo polopaticky vysvětlit jak zakódovat strom?

Mám konkrétně na mysli tuto stránku.

Jak přišel na "1101000"? To jako že zapisuji při každém průchodu vlevo 1 a pokud najdu potomka, tak 0?

Už se s tím patlám snad týden. Je mi jasné, že to bude prkotina, ale čím víc nad tím přemýšlím, tím to je horší.

Přiřazování kódu ke znakům mám hotové, to jsem ještě pochopil.

Děkuji za každou radu.

[nou]

tiez nechapem ako k tomu prisiel. ale nasiel som iny sposob ako ulozit ten strom.

ak mas list tak zapis 1-bit+8 bitov toho znaku. ak je to uzol tak zapis 0 a potom zapis laveho potomka a nasledne praveho. v tebou linkovanom priklade by ten strom bol zapisany takto.

01A001B01D1K1R

prva nula hovori ze koren je uzol. lavy potomok je list s A. ideme dalej. lavy potomok korena je uzol a ze lavy potomok toho uzla je zase uzol. potomok tohto druheho uzla je list s B.

[1Pupik1989]

Něco takového jsem našel na stackoverflow. To se vlastně dá zapisovat při přiřazování znaků z kořene.

Mě spíš zajímalo jak to dokázal stáhnout na 7 bitů.

//edit: Když tak koukám na ten jeho strom, tak mi to asi začíná docházet. Ona má vždy list vlevo a vrchol vpravo. O úroveň níž je to zase naopak. Takže mu nejspíš stačí uložit jen krok o úroveň níž vlevo. Je to tedy jen teorie, ale odpovídá to.

//edit2: Ten výstup jak píšeš vlastně mám.

Kód: Vybrat vše

function recursive(node,bin,level){
    if(node.left == null){ //pokud nemá potomky, pak je to list
      o[node.name] = bin;
      tree += '1'+node.name; //zapíšu 1 + znak
      return;
    }

    tree += '0'; //není list, zapíšu 0

    recursive(node.left,bin+'0',level+1);     
    recursive(node.right,bin+'1',level+1);
  };