binary tree token problem

Hi there... I've got a question about tokenizing strings...

I'm attempting to write a program that inputs a sentence from the user, tokenizes it and then hands the words to a binary search tree. I am using 'strtok' to to tokenize the sentence so the original is in a char format. I can print the individual tokens using a pointer and everything works great until I hand the tokens to the tree insert function. It appears that the program only hands off the first character of each word instead of the whole token. I get warnings that the individual first letters are dups (which is a check in the insertNode function template) so I think the function call to insertNode might be the culprit although I can't figure out a way to hand the tokens off any other way (I tried several).

Here is the pertinent code (I omitted the header files because I suspect the problem is in the function call ):

Code:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;
using std::fixed;

#include <cstring>  // prototype for strtok

#include "tree.h"  // Tree class definition

int main()
{
   Tree< char > charTree;  // create Tree
    char sentence[150];
    char *tokenPtr;
	
    cout << "Enter a sentence (150 characters max):\n";

   cin.getline( sentence, 150, '\n' );


    cout << "The string to be tokenized is:\n" << sentence
        << "\n\nThe tokens are:\n\n";

    // begin tokenization of sentence
    tokenPtr = strtok( sentence, " " );

    // continue tokenizing sentence until tokenPtr becomes NULL
    while ( tokenPtr != NULL ) {
	charTree.insertNode( *tokenPtr );
	cout << tokenPtr << '\n';
        tokenPtr = strtok( NULL, " " );  // get next token 
 
    } // end while

    cout << "\nPreorder traversal\n";
    charTree.preOrderTraversal();

    cout << "\nInorder traversal\n";
    charTree.inOrderTraversal();

    cout << "\nPostorder traversal\n";
    charTree.postOrderTraversal();

    cout << endl;

    return 0;

} // end main

The assignment suggested to use the strtok function so I assumed that this would be the easiest way to accomplish the tokenization of the sentence. I checked many of the previous binary tree threads here but could not find anything that seemed similar to this particular problem. I'm probably missing something obvious but I can seem to figure out why the whole word is not getting passed to the function...

Any assistance would be appreciated. Thanks...

Have you Goooooooooogled?

"c++ std::string"
"c++ std::stringstream"

strtok() is just soooooooooo old-school.

Don't intermix C and C++ code -- you'll scare people, and one day your poor compiler will freak out.

>strtok() is just soooooooooo old-school.
What's wrong with old-school?

>Don't intermix C and C++ code -- you'll scare people
Not the people that matter.

>and one day your poor compiler will freak out.
Doubtful.

>Here is the pertinent code
That's not all of the relevant code. If you suspect insertNode (I do too), you need to post the class definition as well as the code for insertNode. When you have a run-time bug, it helps to post enough code for us to be able to run so that we can see what you're seeing.

>charTree.insertNode( *tokenPtr );
Depending on how you've implemented insertNode, this may or may not introduce a painful dependency. tokenPtr is just that, a pointer. If sentence ever changes, the data in your tree could change as well.

jafet - I appreciate the look... The assignment suggested 'strtok' so I assumed that it was the best way to go... You know what the say about assumptions, though...

Prelude - Sorry about that... Here are the header files involved:

Code:

// Fig. 17.17: treenode.h
// Template TreeNode class definition.
#ifndef TREENODE_H
#define TREENODE_H

// forward declaration of class Tree
template< class NODETYPE > class Tree;  

template< class NODETYPE >
class TreeNode {
    friend class Tree< NODETYPE >;

public:

    // constructor
    TreeNode( const NODETYPE &d )   
        : leftPtr( 0 ), 
          data( d ), 
          rightPtr( 0 ) 
    { 
        // empty body 
   
    } // end TreeNode constructor

    // return copy of node's data
    NODETYPE getData() const 
    { 
        return data; 

    } // end getData function

private:
    TreeNode< NODETYPE > *leftPtr;  // pointer to left subtree
    NODETYPE data;
    TreeNode< NODETYPE > *rightPtr; // pointer to right subtree

}; // end class TreeNode

#endif

Code:

// Fig. 17.18: tree.h
// Template Tree class definition.
#ifndef TREE_H
#define TREE_H

#include <iostream>

using std::endl;

#include <new>
#include "treenode.h"

template< class NODETYPE >
class Tree {

public:
    Tree();
    void insertNode( const NODETYPE & );
    void preOrderTraversal() const;
    void inOrderTraversal() const;
    void postOrderTraversal() const;

private:
    TreeNode< NODETYPE > *rootPtr;

    // utility functions
    void insertNodeHelper( 
        TreeNode< NODETYPE > **, const NODETYPE & );
    void preOrderHelper( TreeNode< NODETYPE > * ) const;
    void inOrderHelper( TreeNode< NODETYPE > * ) const;
    void postOrderHelper( TreeNode< NODETYPE > * ) const;

}; // end class Tree

// constructor
template< class NODETYPE >
Tree< NODETYPE >::Tree() 
{ 
    rootPtr = 0; 

} // end Tree constructor

// insert node in Tree
template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{ 
    insertNodeHelper( &rootPtr, value ); 

} // end function insertNode

// utility function called by insertNode; receives a pointer
// to a pointer so that the function can modify pointer's value
template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( 
    TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
    // subtree is empty; create new TreeNode containing value
    if ( *ptr == 0 )  
        *ptr = new TreeNode< NODETYPE >( value );

    else  // subtree is not empty

        // data to insert is less than data in current node
        if ( value < ( *ptr )->data )
         insertNodeHelper( &( ( *ptr )->leftPtr ), value );

        else

            // data to insert is greater than data in current node
            if ( value > ( *ptr )->data )
                insertNodeHelper( &( ( *ptr )->rightPtr ), value );

            else  // duplicate data value ignored
                cout << value << " dup" << endl;

} // end function insertNodeHelper

// begin preorder traversal of Tree
template< class NODETYPE > 
void Tree< NODETYPE >::preOrderTraversal() const
{ 
    preOrderHelper( rootPtr ); 

} // end function preOrderTraversal

// utility function to perform preorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper( 
    TreeNode< NODETYPE > *ptr ) const
{
    if ( ptr != 0 ) {
        cout << ptr->data << ' ';         // process node
        preOrderHelper( ptr->leftPtr );   // go to left subtree
        preOrderHelper( ptr->rightPtr );  // go to right subtree

    } // end if

} // end function preOrderHelper

// begin inorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{ 
    inOrderHelper( rootPtr ); 

} // end function inOrderTraversal

// utility function to perform inorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper( 
    TreeNode< NODETYPE > *ptr ) const
{
    if ( ptr != 0 ) {
        inOrderHelper( ptr->leftPtr );   // go to left subtree
        cout << ptr->data << ' ';        // process node
        inOrderHelper( ptr->rightPtr );  // go to right subtree

    } // end if

} // end function inOrderHelper

// begin postorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{ 
    postOrderHelper( rootPtr ); 

} // end function postOrderTraversal

// utility function to perform postorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper( 
    TreeNode< NODETYPE > *ptr ) const
{
    if ( ptr != 0 ) {
        postOrderHelper( ptr->leftPtr );   // go to left subtree
        postOrderHelper( ptr->rightPtr );  // go to right subtree
        cout << ptr->data << ' ';          // process node

    } // end if

} // end function postOrderHelper

#endif

The program is designed to take in just one sentence, tokenize it and pass them to the insertNode function as it is tokenized for insertion into the tree...

I used:

Code:

charTree.insertNode( *tokenPtr );

...because I knew that 'strtok' alters the original string as it tokenizes so I wanted to ensure I passed each word to the function before the next tokenization pass... I'm a little shaky on pointers but I assumed '*tokenPtr' would refer to the token itself (as opposed to the address '&tokenPtr')... Apparently, it is only passing the first letter because I created a 'char' tree (I assume?) and only expects a one char input....

In the 'cout' line below it, the entire token prints to screen without difficulty so I'm sure the pointer can reference the whole word... This is making my head hurt a little! LOL!

Duh, I wasn't even close to paying attention. The problem is both the definition of your tree object and the call to insertNode. You define the template as having char as the type:

Code:

Tree< char > charTree;

Pointer to char would be better for what you're trying to do:

Code:

Tree< char* > charTree;

Ideally you would use a string object instead of pointers. Then you call insertNode with *tokenPtr, but that's dereferencing the pointer and gives you a char (the first character in the string). That's your problem. Add a * in your object definition and remove it for your call to insertNode and things should work a little better.

But now you've got that dependency issue I was talking about. In your constructor this kills you when you use pointers:

Code:

data( d ),

This copies the pointer, not the data that the pointer points to. This is where string objects really shine because otherwise you need to make a deep copy of the string where the string class does this for you.

Prelude - The sentence input is a one shot deal for this program (the tokenization process changes what is in sentence, however, right?)...

I changed the tree object definition:

Code:

Tree< char > charTree;

to:

Code:

Tree< char* > charTree;

...and the call to insertNode...

Code:

charTree.insertNode( *tokenPtr );

to:

Code:

charTree.insertNode( tokenPtr );

These changes definitely made the program insert the words into the tree now and inorder and postorder traversal seem to work fine...

On the downside, the preorder traversal seems to have stopped working... It now comes out exactly in the same order as the inorder traversal... The original setup I used seemed to work OK (with the first letters)... Is this the dependency problem you spoke of?

Is there any easy way to convert this to work with strings? I don't know of a command similar to strtok that works with strings... How would you tokenize the sentence string?

BTW - I really appreciate your help... I think I'm a little over my head here! I feel like I understand most of this but when something unexpected like this happens, I get totally confused, especially when pointers are involved...

>the tokenization process changes what is in sentence, however, right?
Yes, null characters are inserted to split the string up into multiple strings.

>the preorder traversal seems to have stopped working...
Well technically it never did work in the first place. The problem is that you're comparing pointers, not the strings that they point to. Maybe something like this instead?

Code:

template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( 
                                        TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
  // subtree is empty; create new TreeNode containing value
  if ( *ptr == 0 )  
    *ptr = new TreeNode< NODETYPE >( value );

  else  // subtree is not empty

    // data to insert is less than data in current node
    if ( strcmp ( value, ( *ptr )->data ) < 0 )
      insertNodeHelper( &( ( *ptr )->leftPtr ), value );

    else

      // data to insert is greater than data in current node
      if ( strcmp ( value, ( *ptr )->data ) > 0 )
        insertNodeHelper( &( ( *ptr )->rightPtr ), value );

      else  // duplicate data value ignored
        cout << value << " dup" << endl;

} // end function insertNodeHelper

>How would you tokenize the sentence string?
A stringstream is probably the simplest way. This has come up before, so you can probably find code (probably from me) for tokenizing a std::string.

Will adding 'strcmp' in the template still allow its use for other types of variables (i.e. - int, double, etc.)? I was shying away from messing with the templates themselves to avoid making it string-specific...

Just curious...

BTW - I am looking up the 'stringstream' posts to see if I can convert the program without giving myself an anyeurism!

I appreciate the assist...

>>Will adding 'strcmp' in the template still allow its use for other types of variables (i.e. - int, double, etc.)?

Nope. Why not use the std::string type instead? This allows you to use its overloaded operators and not have to worry about strcmp.

Otherwise, you could specialize your class to deal with char pointers (look up template specialization)

>I was shying away from messing with the templates themselves to avoid making it string-specific...
I got that impression, but if you want to use C-style strings, you're SOL. Either use std::strings, because they overload the comparison operators, or specialize your template for C-strings. If you don't like templates, you won't like specializations. Let's say something like this:

Code:

#include <iostream>
#include <ostream>
#include <sstream>
#include <string>

using namespace std;

template <typename T>
struct jsw_node {
  T data;
  jsw_node<T> *link[2];

  jsw_node ( T init )
    : data ( init )
  {
    link[0] = link[1] = 0;
  }
};

template <typename T>
class jsw_tree {
  jsw_node<T> *root;
public:
  jsw_tree()
    : root ( 0 )
  {}

  void insert ( T data );
  void preorder ( ostream& out );
  void inorder ( ostream& out );
  void postorder ( ostream& out );
private:
  jsw_node<T> *insert_r ( jsw_node<T> *tree, T data );
  void preorder_r ( jsw_node<T> *tree, ostream& out );
  void inorder_r ( jsw_node<T> *tree, ostream& out );
  void postorder_r ( jsw_node<T> *tree, ostream& out );
};

template <typename T>
void jsw_tree<T>::insert ( T data )
{
  root = insert_r ( root, data );
}

template <typename T>
void jsw_tree<T>::preorder ( ostream& out )
{
  preorder_r ( root, out );
}

template <typename T>
void jsw_tree<T>::inorder ( ostream& out )
{
  inorder_r ( root, out );
}

template <typename T>
void jsw_tree<T>::postorder ( ostream& out )
{
  postorder_r ( root, out );
}

template <typename T>
jsw_node<T> *jsw_tree<T>::insert_r ( jsw_node<T> *tree, T data )
{
  if ( tree == 0 )
    tree = new jsw_node<T> ( data );
  else {
    int dir = tree->data < data;
    tree->link[dir] = insert_r ( tree->link[dir], data );
  }

  return tree;
}

template <typename T>
void jsw_tree<T>::preorder_r ( jsw_node<T> *tree, ostream& out )
{
  if ( tree != 0 ) {
    cout<< tree->data <<' ';
    preorder_r ( tree->link[0], out );
    preorder_r ( tree->link[1], out );
  }
}

template <typename T>
void jsw_tree<T>::inorder_r ( jsw_node<T> *tree, ostream& out )
{
  if ( tree != 0 ) {
    inorder_r ( tree->link[0], out );
    cout<< tree->data <<' ';
    inorder_r ( tree->link[1], out );
  }
}

template <typename T>
void jsw_tree<T>::postorder_r ( jsw_node<T> *tree, ostream& out )
{
  if ( tree != 0 ) {
    postorder_r ( tree->link[0], out );
    postorder_r ( tree->link[1], out );
    cout<< tree->data <<' ';
  }
}

int main()
{
  string line;
  
  cout<<"Enter a sentence: ";

  if ( getline ( cin, line ) ) {
    jsw_tree<string> tree;
    stringstream ss ( line );
    string tok;

    while ( ss>> tok )
      tree.insert ( tok );

    tree.preorder ( cout );
    cout<<'\n';
    tree.inorder ( cout );
    cout<<'\n';
    tree.postorder ( cout );
    cout<<"\n\n";
  }

  jsw_tree<int> tree2;
  int data;

  // Repeat with integers
  while ( cin>> data )
    tree2.insert ( data );

  tree2.preorder ( cout );
  cout<<'\n';
  tree2.inorder ( cout );
  cout<<'\n';
  tree2.postorder ( cout );
  cout<<'\n';
}

OK... Now I feel really stupid... I'm getting a bit flustered because my assignment is due in about an hour!

I converted to strings per the suggestions here... It makes more sense to me this way, too... Pointers bad!

Code:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;
using std::fixed;

//#include <cstring>  // prototype for strtok

#include <string>
using std::string;

#include <sstream>
using std::stringstream;

#include "tree.h"  // Tree class definition

int main()
{
	Tree< string > stringTree;  // create Tree
    string sentence;
    string token;
	
    cout << "Enter a sentence:\n";

	std::getline( cin, sentence );
        cin.ignore();  // I tried this with and without... no change

    cout << "The string to be tokenized is:\n" << sentence;
    cout << "\n\nThe tokens are:\n\n";

	stringstream strm( sentence );

	while ( strm >> token ) {
		cout << token << endl;
		stringTree.insertNode( token );

	} // end while

    cout << "\nPreorder traversal\n";
    stringTree.preOrderTraversal();

    cout << "\nInorder traversal\n";
    stringTree.inOrderTraversal();

    cout << "\nPostorder traversal\n";
    stringTree.postOrderTraversal();

    cout << endl;

    return 0;

} // end main

The stringstream looks like it will do exactly what I want (I found a reference to the FAQs in another thread)... I've been through a bunch of posts and I know I'm missing something stupid... The program prompts for the sentence and when I hit 'enter', the program just stops!

I know I'm missing something simple (and probably quite stupid!)...

HELP!

Incidentally, this FAQ was excellent...
Strings to tokens

I've been playing...

The program works perfectly except I have to use 'CTL-X' and 'enter' to get the program to process the sentence... I tried changing the getline to:

std::getline( cin, sentence, '\n' );

but it still doesn't respond to the 'enter' key...

I have another question that arose after looking at this thread:
binary tree start

Under curlios' post stamped "01-01-2004, 02:34 PM", his code showed 'using std::getline'... My compiler won't accept that... It gives an error stating that getline is not a member?

C2039: 'getline' : is not a member of 'std'
C2873: 'getline' : symbol cannot be used in a using-declaration

I'm using MS VC++ Version 6.0 (Introductory Edition)

Could this be my problem?

Sorry for spamming... I just wanted to let everyone know that I have found the problem... It was Microsoft!

I found this thread in my hunt for sanity...
getline (function)???

The user with the unusual screenname 'hk_mp5kpdw' saved me from a few more gray hairs! He mentioned a bug in VC++ version 6.0 in the getline function that was exactly my problem...

getline hotfix

Since I am using a Deitel-provided Student Introductory Edition, I did not know I could use the service packs on the MS site (yes, I am a dope!) I manually corrected the 'String' file and voila! Works fine...

Thank you jafet, JaWiB and Prelude (also hk_mp5kpdw) for putting up with my ignorance... Your string suggestion works much better... I wish I had gone with it sooner (my assignment was 1/2 hr. late)... Oh well, at least I understand the concept better now... Hopefully, one of these days, I'll be able to help people out the way you all do... I really enjoy programming and I'm sure I'll be playing around with C++ long after this class is over...

Thanks again,
Steve