>I intended build tree to imediately initialize the root node as it will be null initialy.
This is fine provided root really is null. A local pointer is not initialized to null according to Standard C++, so you must do it manually. If your compiler does this for you, you still should do it manually to make your code more portable.
>is this because I have not yet implemented my delete routine or is there some other problem in the code I have so far?
It has nothing to do with a delete routine. In fact, many trees don't bother to implement deletion, or only do it in a rudamentary way such as flagging nodes as deleted instead of actually removing them. This saves the programmer of the effort of implementing difficult deletion routines.
Your code does have problems though:
>void insert_node(tree_node **ptrnode, string word)
You have the right idea passing a double pointer (though a reference to a pointer would be much cleaner), however, don't forget that buildtree is the function that calls insert_node, and buildtree only takes a single pointer. When buildtree returns, root will be whatever it was before you called the function. As such, buildtree should also take a double pointer.
The format of your insertion function is uncomfortable to read, try something like this:
Code:
void insert_node(tree_node **ptrnode, string& word)
{
if (*ptrnode==0)
*ptrnode = new tree_node(word,1,NULL,NULL);
else if (word<((*ptrnode)->word))
insert_node( &((*ptrnode)->left),word);
else if (word>((*ptrnode)->word))
insert_node( &((*ptrnode)->right),word);
else
++((*ptrnode)->count);
}
Your tokenizing code could use some work. For tree testing I changed it to this:
Code:
void buildtree(tree_node **base, string& wordlist)
{
Tokenizer t(wordlist);
while (!t.done())
insert_node(base, t.next());
}
Using the following class from my source libraries:
Code:
#include <sstream>
#include <string>
#include <vector>
class Tokenizer {
public:
explicit Tokenizer ( const std::string& s, char delim = ' ' ) throw();
explicit Tokenizer ( const std::string& s, const std::string& delim ) throw();
public:
std::string next() throw() { return !done() ? *current++ : std::string(); }
bool done() const throw() { return current == tokens.end(); }
private:
std::vector<std::string> tokens;
std::vector<std::string>::iterator current;
};
Tokenizer::Tokenizer ( const std::string& s, char delim ) throw()
{
std::istringstream grabber ( s );
std::string token;
while ( getline ( grabber, token, delim ) ) {
if ( !token.empty() )
tokens.push_back ( token );
}
current = tokens.begin();
}
Tokenizer::Tokenizer ( const std::string& s, const std::string& delim ) throw()
{
std::string token;
std::string::size_type front = 0;
std::string::size_type back = 0;
while ( true ) {
if ( back == std::string::npos )
break;
front = s.find_first_not_of ( delim, front );
if ( front == std::string::npos )
break;
back = s.find_first_of ( delim, front );
token = s.substr ( front, back - front );
tokens.push_back ( token );
front = back + delim.length();
}
current = tokens.begin();
}
If you want, you can compare your code with my constructor to see where your code might be going wrong. Here is a hint: It goes into an infinite loop using the first token. Also, compare this with your code, it implements the changes I've suggested. It also checks to make sure that all of the items were properly inserted into the tree by using an inorder traversal:
Code:
void buildtree(tree_node*&, string&);
void insert_node(tree_node*&, string&);
void traverse(tree_node* root)
{
if (root == 0)
return;
traverse(root->left);
cout << root->word << endl;
traverse(root->right);
}
int main()
{
string sentence;
tree_node* root = 0;
cout << "Enter a sentence press enter when done." << endl;
getline(cin,sentence);
buildtree(root,sentence);
// Make sure insertion worked properly
traverse(root);
return 0;
};
void buildtree(tree_node*& base, string& wordlist)
{
Tokenizer t(wordlist);
while (!t.done())
insert_node(base, t.next());
}
void insert_node(tree_node*& ptrnode, string& word)
{
if (ptrnode == 0)
ptrnode = new tree_node(word, 1, NULL, NULL);
else if (word < ptrnode->word)
insert_node(ptrnode->left, word);
else if (word > ptrnode->word)
insert_node(ptrnode->right, word);
else
++ptrnode->count;
}