Binary Tree Maze

Hi guys I am working on a maze project where in a binary tree maze is generated by a text file and then recursively solved. I know the theory behind recursively solving a maze and have no problems writing a program using arrays but the switch to binary trees has thrown me. Any suggestions on how I should proceed? thanks.

CPP file
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <fstream>
#include <ctype.h>

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

using namespace std;



class MazePoint
{
   private:  
      int x;
      char pointType;
   
   public:  
      int getX() const { return x; }
   
      bool operator == (const MazePoint &other) const { return (this->x == other.x); }   
      bool operator < (const MazePoint &other) const { return (this->x < other.x); }
      void setMazePoint(char ch, int i);
};

// ---------------------------------------------------------------------------------------

void MazePoint::setMazePoint(char ch, int i)
{
   pointType = ch;
   x = i;
}  


   
class Row
{
   private:   
      bintree<MazePoint> mazePoints;
      int y;
   
   public:   
      void setRow(int number) { y = number; } 
      int getY() { return y; }   
      void newRow() { y++; }  
   
      bool operator == (const Row &other) const { return (this->y == other.y); } 
      bool operator < (const Row &other) const { return (this->y < other.y); }
      void store(char ch, int i);

};


void Row::store(char ch, int i)
{
   MazePoint point;
   point.setMazePoint(ch, i);
   mazePoints.insert(point);
}


class Maze
{
   private:   
      bintree<Row> rows;
      int startX, startY;
      int finishX, finishY;
         
   public:     	
      void loadMaze(const char *file);
      void solveMaze();
      void findStart();
         
};



void Maze::loadMaze(const char *file)
{
   ifstream fin;
   
   char ch;
   Row row;
   
   row.setRow(1);
   int i = 0;
   
   fin.open(file);
   
   if(!fin)
   {
      cout << "Cannot read from " << file << "\n";
      exit(0);
   }
   
   while(fin.get(ch))
   {
      i++;
      row.store(ch, i);
      
      if(ch == '\n')
      {
         rows.insert(row);
         row.newRow();
      }
   }     
   fin.close();
}  




int main(int argc, char *argv[])
{
   string file;
   Maze theMaze;
   
   file = argv[1];
   
   if (argc !=2)
   {
      cout << "One Argument Must Be Provided\n";
      return 0;
   }
   
   theMaze.loadMaze(argv[1]);
   return(0);
}


Bintree.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#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;
	  
	  int numNodes() const
      {
	     // return a count of the number of nodes in the tree
		 // used by tree verify function
         if (root == NULL) 
         {
            return 0;
         } 
         else 
         {
            return root->numNodes();
         }
      }
      
   public:
      /*******************************************************\
         constructors & destructors
      \*******************************************************/
      
      // constructor
      bintree() : root(NULL), numItems(0) {}

      // copy constructor
      bintree(const bintree<dataType> &other) : numItems(other.numItems) 
      {
         if (other.root != NULL) 
         {
            root = new binNode<dataType>(*(other.root));
         }
         else 
         {
            root = NULL;
         }
      }
      
      // destructor
      ~bintree() 
      {
         if (root != NULL) delete root;
      }
      
      /*******************************************************\
          tree information functions
      \*******************************************************/
      
      bool empty() const 
      {
         return (numItems == 0);
      }
      
      int size() const 
      {
         // return number of nodes in the tree
		 
         return numItems;
      }
      
      int treeHeight() const 
      {
         // return the maximum height of the tree
		 
         if (root == NULL) 
         {
            return 0;
         } 
         else 
         {
            return root->getHeight();
         }
      }

      int maxTreeDepth() const 
      {
         if (root == NULL) 
         {
            return 0;
         } 
         else 
         {
            return root->maxTreeDepth();
         }
      }

      int numLeafNodes() const 
      {
         // return the number of leaf nodes in the tree
		 
         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
         
         // case of no nodes in tree
         if (numItems == 0) return 1.0;
         
         // calculate balance
         double log2numItems = log10(numItems + 1) / log10(2);
         return log2numItems / maxTreeDepth() * (numLeafNodes() * 2) / (numItems + 1); 
      }

      bool verifyTree(char *error) const
      {
	    // verify the tree is correcttly structured and nothing is broken
		 
         if (root == NULL) return true;
         else 
         {
            if (numNodes() != numItems) 
            {
               strcpy(error, "Num nodes not the same as size");
               return false;
            }
            return root->verifyTree(error);
         }
      }
      
      /*******************************************************\
         insertion, erasure and find functions
      \*******************************************************/
      
      void insert(const dataType& newData) 
      {
	     // insert the newData into the tree
		 
         if (root == NULL) 
         {
            root = new binNode<dataType>(newData);
         } 
         else 
         {
            root->insert(root, newData);
         }
         numItems++;
      }
      
      void erase(const dataType& delData) 
      {
	 // find where delData is in tree and erase it
		 
         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)
      {
         // 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);
      }
	  
	  const dataType* findConst(const dataType& findData) const
	  {
         if (root == NULL) return NULL;
         else return root->findConst(findData);
	  }

      /*******************************************************\
         overloaded operators 
      \*******************************************************/

      bintree<dataType>& operator = (const bintree<dataType> &other) 
      {
	     // make this tree equal to other. 
		 // erases the entire current contents of the tree doing this
		 
         if (root != NULL) 
         {
            delete root;
            numItems = 0;
         }
         if (other.root != NULL) 
         {
            root = new binNode<dataType>(*(other.root));
            numItems = other.numItems;
         }
         return *this;
      }


      /*******************************************************\
         print function for assignment. 
		 assumes dataType has toString() function 
      \*******************************************************/
	  
	  void print() const {
	     if (root != NULL) root->print();
      }
};

#endif
Topic archived. No new replies allowed.