Perché creare un albero di Huffman per carattere invece di un nodo?

2

Per un incarico scolastico dovremmo realizzare un'implementazione Java di un compressore / decompressore usando l'algoritmo di Huffman.

Ne ho letto un po ', specialmente questo tutorial in C ++: link

Nel mio programma, stavo pensando di avere Nodi che hanno le seguenti proprietà:

  • Frequenza totale
  • Carattere (se una foglia)
  • Figlio destro (se presente)
  • Figlio sinistro (se presente)
  • Parent (se presente)

Quindi quando si costruisce l'albero di Huffman, si tratta solo di collegare un nodo ad altri, ecc.

Tuttavia, sono un po 'confuso dalla seguente citazione (enfasi mia):

First, every letter starts off as part of its own tree and the trees are ordered by the frequency of the letters in the original string. Then the two least-frequently used letters are combined into a single tree, and the frequency of that tree is set to be the combined frequency of the two trees that it links together.

La mia domanda: perché dovrei creare un albero per lettera, invece di un solo nodo per lettera e poi fare il collegamento più tardi?

Non ho iniziato la codifica, sto solo studiando l'algoritmo per primo, quindi suppongo che mi manchi un dettaglio importante. Che cos'è?

    
posta Omega 13.11.2012 - 19:53
fonte

1 risposta

3

La riga precedente dice: "L'idea alla base dell'algoritmo è costruire l'albero dal basso verso l'alto."

Ciò che l'autrice sta dicendo è che si inizia creando un oggetto TreeNode (o qualunque cosa tu scelga di chiamare i tuoi nodi) per ogni lettera e poi combinandoli in ordine di frequenza (prima i più bassi) per costruire il finale albero.

Il dettaglio che ti manca è che puoi pensare a una TreeNode come se fosse un albero.

    
risposta data 13.11.2012 - 20:07
fonte

Leggi altre domande sui tag