Huffman codes are all variable-length --don't tack-on extra zeros (that would change the code).
Your tree should be organized top-down with branch 0 having a summed-weight <= branch 1. (Note: the tree will have a "random" balance.) The huffman code is just a list of branches taken in the path from root (MSB) to leaf (LSB).
To decode: starting at the root node, just peel one bit at a time from the input and follow that branch until you hit a leaf node, then emit the leaf's value. The next input bit will again be from the root node.
To encode is just a tad-bit trickier: for each leaf, collect all bits back to the root, then emit them in reverse order (without adding any other bits into the output stream).
For simple bit-packing and unpacking, use a bitvector (vector<bool>). You can then push and read individual bits easily enough...
You need to keep track of how many bits you have "output" so far. When you get eight or more, output a byte.
unsigned char bits = 0; // the unwritten bits
int count = 0; // the number of unwritten bits
// Write a single bit to the output stream
void write_bit( ostream& outs, bool bit )
// Add the latest bit into our "to-output" bits
bits |= bit << count;
// Track how many we have "output" so far
if (++count < 8) return;
// If we have "output" a whole byte, then
// actually write it to the output stream
outs.put( bits );
// And reset
bits = 0;
count = 0;
// Write any left-over bits --filling
// with zeros to the even byte.
void flush_bits( ostream& outs )
if (count) outs.put( bits );
bits = 0;
count = 0;
I'm not sure how exactly you plan to avoid the STL in C++. The solution would be much nicer if you were to use it... but the above demonstrates the basics.
Notice how since we are dealing with a bit-stream, we must output bits in the same order as we get them -- meaning:
bit # byte 1 byte 2
1 .......@ ........
2 ......@x ........ These bytes are DISPLAYED
3 .....@xx ........ in the way that we humans
4 ....@xxx ........ like to read them, but what
5 ...@xxxx ........ is really IMPORTANT is that
6 ..@xxxxx ........ the bits fill in from the
7 .@xxxxxx ........ LEAST-significant bit to the
8 @xxxxxxx ........ MOST-significant bit in each byte.
9 xxxxxxxx .......@
10 xxxxxxxx ......@x
Input from the bitstream works the same way: read bits in order: first to last byte, lsb-to-msb in each byte.
public class GrossmontBank
//class variables (global - accessible throughout this class)
//scanner object to be used throughout
private static Scanner input = new Scanner(System.in);