samedi 29 avril 2017

Trying to Return a string(concatenated) through recursion in a binary tree

I have all but given up completely. This is part of a Huffman Code exercise using binary trees.

My Encode() function will not work because my helper CharToCode() does not work. It always returns a blank line, instead of a binary number (to signify it exact location on the tree).

CharToCode(): nonmember recursive helper function to find an encoding from the codetree.

Here is what I must accomplish:

Build a path (in string 'pathSoFar', by concatenating a 0 or 1 as appropriate) as the function traverses the tree. When a leaf node is reached, if the leaf data value is the character being encoded, return the path; otherwise, this was not the correct path and return the empty string.

Assume that the function is being called correctly in the driver (main) file and that the constructor and load functions are correct. Here is what I have:

void HuffmanTree::Encode(std::istream& messageFile, std::ostream & out)
{
   char ch;
   std::string pathSoFar;
   std::string huffman;


   while (messageFile.get(ch))
   {
      huffman = CharToCode(ch, root, pathSoFar);
      out << pathSoFar;
   }
   out << std::endl;
}

std::string CharToCode(char ch, TreeNode* localRoot, std::string pathSoFar)
{
   std::string code;
   if(localRoot->info == ch)
      return pathSoFar;
   else
   {  
      if(localRoot->left != NULL)    
         return CharToCode(ch, localRoot->left, pathSoFar+'0');
      else if(localRoot->right != NULL)
         return CharToCode(ch, localRoot->right, pathSoFar+'1'); 
   }
   return "";
}

Aucun commentaire:

Enregistrer un commentaire