Thread: Insert() function of custom binary tree template not being used correctly

Hi All,

I am writing a program for an assignment which uses binary trees to store a text file (a kind of maze):
1) Create a maze object which contains a binary tree of rows
2) Create a row object which contains a binary tree of maze points and a y value
3) Create a maze point object which contains a char attribute and an x value

This way, I should be able to traverse the file as if it was a 2D-Array, I think. I then have to run tests on it and print it out. But I am getting an error before I can even get as far as to run tests:

Code:

binnode.h: In member function 'void binNode<dataType>::insert(const dataType&) [with dataType = mazePoint]':
bintree.h:99:   instantiated from 'void bintree<dataType>::insert(const dataType&) [with dataType = mazePoint]'
assign3.cpp:82:   instantiated from here
binnode.h:58: error: no match for 'operator==' in '((binNode<mazePoint>*)this)->binNode<mazePoint>::nodeData == dataItem'
binnode.h:62: error: no match for 'operator<' in 'dataItem < ((binNode<mazePoint>*)this)->binNode<mazePoint>::nodeData'
binnode.h: In member function 'void binNode<dataType>::insert(const dataType&) [with dataType = mazeRow]':
bintree.h:99:   instantiated from 'void bintree<dataType>::insert(const dataType&) [with dataType = mazeRow]'
assign3.cpp:129:   instantiated from here
binnode.h:58: error: no match for 'operator==' in '((binNode<mazeRow>*)this)->binNode<mazeRow>::nodeData == dataItem'
binnode.h:62: error: no match for 'operator<' in 'dataItem < ((binNode<mazeRow>*)this)->binNode<mazeRow>::nodeData'

Here is my code so far below. The cpp file uses bintree.h and binnode.h, but note that I am not allowed to modify the header files.

assign2.cpp:

Code:

#include <iostream>
#include <fstream>
#include <ctype.h>
#include <cstdlib>

#include "bintree.h"
#include "binnode.h"

using namespace std;

class mazePoint
{
   private:
   
   int x;
   char point_type;
      
   public:   
   
   mazePoint();
   void setMazePoint(char point, int i);
   int get_potision();
};

class mazeRow
{
   private:
   
   bintree<mazePoint> points;
   int y;
      
   public:   
   
   mazeRow();
   void setMazeRow(int row_number);   
   void store_points(char ch, int i);
   int get_size();
   void new_row();
   void clear();
};

void load_maze(bintree<mazeRow> &maze, string arg);

int main (int argc, char *argv[]) 
{
   bintree<mazeRow> maze;
   
   //Make sure a maze file was provided   
   if (argc != 2) 
   {
      cout << "Must supply 1 argument to this program\n";
      return 0; 
   }     
   
   //Load and test the maze  
   load_maze(maze, argv[1]);
    
   //If load successful, calculate and print solution  
//   find_solution(maze);
//   print_solution(maze);
   
   //Cleanup
//   clear_rows(maze_rows);

   return 0; 
}

void mazeRow::setMazeRow(int row_number)
{
   y = row_number;
}

int mazeRow::get_size()
{
   return points.size();
}

void mazeRow::store_points(char ch, int i)
{
   mazePoint point;
   point.setMazePoint(ch, i);
   points.insert(point);
}

void mazeRow::new_row()
{
   y++;
}

void mazePoint::setMazePoint(char point, int i)
{
   point_type = point;
   x=i;
}

int mazePoint::get_potision()
{
   return x;
}

void load_maze(bintree<mazeRow> &maze, string arg) 
{
   string filein;
   
   mazeRow row;
   row.setMazeRow(1);
   
   ifstream fin;
   char ch;
   int i = 0;
  
   filein = arg;
  
   //open stream to filein
   fin.open(filein.c_str());
   if (!fin) 
   {
      cerr << "Unable to load maze " << filein << " \n";
      exit(0); 
   }
  
   while (!fin.eof()) 
   {
      fin.get(ch);
      i++;
      row.store_points(ch, i);
      if(ch == '\n') 
      {         
         maze.insert(row);
         row.new_row();
      }
   }
  
   fin.close();      
         
   //Run tests on the maze to make sure it is valid  
//   if(test_maze(maze) == 0)
//   {
//      cout << "Unable to load maze " << filein << " \n";
//      exit(0);
//   }
}

bintree.h:

Code:

#ifndef BINTREE_H_
#define BINTREE_H_

#include <stdexcept>
#include <math.h>

#include "binnode.h"

/********************************************************\
   template class for a binary tree
\********************************************************/
      

template <typename dataType> class bintree
{  
   private:
      binNode<dataType> *root;
      int numItems;
      
   public:
      /*******************************************************\
         constructors & destructors
      \*******************************************************/
      
      // constructor
      bintree() : root(NULL), numItems(0) {}
      
      // destructor
      ~bintree() {
         if (root != NULL) delete root;
      }
      
      /*******************************************************\
         misc functions
      \*******************************************************/
      
      bool empty() const {
         return (numItems == NULL);
      }
      
      int size() const {
         return numItems;
      }
      
      int numNodes() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->numNodes();
         }
      }
      
      int maxTreeDepth() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->maxTreeDepth();
         }
      }
      
      int numLeafNodes() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->numLeafNodes();
         }
      }
      
      double balance() const {
         // Returns a measure of how balanced a tree is.
         // A value of 1 is a prefectly balanced tree.
         // The closer to 0 the value is the more unbalanced
         // the tree.
         // A value < 0.5 indicates a tree that is seriously unbalanced
         
         if (numItems == 0) return 1.0;
         else return root->balance();
      }
      
      void rebalance() {
         // Rebalance tree using the AVL algorithm
         // While this does not guarantee a perfectly balanced tree
         // it does make it mostly balanced by guranteeing that the diference
         // in depth between every right and left subtree is at most 1
         
         if (root != NULL) {
            while (root->rebalance(root));
         }
      }
      
      /*******************************************************\
         insertion and erasure functions
      \*******************************************************/
      
      void insert(const dataType& newData) {
         if (root == NULL) {
            root = new binNode<dataType>(newData);
         } else {
            root->insert(newData);
         }
         numItems++;
      }
      
      void erase(const dataType& delData) {
      
         if (root == NULL) {
            throw std::invalid_argument("data does not exist in tree to erase");
         }
         
         root->erase(&root, delData);
         
         numItems--;
      }
      
      dataType* find(const dataType &findData) const {
         // this function looks for findData in the tree.
	 // If it finds the data it will return the address of the data in the tree
	 // otherwise it will return NULL
         if (root == NULL) return NULL;
         else return root->find(findData);
      }
	  
      /*******************************************************\
         print function for assignment. 
         assumes dataType has print() function 
      \*******************************************************/
	  
      void print() const {
          if (root != NULL) root->print();
      }
};

#endif

binnode.h:

Code:

#ifndef BINNODE_H
#define BINNODE_H

#include <math.h>
#include <iostream> 

/********************************************************\
   template node class for binary tree
\********************************************************/

template <typename dataType> class binNode 
{
   private:
      dataType nodeData;
      binNode<dataType> *left, *right;
      
      void deleteNode(binNode<dataType> **root) {
         if (left == NULL && right == NULL) {
            // leaf node
            *root = NULL;
         } else if (left == NULL) {
            // right branch but no left branch
            *root = right;
         } else if (right == NULL) {
            // left branch but no right branch
            *root = left;
         } else {
            // has left and right branch
            binNode<dataType> *temp = right;
            // find left most node of right branch
            while (temp->left != NULL) temp = temp->left;
            // attach left branch to left side of right branch
            temp->left = left;
            // make root point to right branch
            *root = right;
         }
         left = NULL;
         right = NULL;
         delete (this); 
      }
           
   public:
      // constructors
      binNode() : left(NULL), right(NULL) {
      }
   
      binNode(const dataType& dataItem) :
         nodeData(dataItem), left(NULL), right(NULL) {
      }
   
      // destructor
      ~binNode() {
         if (left != NULL) delete left;
         if (right != NULL) delete right;
      }
   
      void insert(const dataType& dataItem) {
         if (nodeData == dataItem) {
            throw std::invalid_argument("dataItem already in tree");
         }
      
         if (dataItem < nodeData) {
            if (left == NULL) {
               left = new binNode(dataItem);
            } else {
               left->insert(dataItem);
            }
         } else {
            if (right == NULL) {
               right = new binNode(dataItem);
            } else {
               right->insert(dataItem);
            }
         }
      }
      
      void erase(binNode<dataType> **root, const dataType &delData) {
         if (delData == nodeData) {
            deleteNode(root);
         } else {
            if (delData < nodeData) {
               if (left == NULL) {
                  throw std::invalid_argument("delItem not in tree");
               } else {
                  left->erase(&left, delData);
               }
            } else {
               if (right == NULL) {
                  throw std::invalid_argument("delItem not in tree");
               } else {
                  right->erase(&right, delData);
               }
            }
         }
      }
      
      dataType* find(const dataType &findData) {
         if (findData == nodeData) {
            return &nodeData;
         } else if (findData < nodeData) {
            if (left == NULL) return NULL;
            else return left->find(findData);
         } else {
            if (right == NULL) return NULL;
            else return right->find(findData);
         }
      }


      
      bool rebalance(binNode<dataType>* &root) {
         // rebalance the subtrees hanging from this node
         int rnodes=0, lnodes=0, nodes, dif;
         bool rotate = false;
            
         if (left != NULL) {
            if (left->rebalance(left)) rotate = true;
            lnodes = left->numNodes();
         }
         if (right != NULL) {
            if (right->rebalance(right)) rotate = true;
            rnodes = right->numNodes();
         }
         
         if (rnodes > lnodes) {
            dif = rnodes - lnodes;
            // work out node difference if we rotate anticlockwise
            rnodes = 0;
            if (right != NULL && right->right != NULL) rnodes = right->right->numNodes(); 
            nodes = 0;
            if (right != NULL && right->left != NULL) nodes = right->left->numNodes();
            lnodes = 1 + lnodes + nodes;
            if (abs(lnodes - rnodes) < dif) {
               // rotate anticlockwise
               root = right;
               right = right->left;
               root->left = this;
               rotate = true;
            }
         }
         else if (lnodes > rnodes) {
            // work out node difference if we rotate clockwise
            dif = lnodes - rnodes;
            lnodes = 0;
            if (left != NULL && left->left != NULL) lnodes = left->left->numNodes();
            nodes = 0;
            if (left != NULL && left->right != NULL) nodes = left->right->numNodes();
            rnodes = 1 + rnodes + nodes;
            if (abs(lnodes - rnodes) < dif) {
               // rotate clockwise
               root = left;
               left = left->right;
               root->right = this;
               rotate = true;
            }
         }
         return rotate;
      }

      double balance() const {
         int lheight = 0, rheight = 0, dif;
         double bal = 1.0;

         if (left != NULL) {
            lheight = left->maxTreeDepth();
            bal *= sqrt(left->balance());
         }
         if (right != NULL) {
            rheight = right->maxTreeDepth();
            bal *= sqrt(right->balance());
         }

         dif = abs(lheight - rheight);
         if (dif <= 1) return bal;
         else return bal / log(dif);
      }
      
      // tree statistic functions
      int maxTreeDepth() const {
         int rdepth = 0, ldepth = 0;
         
         if (left != NULL) ldepth = left->maxTreeDepth();
         if (right != NULL) rdepth = right->maxTreeDepth();
         
         if (ldepth > rdepth) return 1 + ldepth;
         else return 1 + rdepth;
      }
      
      int numNodes() const {
         int size = 1;
         
         if (left != NULL) size += left->numNodes();
         if (right != NULL) size += right->numNodes();
         
         return size;
      }
	  
	  void print() const {
	     if (left != NULL) left->print();
		 std::cout << nodeData.toString() << "\n";
		 if (right != NULL) right->print();
      }
      
      int numLeafNodes() const {
         if (left == NULL && right == NULL) return 1;
         
         int numLeaf = 0;
         if (left != NULL) numLeaf += left->numLeafNodes();
         if (right != NULL) numLeaf += right->numLeafNodes();
         return numLeaf;
      }
      
      // overloaded dereference operator
      const dataType& operator * () const {
         return nodeData;
      }
};

#endif

Hi,

Thanks for advice! I think I successfully overloaded the operators, so it can compile. However, running the code produces the following error:

Code:

terminate called after throwing an instance of 'std::invalid_argument'
  what():  dataItem already in tree
Abort - core dumped

Clearly I'm having trouble inserting an object into the tree. I put some couts into the code to see what it gets up to. It seems to be faltering at the line "points.insert(point);" in the mazeRow's store_points function. Could you please shed some light onto what (I assume fundamental) rule I must be breaking here?

Here is my updated cpp file:

Code:

#include <iostream>
#include <fstream>
#include <ctype.h>
#include <cstdlib>

#include "bintree.h"
#include "binnode.h"

using namespace std;

class mazePoint
{
   private:
   
   int x;
   char point_type;
      
   public:   
   
   void set_maze_point(char point, int i); 
   bool operator!=(const mazePoint &other) const;
   bool operator==(const mazePoint &other) const;
   bool operator<(const mazePoint &other) const;
};

class mazeRow
{
   private:
   
   bintree<mazePoint> points;
   int y;
      
   public:   
   
   void set_maze_row(int row_number);   
   void store_points(char ch, int i);
   int get_size();
   void new_row();
   void clear();
   bool operator!=(const mazeRow &other) const;
   bool operator==(const mazeRow &other) const;
   bool operator<(const mazeRow &other) const;
};

void load_maze(bintree<mazeRow> &maze, string arg);

int main (int argc, char *argv[]) 
{
   bintree<mazeRow> maze;
   
   //Make sure a maze file was provided   
   if (argc != 2) 
   {
      cout << "Must supply 1 argument to this program\n";
      return 0; 
   }     
   
   //Load and test the maze  
   load_maze(maze, argv[1]);
    
   //If load successful, calculate and print solution  
//   find_solution(maze);
//   print_solution(maze);
   
   //Cleanup
//   clear_rows(maze_rows);

   return 0; 
}

void mazeRow::set_maze_row(int row_number)
{
   y = row_number;
}

int mazeRow::get_size()
{
   return points.size();
}

void mazeRow::store_points(char ch, int i)
{
   cout << "Store Step 1\n";
   mazePoint point;   
   cout << "Store Step 2\n";
   point.set_maze_point(ch, i);
   cout << "Store Step 3\n";                  //ran through steps 1 - 3 twice
   points.insert(point);                           //must have faltered here when inserting a second point
}

void mazeRow::new_row()
{
   y++;
}

void mazePoint::set_maze_point(char point, int i)
{
   point_type = point;
   x=i;
}

bool mazeRow::operator==(const mazeRow &other) const
{
   return(this->y == other.y);
}

bool mazePoint::operator==(const mazePoint &other) const 
{
   return(this->point_type == other.point_type);
}

bool mazePoint::operator<(const mazePoint &other) const
{
   return(this->point_type < other.point_type);
}

bool mazeRow::operator<(const mazeRow &other) const
{
   return(this->y < other.y);
}

void load_maze(bintree<mazeRow> &maze, string arg) 
{
   string filein;
   
   mazeRow row;
   row.set_maze_row(1);
   
   ifstream fin;
   char ch;
   int i = 0;
  
   filein = arg;
  
   //open stream to filein
   fin.open(filein.c_str());
   if (!fin) 
   {
      cerr << "Unable to load maze " << filein << " \n";
      exit(0); 
   }
  
   while (!fin.eof()) 
   {
      cout << "Step 1\n";
      fin.get(ch);
      cout << "Step 2\n";
      i++;
      cout << "Step 3\n";                 //ran through steps 1 - 3 twice
      row.store_points(ch, i);
      cout << "Step 4\n";                 //did not get up to this step
      if(ch == '\n') 
      {         
         cout << "Step 5\n";
         maze.insert(row);
         cout << "Step 6\n";
         row.new_row();
      }
   }
  
   fin.close();      
         
   //Run tests on the maze to make sure it is valid  
//   if(test_maze(maze) == 0)
//   {
//      cout << "Unable to load maze " << filein << " \n";
//      exit(0);
//   }
}

Your operator only checks the char value and not the int value when comparing two mazePoints. So even if i is different, two objects with the same ch will be considered "the same". If that's not what you want, then you need to rewrite your operator< to look at both the char and the int.

Thanks tabstop, I'll keep that in mind. I wonder if you could also help me with the error I'm experiencing?

Originally Posted by abrownin

Thanks tabstop, I'll keep that in mind. I wonder if you could also help me with the error I'm experiencing?

That is the error you're experiencing. Read the error/exception message again:

Code:

dataItem already in tree

If you don't write operator== or operator< in a meaningful way, then your bintree cannot put things in the proper places and, in this case, can't tell the difference between two different points.

Oh wow I'm such a dunce - thanks heaps, I'll try it when I get home and update with the result!

Thanks tabstop, that totally worked, now I'm working on being able to print the "maze". I've been struggling with it all night, but I'm receiving this error:

Code:

binnode.h: In member function 'void binNode<dataType>::print() const [with dataType = mazePoint]':
bintree.h:129:   instantiated from 'void bintree<dataType>::print() const [with dataType = mazePoint]'
assign3.cpp:126:   instantiated from here
binnode.h:200: error: 'const class mazePoint' has no member named 'toString'

Here's my latest cpp code: I tried including string.h, but that didn't work. I gave the class a toString function, but it wasn't happy with that either; there were more errors.

Code:

#include <iostream>
#include <fstream>
#include <ctype.h>
#include <cstdlib>
#include <string.h>

#include "bintree.h"
#include "binnode.h"

using namespace std;

class mazePoint
{
   private:
   
   int x;
   char point_type;
      
   public:   
   
   void set_maze_point(char point, int i);
   void print();
   //const string toString();
   bool operator!=(const mazePoint &other) const;
   bool operator==(const mazePoint &other) const;
   bool operator<(const mazePoint &other) const;
};

class mazeRow
{
   private:
   
   bintree<mazePoint> points;
   int y;
      
   public:   
   
   void set_maze_row(int row_number);   
   void store_points(char ch, int i);
   int get_size();
   void new_row();
   void print();
   void clear();
   bool operator!=(const mazeRow &other) const;
   bool operator==(const mazeRow &other) const;
   bool operator<(const mazeRow &other) const;
};

void load_maze(bintree<mazeRow> &maze, string arg);
void print_maze(bintree<mazeRow> &maze);

int main (int argc, char *argv[]) 
{
   bintree<mazeRow> maze;
   
   //Make sure a maze file was provided   
   if (argc != 2) 
   {
      cout << "Must supply 1 argument to this program\n";
      return 0; 
   }     
   
   //Load and test the maze  
   load_maze(maze, argv[1]);
    
   //If load successful, calculate and print solution  
//   find_solution(maze);
//   print_solution(maze);
   
   //Cleanup
//   clear_rows(maze_rows);

   return 0; 
}

void mazeRow::set_maze_row(int row_number)
{
   y = row_number;
}

int mazeRow::get_size()
{
   return points.size();
}

void mazeRow::store_points(char ch, int i)
{
   mazePoint point;
   point.set_maze_point(ch, i);
   points.insert(point);
}

void mazeRow::new_row()
{
   y++;
}

void mazePoint::set_maze_point(char point, int i)
{
   point_type = point;
   x=i;
}

bool mazeRow::operator==(const mazeRow &other) const
{
   return(this->y == other.y);
}

bool mazePoint::operator==(const mazePoint &other) const 
{
   return(this->x == other.x);
}

bool mazePoint::operator<(const mazePoint &other) const
{
   return(this->x < other.x);
}

bool mazeRow::operator<(const mazeRow &other) const
{
   return(this->y < other.y);
}

void mazeRow::print()
{
   points.print();
}

void mazePoint::print()
{
   cout << point_type;
}

/*const mazePoint::string toString()
{
   stringstream ss;
   string s;
   ss << point_type;
   ss >> s;
}*/

void load_maze(bintree<mazeRow> &maze, string arg) 
{
   string filein;
   
   mazeRow row;
   row.set_maze_row(1);
   
   ifstream fin;
   char ch;
   int i = 0;
  
   filein = arg;
  
   //open stream to filein
   fin.open(filein.c_str());
   if (!fin) 
   {
      cerr << "Unable to load maze " << filein << " \n";
      exit(0); 
   }
  
   while (!fin.eof()) 
   {
      fin.get(ch);
      i++;
      row.store_points(ch, i);
      if(ch == '\n') 
      {         
         maze.insert(row);
         row.new_row();
      }
   }
  
   fin.close();      
         
   //Print the maze (temp test)
   print_maze(maze);
   
   row.print();
   
   //Run tests on the maze to make sure it is valid  
//   if(test_maze(maze) == 0)
//   {
//      cout << "Unable to load maze " << filein << " \n";
//      exit(0);
//   }
}

void print_maze(bintree<mazeRow> &maze)
{
}