Huffman Code Encoding

Question

I am trying to make a Huffman tree encoding. My tree is right. I just need to figure out how to fix my recursive function in order to properly create the table. Thanks for any help I can get.

struct Code { char letter; string code; }; void createCode(BTree<Data>* root,string codeStr,vector<Code> &table) { if (root->getRightChild() == NULL && root->getLeftChild() == NULL) { Code code; code.letter = root->getData().getLetter(); code.code = codeStr; table.push_back(code); } else { createCode(root->getLeftChild(), codeStr.append("1"),table); createCode(root->getRightChild(), codeStr.append("0"),table); } } 

Answer 1

codeStr.append modifies codeStr . So, you correctly pass codeStr + "1" first recursive call, but codeStr + "10" to the second. As a result, all occurrences of "0" are added by an additional "1".

Try

 createCode(root->getLeftChild(), codeStr + "1",table); createCode(root->getRightChild(), codeStr + "0",table);