Recursive loop in Huffman Tree

Newbie & Debugging Questions
#1

recursive loops are not my strong side so i need some help:

ive made a huffman tree, which consist of two elements: leaves and nodes (leaves carry the character information, the nodes get calculated). each node has the information of which two elements came before (called leftElement and rightElement). per isLeaf() you can test if its a leaf and therefore you reached the end of a brunch.

to create an easy tree i sort the leaves at the beginning so that each huffman tree looks like this: e.g.:

10% 20% 30% 40%
A B C D
| | | | | |
Node1 | | | |
|-------------- Node2 | |
| | |
----------- Node3

hope it doesnt look too confusing =)

now my problem: i need to generate the code itself with an recursion so that every node/leaf gets walked through an for each left branch a ‘0’ is remembered and for each right branch a ‘1’. important is, that i need to save the result after a leave is reached.
i had some experiments, but no good result.

#2

hmmm, ascii format got lost, better:

zeus.fh-brandenburg.de/~huellein/tree.jpg

#3

ok, questions is still alive, but ilve noticed, that it is absolutely wrong to state, that in presorted order the tree always looks like ive displayed …

#4

I don’t think presorting will ever get you a nice neat code like you said first. It depends on the probablility of the sources.

Anyway, to recurse the tree, you need something like this:



class Node
{
    Node left;
    Node right;
    int code;
    int codeBits;

    void BuildCode( int depth, int currentCode )
    {
          code = currentCode;
          codeBits = depth;

          // Give '0' for left
          if(left != null)
              left.BuildCode(depth+1, code<<1);
          
          // Give '1' for right
          if(right != null)
              right.BuildCode(depth+1, (code<<1)+1);
     }
}

You call this by doing:

rootNode.BuildCode(0,0);

The root node will get code 0, length 0. Its ‘left’ will be 0, 1bit, the right ‘1, 1 bit’, and so on down the tree.
Decoding can be done by traversing the tree itself and taking left/right branches as the bits dictate until you reach a ‘null’ reference. Then the node you are in is the character denoted by the Huffman code.

As an aside, you can create a more efficient tree by using a state machine. I can’t remember the code but a bit of googling should find it. Its a bit harder to understand though!

Hope this helps,

  • Dom
#5

at least ive solved the problem by myself, but thx a lot for your answer. i should only test which algorithm is better :slight_smile: