binary tree start

Here is the start of the code I have been working on implementing a binary tree. It is just a beginning, and preludes post about binary trees makes me want to change the implementation a bit. I am getting a simple syntax error that has me baffeld also any comments on this beginning code are welcome.

Code:

//binarytree.cc  uses struct, simple function to seperate
//               sentence into words in a binary tree
//               uses inordertraversal to display sorted words


#include <iostream>
using std::cout;
using std::cin;
using std::endl;

#include <string>
using std::string;

struct tree_node
{
  string word;
  int count;
  tree_node* left;
  tree_node* right;
};

// takes a sentence a builds a binary tree constructed from the words
void buildtree(tree_node*,string);
void insert_node(tree_node**, string);

int main(int argc, char * argv[])
{
  
  string sentence;
  tree_node* root;               // top of binary tree

  cout << "Enter a sentence press enter when done." << endl;
  getline(cin,sentence);

  buildtree(root,sentence);
};

void buildtree(tree_node * base, string wordlist)
{
  //delims holds charachters used to seperate words froms sentence
  const string delims(" \t");

  int count = 0;// word count
  
  string::size_type begIdx, endIdx;// indices of single word
    
  //search for beginning of first word
  begIdx = wordlist.find_first_not_of(delims);

  //while beginning of word found loop
  while (begIdx != string::npos){
    
    //search for end of actual word
    endIdx = wordlist.find_first_of(delims, begIdx);
    
    if (endIdx == string::npos){
      //end of word is end of line
      endIdx = wordlist.length();
    }
    
    insert_node(&base,wordlist.substr(begIdx,endIdx));
   }
}

void insert_node(tree_node **ptrnode, string word)
{
  // test to see if node has been initialized or is null
  if (*ptrnode==0)
    *ptrnode = new tree_node{word,1,0,0};// syntax error here before {
  else
    //has been initialized so 
    //insert into left branch if less than parent value
    if (word<((*ptrnode)->word))
      insert_node( &((*ptrnode)->left),word,count);
    else
      //values in right branches are greater than values in parent node
      if (word>((*ptrnode)->word))
	insert_node( &((*ptrnode)->right),word,count);
      else
	//duplicate word so just increase count
	++((*ptrnode)->count);
}

binarytree.cc:69: error: syntax error before `{' token

What works with static initialization doesn't work work with dynamic initialization.
What you need is a constructor for tree_node like so:

Code:

struct tree_node
{
  string word;
  int count;
  tree_node* left;
  tree_node* right;

  tree_node(const string &wd, int cnt, tree_node *l, tree_node *r)
      : word(wd), count(cnt), left(l), right(r) {}
};

Then change your curlies to parenthesis to invoke the constructor via the call to new.

You'll also find that you need "using std::getline;", main() doesn't return a value, count is undeclared in insert_node(), you're calling insert_node() with 2 parameters in some spots and 3 parameters in others, and root is uninitialized in main().

Didn't look at the code for correctness - but you should be on your way to testing what you have done so far.

gg

I fixed many of the errors you pointed out.
This is the code. Do I need to initialize the root node in main. I intended build tree to imediately initialize the root node as it will be null initialy.

Code:

//binarytree.cc  uses struct, simple function to seperate
//               sentence into words in a binary tree
//               uses inordertraversal to display sorted words


#include <iostream>
using std::cout;
using std::cin;
using std::endl;

#include <string>
using std::string;

struct tree_node
{
  string word;
  int count;
  tree_node* left;
  tree_node* right;
  
  tree_node(const string wd,int cnt,tree_node * lft, tree_node* rght)
    :word(wd), count(cnt), left(lft), right(rght){};

};

// takes a sentence a builds a binary tree constructed from the words
void buildtree(tree_node*,string);
void insert_node(tree_node**, string);

int main(int argc, char * argv[])
{
  
  string sentence;
  tree_node* root;               // top of binary tree

  cout << "Enter a sentence press enter when done." << endl;
  getline(cin,sentence);

  buildtree(root,sentence);
  
  return 0;
};

void buildtree(tree_node * base, string wordlist)
{
  //delims holds charachters used to seperate words froms sentence
  const string delims(" \t");
    
  string::size_type begIdx, endIdx;// indices of single word
    
  //search for beginning of first word
  begIdx = wordlist.find_first_not_of(delims);

  //while beginning of word found loop
  while (begIdx != string::npos){
    
    //search for end of actual word
    endIdx = wordlist.find_first_of(delims, begIdx);
    
    if (endIdx == string::npos){
      //end of word is end of line
      endIdx = wordlist.length();
    }
    
    insert_node(&base,wordlist.substr(begIdx,endIdx));
   }
}

void insert_node(tree_node **ptrnode, string word)
{
  // test to see if node has been initialized or is null
  if (*ptrnode==0)
    *ptrnode = new tree_node(word,1,NULL,NULL);
  else
    //has been initialized so 
    //insert into left branch if less than parent value
    if (word<((*ptrnode)->word))
      insert_node( &((*ptrnode)->left),word);
    else
      //values in right branches are greater than values in parent node
      if (word>((*ptrnode)->word))
	insert_node( &((*ptrnode)->right),word);
      else
	//duplicate word so just increase count
	++((*ptrnode)->count);
}

btw the code now compiles I get a segmentation fault when executing is this because I have not yet implemented my delete routine or is there some other problem in the code I have so far?
btw thanks for the response Codeplug.

>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;
}

I fixed the problems with the tokenizer, although I did not use your class (That will come in the future). I had forgotten to update the begIdx as your hint led me to discover. Also I found a bug in my use of substr.

I learned that pointer act like any var as far as initialization goes so set it to NULL, thanks.

Had to think about using a pointer to pointer a bit for the build routine. Still a little shakey here but assume passing the address to a pointer would only allow me to manipulate the address of the root and not the contents. I avoided using non constant refrences in my argument list following Storstups advice to use pointer instead, although I understand this is moot because you where using a pointer to a refrence. For my own better understanding I stuck with pure pointers. It remindes me of calculas and second dirivatives.

Implemented your traversal routine which I understand ok, but need to continue reading your other post now. Anyhow now I can take the next step and free the memory. My idea is to use post order traversal in deleting the nodes. I haven't read any further about deletion and will expirment with my method before I do, so no hints please anyhow here is the working code so far thanks for the help!

Code:

//binarytree.cc  uses struct, simple function to seperate
//               sentence into words in a binary tree
//               uses inordertraversal to display sorted words


#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::getline;

#include <string>
using std::string;

struct tree_node
{
  string word;
  int count;
  tree_node* left;
  tree_node* right;
  
  tree_node(const string wd,int cnt,tree_node * lft, tree_node* rght)
    :word(wd), count(cnt), left(lft), right(rght){};

};


// takes a sentence a builds a binary tree constructed from the words
void buildtree(tree_node**,string);
void insert_node(tree_node**, string);


//inorder traversal provided by prelude (www.cprogramming.com)
//produces an ascending sorted list by processing left nodes
//ie finding smallest values, then right nodes next value greater
//than parent node and returning (recursively processing all nodes)

void in_order_traverse(tree_node* root)
{
  if (root == 0)
    return;
  in_order_traverse(root->left);
  cout << root->word << endl;
  in_order_traverse(root->right);
}

int main(int argc, char * argv[])
{
  
  string sentence;
  tree_node* root=0;               // top of binary tree
  

  cout << "Enter a sentence press enter when done." << endl;
  getline(cin,sentence);

  buildtree(&root,sentence);
  in_order_traverse(root);

  return 0;
};

void buildtree(tree_node **base, string wordlist)
{
  //delims holds charachters used to seperate words froms sentence
  const string delims(" \t.,");
    
  string::size_type begIdx, endIdx;// indices of single word
    
  //search for beginning of first word
  begIdx = wordlist.find_first_not_of(delims);

  //while beginning of word found loop
  while (begIdx != string::npos){
    
    //search for end of actual word
    endIdx = wordlist.find_first_of(delims, begIdx);
    
    if (endIdx == string::npos){
      //end of word is end of line
      endIdx = wordlist.length();
    }
    insert_node(&(*base),wordlist.substr(begIdx,endIdx-begIdx));
    //cout << wordlist.substr(begIdx,endIdx-begIdx)<<endl;
    begIdx = wordlist.find_first_not_of(delims,endIdx);
 
  }
}

void insert_node(tree_node **ptrnode, string word)
{
  // null node pointer indicates need to create new node
  // otherwise words less than parent value inserted into left branch
  // and words greater than parent are inserted into right branch
  // matching words update count (number of a given 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);
}

>My idea is to use post order traversal in deleting the nodes.
Postorder traversal is by far the easiest way to release the memory for every item in a tree. As an added challenge later, try writing it without using recursion. In my tutorial I meant to have that as an exercise, but apparently forgot about it.

[Note: Prelude has trouble reading, and completely missed that she actually did have that as exercise 8.]

Well I implemented the post_order_traversal
then read more of your post about traversal, breadth_first traversal was somthing new to me. I implemented a pointer to function in my traversal routines which is a good idea on your part. I read your iterative approach for depth_first traversal so it was fairly easy to do the post_order_traversal again using the iterative method. If I hadn't read quite so far it would have been more of a challenge.
Here is the code which now does everything I intended it to do. (which started with an exercise from Strostups C++ Programming Language 3rd edition)
btw I agree so far data structures are a blast.

Code:

 //binarytree.cc  uses struct, simple function to seperate
//               sentence into words in a binary tree
//               uses inordertraversal to display sorted words


#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::getline;

#include <string>
using std::string;

struct tree_node
{
  string word;
  int count;
  tree_node* left;
  tree_node* right;
  
  tree_node(const string wd,int cnt,tree_node * lft, tree_node* rght)
    :word(wd), count(cnt), left(lft), right(rght){};

};

// allows polymorphic actions to be passed to traversal routines
// for processing of data within nodes
typedef void (*fptraction)(struct tree_node *);

// takes a sentence a builds a binary tree constructed from the words
void buildtree(tree_node**,string);
void insert_node(tree_node**, string);


//inorder traversal provided by prelude (www.cprogramming.com)
//produces an ascending sorted list by processing left nodes
//ie finding smallest values, then right nodes next value greater
//than parent node and returning (recursively processing all nodes)

void in_order_traverse(tree_node* root, fptraction action)
{
  if (root == 0)
    return;
  in_order_traverse(root->left,action);
  action(root);
  in_order_traverse(root->right,action);
}

void post_order_traverse(tree_node* root,fptraction action)
{
  if (root == 0)
    return;
  post_order_traverse(root->left, action);
  post_order_traverse(root->right, action);
  //cout << root->word << endl;
  action(root);
}

void post_order_traverse_iterative(tree_node* root, fptraction action)
{
  struct tree_node *save[50];
  int top = 0;

  if (root == 0 )
    return;
  save[top++] = root;
  while ( top != 0 ) {
    root = save[--top];
    if ( root->left != NULL )
      save[top++] = root->left;
    if ( root->right != NULL )
      save[top++] = root->right;
    action( root );
  }
}

// to be used as an action for processing data  when traversing tree
void cout_word(tree_node* ptrnode)
{
  cout << ptrnode->word << endl;
}

void delete_node(tree_node * ptrnode)
{
  delete ptrnode;
}


int main(int argc, char * argv[])
{
  
  string sentence;
  tree_node* root=0;               // top of binary tree
  

  cout << "Enter a sentence press enter when done." << endl;
  getline(cin,sentence);

  buildtree(&root,sentence);
  in_order_traverse(root,&cout_word);
  //clean up nodes
  post_order_traverse(root,&cout_word);
  post_order_traverse(root,&delete_node);
  return 0;
};

void buildtree(tree_node **base, string wordlist)
{
  //delims holds charachters used to seperate words froms sentence
  const string delims(" \t.,");
    
  string::size_type begIdx, endIdx;// indices of single word
    
  //search for beginning of first word
  begIdx = wordlist.find_first_not_of(delims);

  //while beginning of word found loop
  while (begIdx != string::npos){
    
    //search for end of actual word
    endIdx = wordlist.find_first_of(delims, begIdx);
    
    if (endIdx == string::npos){
      //end of word is end of line
      endIdx = wordlist.length();
    }
    insert_node(&(*base),wordlist.substr(begIdx,endIdx-begIdx));
    //cout << wordlist.substr(begIdx,endIdx-begIdx)<<endl;
    begIdx = wordlist.find_first_not_of(delims,endIdx);
 
  }
}

void insert_node(tree_node **ptrnode, string word)
{
  // null node pointer indicates need to create new node
  // otherwise words less than parent value inserted into left branch
  // and words greater than parent are inserted into right branch
  // matching words update count (number of a given 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);
}

I'm not sure I implemented the post_order_traversal_iterative routine properly. Forgive me for my persumption. I'm currently reading more of preludes post and see there are issues with other forms of depth first traversal to be taken into account. Before I do anything else I will finish reading and digesting the rest of that post.