Thread: binary tree token problem

  1. #1
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18

    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...
    Last edited by OldSchool; 05-27-2006 at 09:51 PM.

  2. #2
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  4. #4
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18
    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!

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    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.
    My best code is written with the delete key.

  6. #6
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18
    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...

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  8. #8
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18
    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...

  9. #9
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    >>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)
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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';
    }
    My best code is written with the delete key.

  11. #11
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18
    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!
    Last edited by OldSchool; 05-28-2006 at 09:07 PM.

  12. #12
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18
    Incidentally, this FAQ was excellent...
    Strings to tokens

  13. #13
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18
    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?
    Last edited by OldSchool; 05-28-2006 at 09:44 PM.

  14. #14
    Registered User OldSchool's Avatar
    Join Date
    Apr 2006
    Location
    Virginia
    Posts
    18
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree scope? problem
    By tms43 in forum C++ Programming
    Replies: 5
    Last Post: 11-01-2006, 10:13 PM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  3. problem in storing data in a binary search tree
    By alavardi in forum C Programming
    Replies: 5
    Last Post: 02-13-2005, 03:20 PM
  4. Problem with binary search tree :(
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 05-01-2002, 10:31 PM
  5. problem in binary expression tree
    By hanij in forum C Programming
    Replies: 6
    Last Post: 04-28-2002, 08:31 AM