Jump to content
Larry Ullman's Book Forums

A Binary Tree In C++ / In The Spirit Of Revue & Pursue


Recommended Posts

Hi,

 

On page 432, Larry mentions binary trees as good containers for data in certain circumstances.

 

Having recently created a small C program which implemented a binary tree, I am now trying to replicate that in C++.  But I am having an issue that I can't find the answer to in other forums so I'm wondering if someone can guide me in this case. 

 

Here's extracts of my code:

using std::string; // rather than using the whole std namespace

struct TreeNode
{
    // A structure of type TreeNode represents one node in a binary tree of words.
   string the_word;     // The word in this node.
   int counter;     // The count of the number of times this word was read from the input file
   TreeNode *left;     // Pointer to left subtree.
   TreeNode *right;    // Pointer to right subtree.
   TreeNode(string str = "")
     {
           // Constructor, defined for convenience.
           // Make a node containing the specified word.
        the_word = str;
        counter = 1;
        left = NULL;
        right = NULL;
     }
};  // end struct TreeNode

...... intervening code OK to here - now I want to see if the word is in the tree already
 
TreeNode * root = NULL;
TreeNode * tmp;
 
 tmp = treeContains(root, word_list[i]); // tests to see if the word is already in the tree
        std::cout << "tested word was " << word_list[i] << ", tmp is " << tmp << std::endl;
************************* tmp not being set as NULL when it should be??????????????????
        if (tmp == NULL)
         { // The word is not in the tree - add it
          treeInsert(root, word_list[i]);
          std::cout << "After inserting a node for " << word_list[i] << ", root is " << root << std::endl;
          word_count++;
      }
     else
      { // the word is in the tree - increment its counter
       tmp->counter += 1;
      }
 
....... after the search via TreeContains, tmp is not showing zero or null when it should be (it does show the correct tree node address if a match is found)
 
................
 
TreeNode * treeContains( TreeNode *root, string a_word )
{ std::cout << "Entering treeContains, root is " << root << ", a_word is " << a_word << std::endl;
   // Return the address of the node if the word is one of the words in the binary tree
   if (root == NULL)
   {
         // This sub-branch of the tree is empty, so it certainly doesn't contain a_word.
         // This will also pick up the NULL when the tree is totally empty.
      std::cout << "treeContains indicates that root is NULL for " << a_word << std::endl;  
      return NULL;     ********************************************************************************************
   }
   else if ( a_word == root->the_word )
   {
         // Yes, the word has been found in the node currently being examined.
      return root;
   }
   else
    { 
     int rc = 0;
  rc = caseicompare(a_word, root->the_word); // case insensitive string compare
  std::cout << "Comparing " << a_word << " with " << root->the_word << " in treeContains, rc is " << rc << std:: endl;
     if ( rc < 0 )
     {
          // If the word occurs, it must be in the left subtree.
        treeContains( root->left, a_word );
     }
     else
     {
          // If the word occurs, it must be in the right subtree.
       treeContains( root->right, a_word );
     }
 }
  
}  // end treeContains()

The ************** line of code above is either not returning NULL properly or I am not invoking the call to the treeContains function properly.

 

My environment is Windows 7, 64 bit with Dev-C++ as the IDE.

 

Any advice will be most appreciated and thank you in anticipation.

 

Cheers from Oz.

Link to comment
Share on other sites

OK, got it but I don't really understand why!!

 

Just had to add "return" to:

 

if ( rc < 0 )
     {
          // If the word occurs, it must be in the left subtree.
        return treeContains( root->left, a_word ); //******************added 'return' *************************************************
     }
     else
     {
          // If the word occurs, it must be in the right subtree.
       return treeContains( root->right, a_word ); //******************added 'return' *************************************************
     }

in the treeContains function.

 

If anyone can explain this to me I will appreciate it a lot.

 

Cheers from Oz.

 

P.S., the C++ binary tree works fine now :-)

Link to comment
Share on other sites

Hi Larry,

 

Thanks for getting back to me but can you please help me understand why my small code change solved my problem? Is it something to do with the way recursive routines are controlled - I believe that a 'stack' or 'heap' may be involved? Does the 'return' in the recursive call stop that new instigation of the routine from being pushed down a memory construct?

 

Any insights will be most appreciated, and thanks in anticipation.

 

Cheers.

Link to comment
Share on other sites

Sorry! Didn't realize there was an outstanding question! If those calls don't also return the invocation result, you'll never get the recursion necessary to go through all the nodes. This also results in a parallel structure, as the previous two parts of the conditional also return values. 

Link to comment
Share on other sites

 Share

×
×
  • Create New...