Search the Community

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.

Hi Larry, As per your "Tips" on page 351, I found the binary tree suggestion in the 4th bullet point a really good one to get a better understanding of memory management as well as using recursion in C. Thanks for the suggestion. My little program reads in a text file with some words in it, parses out the words and then adds them to a binary tree stored in alphabetic word order. If the word is already in the tree, it adds to a counter of that word; if it is not in the tree it adds it and sets the count for that word to one. At the end of the file, the program prints out the words in the tree in alphabetic order plus the word counts and then deletes all the nodes of the tree. I found this exercise to be a great one in the spirit of 'revue and pursue'. Cheers from Oz.