Solved

Binary Search Tree Help -- urgent

Posted on 2003-11-08
17
228 Views
Last Modified: 2010-04-02
Hi, need help with this code. For some reason it doesnt insert the word and doesnt output anything. I know that nextWord is implemented correctly. what am i doing wrong . THe program is supposed to open a text file , read in word by word and the bst would keep track of the words.

bsearchTree.h
[code]
#ifndef _bsearchTree_h
#define _bsearchTree_h

#include <iostream>
#include <iomanip>
#include <string>
#include <cassert>

using namespace std;

template<class KeyType, class DataType>
struct mypair
{   KeyType key;
    DataType data;
};

template<class KeyType, class DataType>
struct node
{   mypair<KeyType, DataType> element;
    node<KeyType, DataType>* left;
    node<KeyType, DataType>* right;
};

template<class KeyType, class DataType>
class bsearchTree
{
public:
      typedef node<KeyType, DataType>* Ptr;
      bsearchTree(); //defined
          //default constructor - constructs empty tree
         
      ~bsearchTree();//defined
          //destructor. Deletes all nodes in the tree. Uses a
          //recursive private member function.
         
      bool empty();//defined
          //returns true if and only if the tree is empty
         
      long int size();//defined
          //returns the number of nodes in the tree. You cannot
          //just add a data member to the class to keep track of
          //the size. Uses a recursive private member function.
         
      long int height();//defined
          //returns the height of the tree. Uses a recursive
          //private member function. Make the height of an empty
          //tree to be -1 rather than 0 as done in the book.
         
      Ptr find(KeyType k);//defined
          //searches the tree for the key. If the key is found it
          //returns a pointer to the node containing the key;
          //otherwise it returns NULL. Uses private member function
          //findPosition.
         
      void insert(const mypair<KeyType, DataType>& p);//defined
          //checks whether a pair with the key part of p is already
          //in the tree. If so then it prints an error message and
          //does not insert the pair. If not then it inserts the pair.
          //Uses private member function findPosition.
         
      DataType& data(Ptr ptr);//defined
          //returns a referenece to the data part of the element
          //pointed to by p. This will allow the user to modify the
          //data and provides some of the functionality that a true
          //iterator would provide.
         
      void print();//defined
          //outputs the elements in sorted order of the keys, i.e.
          //inorder. Output each element on a separate line, i.e.
          //the output is done as cout<<ptr->element<<endl. Do not
          //directly output the key and data. This way the user can
          //overload the << operator for the pairs to control the output
          //however desired. Uses a recursive private member function.
               
private:
      Ptr root;
     
      void findPosition(const KeyType& k, Ptr& ptr, bool& found);
          //Searches for key, k, in the tree. If found then
          //sets ptr to point to the node containg the key and sets
          //found to true. If not found then sets ptr to point to the
          //node such that an element with this key should be inserted
          //directly below the node (if tree is empty then sets ptr
          //to NULL) and sets found to false.
         
      //other private member function prototypes
        void destroy(Ptr &);//defined
        void inorder(Ptr);//defined
        long int sizeCount(Ptr );
        long int heightCount(Ptr);//defined
        long int maxa(long int,long int);//defined
};

ostream& operator<<(ostream& os, const mypair<string, int> p)
{
      //Ouput the string and then enough space to reach column 20
    //and then output the integer in a field of width 5. This will
    //allow all the words and frequencies to line up nicely as shown
    //in the write-up.

      os<<p.data<<"                   "<<setw(5)<<p.key;
      return os;
}
   
template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::bsearchTree():
root(NULL)
{
}

template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::~bsearchTree()
{
      destroy(root);
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::destroy(node<KeyType, DataType>* &p)
{
      if(p != NULL)
      {
            destroy(p->left);
            destroy(p->right);
            delete p;
            p=NULL;
      }
}

template<class KeyType,class DataType>
bool bsearchTree<KeyType,DataType>::empty()
{
      if(root == NULL)return true;
}

template<class KeyType,class DataType>
DataType& bsearchTree<KeyType,DataType>::data(node<KeyType, DataType>* ptr)
{
      return (ptr->element).data;
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::print()
{
      inorder(root);
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::inorder(node<KeyType, DataType>* p)
{
      if(p != NULL)
      {
            inorder(p->left);
            cout<<p->element<<endl;
            inorder(p->right);
      }
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::height()
{
      return heightCount(root);
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::size()
{
      return sizeCount(root);
}

template<class KeyType,class DataType>
node<KeyType, DataType>* bsearchTree<KeyType,DataType>::find(KeyType k)
{
      node<KeyType, DataType>* ptr;
      bool found=false;

      findPosition(k,ptr,found);

      if(found == true)
      {
            ptr->element.data-=1;
            return ptr;
      }

      return NULL;
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::insert(const mypair<KeyType,DataType>& p)
{

      node<KeyType, DataType>* ptr;
      bool found=false;
      findPosition(p.key, ptr, found);

      if(found == true)cout<<"error duplicates not allowed"<<endl;//should never come here.

      if(found == false && ptr == NULL)
      {
            ptr = new node<KeyType, DataType>;
            assert(ptr != NULL);
            (ptr->element).data=1;
            (ptr->element).key=p.key;
            ptr->left=NULL;
            ptr->right=NULL;
      }
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::findPosition(const KeyType& k, node<KeyType, DataType>* &ptr, bool& found)
{
      node<KeyType, DataType>* current;//pointer to travel the tree
      node<KeyType, DataType>* follow;//pointer behind current


      if(root == NULL)//this is when the tree is empty
      {
            found=false;
            ptr=NULL;
      }

      else
      {
            current = root;

            while(current != NULL && found != true)
            {
                  follow=current;

                  if(current->element.key == k)
                  {
                        ptr=current;
                        found = true;
                        current->element.data+=1;
                  }
                  else
                        if(current->element.key > k)current=current->left;
                        else
                              current = current->right;
            }//end of while

            if(follow->element.key > k)
            {
                  ptr=follow->left;
                  found = false;
            }
            else
            {
                  ptr=follow->right;
                  found = false;
            }


      }//end of else
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::heightCount(node<KeyType, DataType>* p)
{
      if(p == NULL)return -1;

      else
            return 1 + maxa(heightCount(p->left),heightCount(p->right));
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::maxa(long int x, long int y)
{
      return(x > y ? x : y);
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::sizeCount(node<KeyType,DataType>* p)
{
      if( p == NULL)return 0;

      return sizeCount( p->left ) + 1 + sizeCount( p->right );
}


#endif
[/code]

main.cpp
[code]
#include <iostream>
#include <cmath>
#include <string>
#include <fstream>
#include <cctype>
#include <cstdlib>
#include "bsearchTree.h"

using namespace std;

void nextWord(ifstream& ifs, string& word, bool& found);


int main()
{
      char fname[20];
      ifstream infile1;
      string word;
      bool found = true;
      bool finder = false;
      char ch;
      
      bsearchTree<string, int> bst;
      mypair<string, int> bst1;
      

      cout<<"Enter File Name:";
    cin>>fname;
      infile1.open(fname);
      
      if(infile1.fail())
    {
      cerr<<"Input file " <<fname <<" does not exist"<<endl;
      cin.get(ch);
      exit(1);
    }

      while(found == true)
      {
            nextWord(infile1,word,found);

            if(found == true)
            {
                  if(bst.find(word) == NULL)
                  {
                        bst1.key=word;
                        bst1.data=1;
                        bst.insert(bst1);
                  }
            }
            word.erase(word.begin(),word.end());
            finder = false;
      }

      infile1.close();

      cout<<"number of nodes in the tree "<<bst.size()<<endl;
      cout<<"height of tree "<<bst.height()<<endl;
      long double k = bst.size();
      long double a = 2;
      cout<<"height of a perfectly balanced tree "<<floor(log(k)/log(a))<<endl;

      cout<<"Word                Frequency"<<endl;
      bst.print();

      

      system("PAUSE");
      return 0;
}


void nextWord(ifstream& ifs, string& word, bool& found)
{
        char ch=' ';
                               
                         
                 
        while( !isalpha(ch) && !ifs.fail() )
        {
                ifs.get(ch);
        }
        if(ifs.fail())found=false;
        else
                found=true;
       
        while(isalpha(ch) && !ifs.fail())
        {
                word.push_back(tolower(ch));
                ifs.get(ch);
        }
         
       
}

[/code]
0
Comment
Question by:kkool84
  • 8
  • 7
17 Comments
 
LVL 11

Expert Comment

by:bcladd
ID: 9707727
Look at your insert routine. If the element is not found in the tree then you need to insert it into the tree. Your code creates a new node with all of the appropriate data but it is pointed to by a local variable (ptr) inside insert. You need to put the new node in the appropriate position in the tree. Thus the tree IS empty.

-bcl
0
 

Author Comment

by:kkool84
ID: 9707740
I dont quite get what you mean, the ptr has the position where it should be inserted and thats why i create the new node......
0
 

Author Comment

by:kkool84
ID: 9707761
okay buy ptr has just returned from findPosition, which takes the address of the local variable ptr.
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9707764
Quoting from your insert function:

     node<KeyType, DataType>* ptr;
     bool found=false;
     findPosition(p.key, ptr, found);
     
     if(found == true)cout<<"error duplicates not allowed"<<endl;//should never come here.

     if(found == false && ptr == NULL)
     {
          ptr = new node<KeyType, DataType>;
          assert(ptr != NULL);
          (ptr->element).data=1;
          (ptr->element).key=p.key;
          ptr->left=NULL;
          ptr->right=NULL;
     }

Okay, we get into the last if statement if ptr contains NULL. You then create a new node, the address stored in ptr.
But ptr is a pointer at a node. ptr is CREATED on the calling stack when insert starts (see the variable declaration at the top of the code I quoted). It goes out of scope and is DESTROYED when the function terminates (this is the definition of local or automatic storage variables).

Your comment makes me think you wanted findPosition to find the ADDRESS of the POINTER to the node where the new data belongs. That is ptr should be a node<> ** (two stars; pointer at a pointer). That way you could return a pointer at the head pointer or a pointer at the left pointer or a pointer at the right pointer of one of the nodes in the tree.

-bcl
0
 

Author Comment

by:kkool84
ID: 9707776
the function findPosition takes the value by address and not by value, thus it shouldnt be destoyed.

the findPosition functions searches for the spot where the key should be inserted.
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9707809
This is one of the hardest parts of teaching recursive data structures using classes and limited access to the internal structure of the node. Harder without chalk but I will wave my hands as best I can:

In insert:
    ptr is on the stack and holds the address of a node (a pointer at a node).

You call findPosition with ptr. It is passed in by reference. Thus in findPosition:
    ptr is on the stack, refering to the pointer passed in as the second parameter.

This means that modifications done to ptr INSIDE findPosition are reflected in the calling parameter (ptr IN insert).  It DOES NOT mean that after COPYING the value of a pointer into ptr (that is, assigning a value to ptr) and returning from findPosition there is any relation between the two copies of the pointer value.

In particular, look at this section of code from findPosition:

     if(root == NULL)//this is when the tree is empty
     {
          found=false;
          ptr=NULL;
     }

You set ptr to NULL. There is no relationship between ptr and root after this. They both contain NULL but assinging ptr to the address 77 will not change root. Assigning the address 99 to root will have no effect on the value in ptr. They are both copies of the value 0x00000000 (assuming 32 bit addresses).

Does this make sense? What I said above about pointers to pointers would permit you to return a pointer to root rather than just something with the value NULL.

-bcl
0
 

Author Comment

by:kkool84
ID: 9708758
okay i tried making it a "pointer to a pointer" and it gave me huge errors. I dont know if this helps, but the comments in the functions say how they should work, they are the proffs instructions and i cant change them
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9708778
Okay. Great thing about computer programming is that there is almost always more than one way to do something. (The Perl programming lanuage was written around that philosophy.) Note that the problem is in your insert function (and might carry over into the findPosition function) if you are passing a reference to a pointer.

Using the header comments to determine what findPosition should do, what should insert do?

Well what can findPosition return?

found == false, ptr == NULL
found == false, ptr != NULL
found == true, ptr != NULL

Okay, what does each of these return conditions MEAN?

found == false, ptr == NULL
    The tree is empty (root == NULL)
found == false, ptr != NULL
    The tree is not empty, the sought key is not in the tree, ptr points at the PARENT that a node with that key SHOULD have
found == true, ptr != NULL
    The tree is not empty, the sought key IS in the tree, ptr points at the node with the sought key

What should insert do in each case?
The tree is empty (root == NULL)
    Create a new node and set root to point at it (actually add the new node to the tree)
The tree is not empty, the sought key is not in the tree, ptr points at the PARENT that a node with that key SHOULD have
    Create a new node and set the correct child pointer of *ptr (the item pointed to by ptr) to point at new node
The tree is not empty, the sought key IS in the tree, ptr points at the node with the sought key
    Report an error (handled)

Hope this helps. You create a new node but you probably don't want to point ptr at it (the pointer you pass into findPosition) and you want to assign root or a left/right pointer to point at the newly created node.
-bcl


0
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 

Author Comment

by:kkool84
ID: 9708805
things are making some sense right now, and i must add that thanks for helping me since you are the only one attempting to help me out. I will try ur suggestion and get back to you.
0
 

Author Comment

by:kkool84
ID: 9710602
okay modified that to this, and now it only gets 1 word in:-

#ifndef _bsearchTree_h
#define _bsearchTree_h

#include <iostream>
#include <iomanip>
#include <string>
#include <cassert>

using namespace std;





template<class KeyType, class DataType>
struct mypair
{   KeyType key;
    DataType data;
};

template<class KeyType, class DataType>
struct node
{   mypair<KeyType, DataType> element;
    node<KeyType, DataType>* left;
    node<KeyType, DataType>* right;
};

template<class KeyType, class DataType>
class bsearchTree
{
public:
      typedef node<KeyType, DataType>* Ptr;
      bsearchTree(); //defined
          //default constructor - constructs empty tree
         
      ~bsearchTree();//defined
          //destructor. Deletes all nodes in the tree. Uses a
          //recursive private member function.
         
      bool empty();//defined
          //returns true if and only if the tree is empty
         
      long int size();//defined
          //returns the number of nodes in the tree. You cannot
          //just add a data member to the class to keep track of
          //the size. Uses a recursive private member function.
         
      long int height();//defined
          //returns the height of the tree. Uses a recursive
          //private member function. Make the height of an empty
          //tree to be -1 rather than 0 as done in the book.
         
      Ptr find(KeyType k);//defined
          //searches the tree for the key. If the key is found it
          //returns a pointer to the node containing the key;
          //otherwise it returns NULL. Uses private member function
          //findPosition.
         
      void insert(const mypair<KeyType, DataType>& p);//defined
          //checks whether a pair with the key part of p is already
          //in the tree. If so then it prints an error message and
          //does not insert the pair. If not then it inserts the pair.
          //Uses private member function findPosition.
         
      DataType& data(Ptr ptr);//defined
          //returns a referenece to the data part of the element
          //pointed to by p. This will allow the user to modify the
          //data and provides some of the functionality that a true
          //iterator would provide.
         
      void print();//defined
          //outputs the elements in sorted order of the keys, i.e.
          //inorder. Output each element on a separate line, i.e.
          //the output is done as cout<<ptr->element<<endl. Do not
          //directly output the key and data. This way the user can
          //overload the << operator for the pairs to control the output
          //however desired. Uses a recursive private member function.
               
private:
      Ptr root;
     
      void findPosition(const KeyType& k, Ptr& ptr, bool& found);
          //Searches for key, k, in the tree. If found then
          //sets ptr to point to the node containg the key and sets
          //found to true. If not found then sets ptr to point to the
          //node such that an element with this key should be inserted
          //directly below the node (if tree is empty then sets ptr
          //to NULL) and sets found to false.
         
      //other private member function prototypes
        void destroy(Ptr &);//defined
        void inorder(Ptr);//defined
        long int sizeCount(Ptr );
        long int heightCount(Ptr);//defined
        long int maxa(long int,long int);//defined
};

ostream& operator<<(ostream& os, const mypair<string, int> p)
{
      //Ouput the string and then enough space to reach column 20
    //and then output the integer in a field of width 5. This will
    //allow all the words and frequencies to line up nicely as shown
    //in the write-up.

      os<<p.key<<"                 "<<setw(5)<<p.data;
      return os;
}
   
template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::bsearchTree():
root(NULL)
{
}

template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::~bsearchTree()
{
      destroy(root);
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::destroy(node<KeyType, DataType>* &p)
{
      if(p != NULL)
      {
            destroy(p->left);
            destroy(p->right);
            delete p;
            p=NULL;
      }
}

template<class KeyType,class DataType>
bool bsearchTree<KeyType,DataType>::empty()
{
      if(root == NULL)return true;
}

template<class KeyType,class DataType>
DataType& bsearchTree<KeyType,DataType>::data(node<KeyType, DataType>* ptr)
{
      return (ptr->element).data;
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::print()
{
      inorder(root);
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::inorder(node<KeyType, DataType>* p)
{
      if(p != NULL)
      {
            inorder(p->left);
            cout<<p->element<<endl;
            inorder(p->right);
      }
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::height()
{
      return heightCount(root);
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::size()
{
      return sizeCount(root);
}

template<class KeyType,class DataType>
node<KeyType, DataType>* bsearchTree<KeyType,DataType>::find(KeyType k)
{
      node<KeyType, DataType>* ptr;
      bool found;

      findPosition(k,ptr,found);

      if(found == true)
      {
            ptr->element.data--;
            return ptr;
      }
      
      return NULL;
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::insert(const mypair<KeyType,DataType>& p)
{
      node<KeyType,DataType>* ptr;
      bool found=false;

      findPosition(p.key,ptr,found);

      if(found == true)cerr<<"duplicates not allowed."<<endl;


      if(found == false && ptr == NULL)//this means tree is empty
      {
            ptr = new node<KeyType,DataType>;
            assert(ptr != NULL);
            root = ptr;
            ptr->element.key=p.key;
            ptr->element.data=1;
            ptr->left=NULL;
            ptr->right=NULL;
      }

      if(found == false && ptr != NULL)//key is unique
      {
            if(ptr->element.key > p.key)
            {
                  ptr=ptr->left;
                  ptr= new node<KeyType,DataType>;
                  assert(ptr!=NULL);
                  ptr->element.key=p.key;
                  ptr->element.data=1;
                  ptr->left=NULL;
                  ptr->right=NULL;
            }

            else
            {
                  ptr=ptr->right;
                  ptr= new node<KeyType,DataType>;
                  assert(ptr!=NULL);
                  ptr->element.key=p.key;
                  ptr->element.data=1;
                  ptr->left=NULL;
                  ptr->right=NULL;
            }
      }
      

      
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::findPosition(const KeyType& k, node<KeyType, DataType>* &ptr, bool& found)
{
      node<KeyType,DataType>* current;
      node<KeyType,DataType>* follow;

      if(root == NULL)
      {
            found = false;
            ptr=NULL;
      }

      else
      {
            current = root;

            while(current != NULL && found != true)
            {
                  follow=current;

                  if(current->element.key == k)
                  {
                        found = true;
                        current->element.data++;
                        ptr=current;
                  }

                  else
                        if(current->element.key > k)current=current->left;
                        else
                              current=current->right;
            }//end of while

            ptr=follow;
      }

      
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::heightCount(node<KeyType, DataType>* p)
{
      if(p == NULL)return -1;

      else
            return 1 + maxa(heightCount(p->left),heightCount(p->right));
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::maxa(long int x, long int y)
{
      return(x > y ? x : y);
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::sizeCount(node<KeyType,DataType>* p)
{
      if( p == NULL)return 0;

      return sizeCount( p->left ) + 1 + sizeCount( p->right );
}


#endif

0
 
LVL 11

Expert Comment

by:bcladd
ID: 9710634
In insert: DO NOT CHANGE ptr AFTER CALLING findPosition.

This means never use it on the left hand side of an assignment statement.

This also means you will need another, local, pointer variable. Call it newNodePtr or some such. You will allways assign the results of new to newNodePtr (never, ever ptr). You will then, when necessary, set root to newNodePtr (as you do with ptr in the first new block; your code works in this case but it is much, much better form to never, ever assign to ptr after calling findPosition).

Why don't you want to assign to ptr? In particular, why doesn't the following set the left pointer of the node pointed to by pointer to NULL:

    ptr = ptr->left;
    ptr = NULL;

If you go back a couple of posts, back where I was telling you you should use a pointer to a pointer (ignore that advice but read the post and see if you understand why passing ptr as a reference to a pointer didn't work with your original insert), you'll find that all the first assignment does is make a copy of the contents of ptr->left. From that point forward there is no relationship between the copy (ptr now) and the original (old ptr->left). Assignment makes a copy. So, to set ptr's left to NULL you would use one line:

    ptr->left = NULL;

How does this help you? You need (in the appropriate case) to set ptr->left to point at a newly allocated node. You can' t do it in two steps. You must assign ptr->left to point at the new node. Easiest way to do this? Have a pointer that points at the newly allocated node (newNodePtr) and assign it directly to ptr->left.

Suggestion: You would benefit from having a constructor for node<> that takes key and data values and sets the fields and NULLs the pointers. That way you can make sure the pointers are always NULL when the node begins life AND you can make your insert routine shorter and easier to read.

-bcl
0
 

Author Comment

by:kkool84
ID: 9710800
You will then, when necessary, set root to newNodePtr (as you do with ptr in the first new block

i will do that only if i were delete the node right?
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9710812
From your latest posted insert:


     if(found == false && ptr == NULL)//this means tree is empty
     {
          ptr = new node<KeyType,DataType>;
          assert(ptr != NULL);
          root = ptr;
          ptr->element.key=p.key;
          ptr->element.data=1;
          ptr->left=NULL;
          ptr->right=NULL;
     }

Notice that the first thing you do is assign to ptr (you don't want to do that; you want to assign to newNodePtr). Then, two lines below that, you assign ptr (pointer at the new node) to root. Since the pointer to the new node will be newNodePtr, you should assign newNodePtr to root, not ptr (because ptr will still be NULL because you didn't assign anything to it after the call to findPosition).

Then, similarly, you assign ptr to ptr->left (or right) and then assign ptr to a new node. Both of those will be changed to assign to newNodePtr (the new line) and then assign newNodePtr to ptr->left (or right). NOTE: The two assingnment statements are in the reverse order of what you will need.

-bcl
0
 

Author Comment

by:kkool84
ID: 9710842
okay made this change, and now it only keeps track of the first and last word

node<KeyType,DataType>* ptr;
      node<KeyType,DataType>* ptr1;
      bool found=false;

      findPosition(p.key,ptr,found);

      if(found == true)cerr<<"duplicates not allowed."<<endl;


      if(found == false && ptr == NULL)//this means tree is empty
      {
            ptr = new node<KeyType,DataType>;
            assert(ptr != NULL);
            root = ptr;
            ptr->element.key=p.key;
            ptr->element.data=1;
            ptr->left=NULL;
            ptr->right=NULL;
      
      }
      else
      {

            if(found == false && ptr != NULL)//key is unique
            {
                  if(ptr->element.key < p.key)
                  {
                        ptr1=ptr->left;
                        ptr1= new node<KeyType,DataType>;
                        assert(ptr1!=NULL);
                        ptr1->element.key=p.key;
                        ptr1->element.data=1;
                        ptr1->left=NULL;
                        ptr1->right=NULL;
                        ptr->left=ptr1;
                  }

                  else
                  {
                        ptr1=ptr->right;
                        ptr1= new node<KeyType,DataType>;
                        assert(ptr1!=NULL);
                        ptr1->element.key=p.key;
                        ptr1->element.data=1;
                        ptr1->left=NULL;
                        ptr1->right=NULL;
                        ptr->right=ptr1;
                  }
            }
      }
      
0
 
LVL 11

Accepted Solution

by:
bcladd earned 250 total points
ID: 9710947
(1) I must rant: ptr1 is a TERRIBLE name for a variable (ptr is not so great but a pointer with very limited scope is implied by a short name so it is maybe passable in this context). Why does it matter? Because the name, ptr1, gives no indication of how the variable is used. There is nothing in that name that indicates that it will point at a newly allocated node that will be added to the tree. If, a week after you turn this assignment in, you are told to modify insert to do something different (to insert into an AVL rather than a simple binary tree, for example), you'll either spend an hour remembering what ptr1 is for (okay, less in this case but it still wouldn't be instanly clear) and THEN you can start modifying the code. A little typing is worth having your code document itself.

(2) ptr1 = ptr->left (right); is redundant (next line assigns a new value to ptr1).

(3) Try printing the size of your tree after each insert. You will find that there is a problem with the size of the tree. Reading the code you have for insert, I have some confidence that it sets the right or left pointer of the node returned from findPosition correctly. You should examine that code and make sure you, too, are confident about it. That done, I would suspect that findPosition always returns NULL or the root node. Note that I say suspect: I could be wrong and the tree could get mangled somewhere else but I think it is insert where the problem happens and I think it is findPosition that is buggy.

-bcl
0
 
LVL 9

Expert Comment

by:tinchos
ID: 10248812
No comment has been added lately, so it's time to clean up this TA.
I will leave the following recommendation for this question in the Cleanup topic area:

Accept: bcladd {http:#9710947}

Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Tinchos
EE Cleanup Volunteer
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now