Binary Tree Search & Tracking

1
votes

I have a binary tree of node containing an integer and a char. I'm working on Huffman Coding and I want to get the binary presentation of the nodes. A '0' is appended to the string for every left branching and a '1' is appended for every right branching.

I'm thinking of searching for a char but keeping track of its branches, if it's not in the left node, remove the last '0' appended to the string and go back up and check the right. This looks very tasking. Is there another way for me to keep track of the node?

EDIT: I have to use a Binary Tree.

2
c++algorithmbinary-treehuffman-code
Is my question unclear? - MosesA
Really strings? You don't want the bits as actual bits? - harold
Which one would be better/easier? - MosesA
Depends on what you want to do with them - if you're just doing this to personally inspect the results (for example if you're trying to understand how Huffman encoding works) then strings are nice. If you're going to do some actual compression with them, bits are far more useful. (otherwise you'd just end up converting the strings to bits all the time, that's just slow and pointless) - harold
Oh okay. I'm just using them to understand Huffman encoding. Thanks. - MosesA

2 Answers

2
votes

Are you talking about encoding the Huffman output?

You will want to build a table of output codes and lengths for each possible input character - don't traverse the tree on each input character.

2
votes

Sounds like a stack data structure:

You keep track of where you are in the tree by using the stack in this way:

  • path = std::stack<int>
  • move up to parent == pop()
  • move to left child == push(0)
  • move to right child == push(1)

Edit:

You may want to actually use a std::vector<int> with push_back and pop_back instead. It still behaves like a stack, but you can get the entire list of 0's and 1's at the end if you use a vector.