Traversing a Huffman Tree

[stupidenator]

Hello everyone,

I am working on an assignment which has me build a huffman tree. I am fairly confident that I have built my huffman tree correctly, but now I must get the Huffman code for the characters being encoded (I need to get the 1's and 0's). I am not sure how to do this. The tree does not seem to be in any particular order. Do I need to just try a path and if I don't find it, try the other way, or is there some other way I can use? Thanks for any help in advance.

Nick

[~s.o.s~]

Post what have you got till now. I dont properly undestand your question, but if you looking for the explanation for how to convert character to code you can look at http://en.wikipedia.org/wiki/Huffman_coding

[stupidenator]

I'm pretty sure that my tree is built correctly. I am trying to figure out how to traverse the tree. For example, if my input file consisted of "this is a test", I believe I have built the tree correctly with the characters in the leaf nodes. My problem is how I will get to those nodes. I know that a 0 represents going left and a 1 represents going right, but I am confused on how I would know whether to go left or right. My code is provided below.

[iamthwee]

So I guess we should ask do you know how to create a binary tree and do you know how to traverse the nodes in that tree.

If not, it should all be documented on the web, since it's quite a popular resource for data retrieval.

[stupidenator]

I'm fairly confident that I have created the binary tree correctly. Each individual tree has a pointer to the left and right sub trees with the exception of the leaf trees. If I have built a tree that looks like this:

6:
                      4:                                                                2:
  2:a                             2:                                   1:d                      1:g
                          1:i                1:m

I know that the code for 'm' would be 011, But I am not sure how I would determine that in code. i.e. I am not sure how I determine whether i go left or right from any given node to ensure that I am going to find the correct node I am looking for. Thanks for your help, by the way.

Nick

[iamthwee]

Well that's a big project you got there. Knowing about binary trees and how to implement the huffman algorithm. I won't pretend to know it because I don't nor do I have enough time to read up on it.

However, I believe this pdf link should be useful and likewise the following java applet.

http://cs.calvin.edu/books/c++/ds/2e/WebItems/Chapter15/Huffman.pdf

http://www.cs.sfu.ca/CC/365/li/squeeze/Huffman.html

[stupidenator]

Thank you, that did help a lot

[stupidenator]

I've got my tree printing correctly now, but I am now having a problem writing the code to traverse the tree and record the 1's and 0's to address each character in the leaf nodes. I know this should probably be a recursive function, but I cannot seem to figure it out. Any help with this would be greatly appreciated.

Thanks,

Nick

[iamthwee]

I've got my tree printing correctly now, but I am now having a problem writing the code to traverse the tree and record the 1's and 0's to address each character in the leaf nodes. I know this should probably be a recursive function, but I cannot seem to figure it out. Any help with this would be greatly appreciated.

Thanks,

Nick

Ok assuming you have your tree set up correctly, you should have something like this:- http://www.cs.uidaho.edu/~karenv/cs213/cs213.useful.pages/huffman.html

So now all you want is to find out what the binary code is for each letter. Each letter will occupy a leaf ( by definition a leaf is a node with no children). Therefore all you need is a root-to-leaf path algorithm and you will have your binary encodings!

Luckily, the following link, problem 7. shows you what the algorithm is for a root-to-leaf traversal. Look near the bottom.

http://cslibrary.stanford.edu/110/BinaryTrees.html

Job done.