[SOLVED] Huffman tree encoding question

atlantis43 · 05-16-2015, 08:22 AM

Given a Huffman Tree with struct trees composed of (only) the following members:

Code:

typedef struct tree
{
    char symbol;
    int frequency;
    struct tree* left;
    struct tree* right;
}
Tree;

I'm wondering about the process of traversing such a tree to obtain the encoding values.
I assume that as each leaf of this tree is encoded, it would then be necessary to remove it from the tree so as not to repeat traversal of the same leaf.
Is my assumption correct, or is there another way (without including member-data such as the 'level' of the node) to go about such a process?
Thanks for any help.

SoftSprocket · 05-16-2015, 10:37 AM

Generally when you traverse a tree you follow a pattern and that is how you know where to go. Another method is to maintain a stack that holds next information as required.

For a binary tree The Art of Computer Programming gives the traversal patterns listed here: http://webdocs.cs.ualberta.ca/~holte...traversal.html
Another look at it: http://www.geeksforgeeks.org/618/

atlantis43 · 05-16-2015, 11:07 AM

thanks for nice concise link which explains the process.

sundialsvcs · 05-18-2015, 08:28 AM

Exactly, the purpose of a Huffman tree is to allow you to efficiently obtain the shortest-possible bit vector that can encode that particular character. It is a remarkably elegant solution to a problem that was once regarded as intractable.

atlantis43 · 05-19-2015, 12:24 PM

Quote:

Originally Posted by sundialsvcs

Exactly, the purpose of a Huffman tree is to allow you to efficiently obtain the shortest-possible bit vector that can encode that particular character. It is a remarkably elegant solution to a problem that was once regarded as intractable.

Still haven't figured out suitable recursive code for writing the 0's & 1's, but sooner or later I'll get it. Trying to modify some code for 'printing paths' for success.