Hi All,
This was in another thread but it's a completely new problem so I thought I'd create a new thread...
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 - i.e, when I try to just print the maze:
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.
Note: I am not allowed to modify the header files.
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)
{
}
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