Binary Search Tree help

[angrycoder]

I'm supposed to create a program that takes a input file and goes through it and outputs it into a index file and counts the number of times a word appeared. It is only supposed to do words that are 3 letters or longer and I can't figure out how to do it. Please help.

BST.h

#include <iostream>
#include <new>
#include <string>

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE


class BST
{
 private:
  /***** Node class *****/
  class BinNode 
  {
   public:
    string data;
	int frequency;
    BinNode * left;
    BinNode * right;

    // BinNode constructors
    // Default -- data part is default string value; both links are null.
    BinNode()
    : left(0), right(0)
    {}

    // Explicit Value -- data part contains item; both links are null.
    BinNode(string item)
    : data(item), left(0), right(0)
    {}
 
  };// end of class BinNode declaration
  BinNode* myroot;
  typedef BinNode * BinNodePointer; 
  
  /***** Private Function Members *****/
 
  void search2(const string & item, bool & found,
               BinNodePointer & locptr, BinNodePointer & parent) const;
  /*------------------------------------------------------------------------
    Locate a node containing item and its parent.
 
    Precondition:  None.
    Postcondition: locptr points to node containing item or is null if 
        not found, and parent points to its parent.#include <iostream>
  ------------------------------------------------------------------------*/
 
  void inorderAux(ostream & out, 
                  BinNodePointer subtreePtr) const;
  /*------------------------------------------------------------------------
    Inorder traversal auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Subtree with root pointed to by subtreePtr has been
        output to out.
  ------------------------------------------------------------------------*/
 
  void graphAux(ostream & out, int indent,
                      BinNodePointer subtreeRoot) const;
  /*------------------------------------------------------------------------
    Graph auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Graphical representation of subtree with root pointed 
        to by subtreePtr has been output to out, indented indent spaces.
  ------------------------------------------------------------------------*/
 
 /***** Data Members *****/
  BinNodePointer myRoot; 

 public:
  /***** Function Members *****/
  BST();
 
    
  /*------------------------------------------------------------------------
    Construct a BST object.

    Precondition:  None.
    Postcondition: An empty BST has been constructed.
   -----------------------------------------------------------------------*/
  
  bool empty() const;
  /*------------------------------------------------------------------------
    Check if BST is empty.

    Precondition:  None.
    Postcondition: Returns true if BST is empty and false otherwise.
   -----------------------------------------------------------------------*/

  bool search(const string & item) const; 
  /*------------------------------------------------------------------------
    Search the BST for item.

    Precondition:  None.
    Postcondition: Returns true if item found, and false otherwise.
   -----------------------------------------------------------------------*/
   
  void insert(const string & item);
  /*------------------------------------------------------------------------
    Insert item into BST.

    Precondition:  None.
    Postcondition: BST has been modified with item inserted at proper 
        position to maintain BST property. 
  ------------------------------------------------------------------------*/
  
  void remove(const string & item);
  /*------------------------------------------------------------------------
    Remove item from BST.

    Precondition:  None.
    Postcondition: BST has been modified with item removed (if present);
        BST property is maintained.
    Note: remove uses private auxiliary function search2() to locate 
          the node containing item and its parent.
 ------------------------------------------------------------------------*/

   void graph(ostream & out) const;
  /*------------------------------------------------------------------------
    Graphic output of BST.

    Precondition:  ostream out is open.
    Postcondition: Graphical representation of BST has been output to out.
    Note: graph() uses private auxiliary function graphAux().
 ------------------------------------------------------------------------*/
  
  void inorder(ostream & out) const;
  /*------------------------------------------------------------------------
    Inorder traversal of BST.

    Precondition:  ostream out is open.
    Postcondition: BST has been inorder traversed and values in nodes 
        have been output to out.
    Note: inorder uses private auxiliary function inorderAux().
 ------------------------------------------------------------------------*/
 

 

}; // end of class template declaration

//--- Definition of constructor

inline BST::BST()
: myRoot(0)
{}

//--- Definition of empty()

inline bool BST::empty() const
{ return myRoot == 0; }

//--- Definition of search()

bool BST::search(const string & item) const
{
   BST::BinNodePointer locptr = myRoot;
   bool found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
        locptr = locptr->left;
      else if (locptr->data < item)  // descend right
        locptr = locptr->right;
      else                           // item found
        found = true;
   }
   return found;
}

//--- Definition of insert()

inline void BST::insert(const string & item)
{
   BST::BinNodePointer 
        locptr = myRoot,   // search pointer
        parent = 0;        // pointer to parent of current node
   bool found = false;     // indicates if item already in BST
   while (!found && locptr != 0)
   {
      parent = locptr;
      if (item < locptr->data)       // descend left
         locptr = locptr->left;
      else if (locptr->data < item)  // descend right
         locptr = locptr->right;
      else                           // item found
         found = true;
   }
   if (!found)
   {                                 // construct node containing item
      locptr = new(nothrow) BST::BinNode(item); 
        
      if (locptr == 0)	
      {
        cerr << "*** Out of memory -- terminating program ***\n";
	exit(1);
      }

      if (parent == 0)               // empty tree
         myRoot = locptr;
      else if (item < parent->data )  // insert to left of parent
         parent->left = locptr;
      else                           // insert to right of parent
         parent->right = locptr;
   }
   
}

//--- Definition of remove()

void BST::remove(const string & item)
{
   bool found;                      // signals if item is found
   BST::BinNodePointer 
      x,                            // points to node to be deleted
      parent;                       //    "    " parent of x and xSucc
   search2(item, found, x, parent);

   if (!found)
   {
      cout << "Item not in the BST\n";
      return;
   }
   //else
   if (x->left != 0 && x->right != 0)
   {                                // node has 2 children
      // Find x's inorder successor and its parent
      BST::BinNodePointer xSucc = x->right;
      parent = x;
      while (xSucc->left != 0)       // descend left
      {
         parent = xSucc;
         xSucc = xSucc->left;
      }

     // Move contents of xSucc to x and change x 
     // to point to successor, which will be removed.
     x->data = xSucc->data;
     x = xSucc;
   } // end if node has 2 children

   // Now proceed with case where node has 0 or 2 child
   BST::BinNodePointer 
      subtree = x->left;             // pointer to a subtree of x
   if (subtree == 0)
      subtree = x->right;
   if (parent == 0)                  // root being removed
      myRoot = subtree;
   else if (parent->left == x)       // left child of parent
      parent->left = subtree; 
   else                              // right child of parent
      parent->right = subtree;
   delete x;
}

//--- Definition of graph()

inline void BST::graph(ostream & out) const
{ graphAux(out, 0, myRoot); }

//--- Definition of search2()

void BST::search2(const string & item, bool & found,
                            BinNodePointer & locptr, 
                            BinNodePointer & parent) const
{
   locptr = myRoot;
   parent = 0;
   found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
      {
         parent = locptr;
         locptr = locptr->left;
      }
      else if (locptr->data < item)  // descend right
      {
         parent = locptr;
         locptr = locptr->right;
      }
      else                           // item found
         found = true;
   }
}


//--- Definition of graphAux()
#include <iomanip>


void BST::graphAux(ostream & out, int indent, 
                             BinNodePointer subtreeRoot) const
{
  if (subtreeRoot != 0)
    {
      graphAux(out, indent + 8, subtreeRoot->right);
      out << setw(indent) << " " << subtreeRoot->data << endl;
      graphAux(out, indent + 8, subtreeRoot->left);
    }
}

//--- Definition of inorder()

inline void BST::inorder(ostream & out) const
{ 
   inorderAux(out, myRoot); 
}

//--- Definition of inorderAux()

void BST::inorderAux(ostream & out, 
                               BinNodePointer subtreeRoot) const
{
   if (subtreeRoot != 0)
   {
      inorderAux(out, subtreeRoot->left);    // L operation
      out << subtreeRoot->data << "  ";      // V operation
      inorderAux(out, subtreeRoot->right);   // R operation
   }
}




#endif

BST.cpp

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>
using namespace std;

#include "BST.h"



int main( int argc, char *argv)
{
    BST b;
    int ch,tmp,tmp1;
	ifstream inFile;
	string temp;
	
   
	
	inFile.open("prog4example.in");
	
	if(!inFile)
   {
      cerr << "Unable to open file datafile.txt" <<endl;
	  exit(1);
	}
	
	
	while (!inFile.eof())
	{
	inFile >> temp;
	b.insert(temp);
	
	
	
	}
   
   
   inFile.close();
	
	b.inorder(cout);
	
   
    
}

[VernonDozier]

I am looking for something in the code somewhere along the lines of:

if (/* node is found */)
{
    // increment node.frequency
}

I see nowhere where frequency is used at all. Your insertion process should be something like this:

1. Search the tree for a word.
2. If the word exists in the tree, do not create a new node. Increase the existing node's frequency by 1.
3. If the word does not exist in the tree, create a new node where the data element is the word and the frequency element is 1.

[Lerner]

What's the question? You're more likely to get a meaningful response if you don't wait for somebody to download your program and try to compile/run it.

A quick look at insert() suggests that you aren't screening item to be sure it has more than 2 letters in it and I don't see where you increment the counter in parent if item is found in the tree nor do I see where you give the counter in locptr a value as you insert lockptr into the tree if item isn't found in the tree. The latter could be done by the nondefault constructor or during the insertion, depending how you set things up.

However, without knowing what problems you are encountering that discussion may not be worth a hill of beans.

Edit: didn't rescan the thread before posting. Sorry for basically duplicating the post by VernonDozier, though I did add the scan for word length before searching the tree comment to the discussion.