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

This is a discussion on Insert() function of custom binary tree template not being used correctly within the C++ Programming forums, part of the General Programming Boards category; Hi All, I am writing a program for an assignment which uses binary trees to store a text file (a ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    35

    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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,821
    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'

    Your mazePoint class needs to define operator== and operator<

    The template code needs to know how to compare two instances of your mazePoint.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    35
    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);
    //   }
    }

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    35
    Thanks tabstop, I'll keep that in mind. I wonder if you could also help me with the error I'm experiencing?

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by abrownin View Post
    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.

  7. #7
    Registered User
    Join Date
    Apr 2010
    Posts
    35
    Oh wow I'm such a dunce - thanks heaps, I'll try it when I get home and update with the result!

  8. #8
    Registered User
    Join Date
    Apr 2010
    Posts
    35
    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)
    {
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. binary tree token problem
    By OldSchool in forum C++ Programming
    Replies: 13
    Last Post: 05-28-2006, 11:42 PM
  2. error: template with C linkage
    By michaels-r in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2006, 09:11 AM
  3. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 07:39 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21