Thread: binary tree start

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.