C++

Forum

 
BST

anonomyss (32)
What I've Written, I may not change,but can someone help with the 4 functions I made comments for?
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
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
 

class BST
{
public:
    TreeNode* root;

    //member functions

    BST() {
        root = NULL;
    }

    bool isTreeEmpty()
    {
        if (root == NULL)
            return true;   //the tree is empty
        else
            return false;  //the tree is not empty
    }

    void insertNode(TreeNode* new_node) {
        if (root == NULL) {
            root = new_node;
         } //insert the root node
        else {
            TreeNode* temp = root;
            while (temp != NULL) {
                if (new_node->value == temp->value) {
                    cout << "Value Already exist," <<
                        "Insert another value!" << endl;
                    return;
                }
                else if ((new_node->value < temp->value) && (temp->left == NULL)) {
                    temp->left = new_node;  //insert value to the left
                    break;
                }
                else if (new_node->value < temp->value) {
                    temp = temp->left;
                }
                else if ((new_node->value > temp->value) && (temp->right == NULL)) {
                    temp->right = new_node;  //insert value to the right
                    break;
                }
                else {
                    temp = temp->right;
                }
            }
        }
    } //insertNode

    int heightOfTree(TreeNode* r)

    {
           //determine height of tree
           //return value to calling procedure

    }
    };


    void printPreorder(TreeNode* r) //(current node, Left, Right)
    {
          //provide the code for the preorder binary tree traversal function 
	  //print the results to the console
 
    }//printPreorder

    void printInorder(TreeNode* r) //  (Left, current node, Right)
    {
        //provide the code for the inorder binary tree traversal function 
        //print the results to the console

    } //printInorder

    void printPostorder(TreeNode* r) //left, right, root
    {
          //provide the code for the postorder binary tree traversal function 
	  //print the results to the console

    }// printPostorder

    TreeNode *searchForNode(int v) {
        if (root == NULL) {
            return root;
        }
        else {
            TreeNode* temp = root;
            while (temp != NULL) {
                if (v == temp->value) {
                    return temp;
                }
                else if (v < temp->value) {
                    temp = temp->left;
                }
                else {
                    temp = temp->right;
                }
            }
            return NULL;
        }
    }

    TreeNode* minValueNode(TreeNode* node) {
        TreeNode* current = node;
        /* loop down to find the leftmost leaf */
        while (current->left != NULL) {
            current = current->left;
        }
        return current;
    }



    TreeNode* deleteNode(TreeNode* r, int v) {
        // base case
        if (r == NULL) {
            return NULL;
        }
        // If the key to be deleted is smaller than the root's key,
        // then it lies in left subtree
        else if (v < r->value) {
            r->left = deleteNode(r->left, v);
        }
        // If the key to be deleted is greater than the root's key,
        // then it lies in right subtree
        else if (v > r->value) {
            r->right = deleteNode(r->right, v);
        }
        // if key is same as root's key, then This is the node to be deleted
        else {
            // node with only one child or no child
            if (r->left == NULL) {
                TreeNode* temp = r->right;
                delete r;
                return temp;
            }
            else if (r->right == NULL) {
                TreeNode* temp = r->left;
                delete r;
                return temp;
            }
            else {
                // node with two children: Get the inorder successor (smallest
                // in the right subtree)
                TreeNode* temp = minValueNode(r->right);
                // Copy the inorder successor's content to this node
                r->value = temp->value;
                // Delete the inorder successor
                r->right = deleteNode(r->right, temp->value);
                //deleteNode(r->right, temp->value);
            }
        }
        return r;
    }

    void readFromFileData(string thePath) {
        //Open text file and read data into an array
		//Do not change anything
        fstream myFile(thePath + "data.txt", ios_base::in);
        int nextVal;
        if (myFile.is_open()) {
            string tp;
            while (getline(myFile, tp)) {
                myFile >> nextVal;
                TreeNode* new_node = new TreeNode(); //create the instance in the heap-memory (pointer) - can be seen global and stays in memory
                new_node->value = nextVal;
                insertNode(new_node);
            }
        }
    }

}; //BST = binary search tree - nodes are added at the end of the tree (lowest level)


int main()
{
	//do not change anything in main()
    string thePath = "C:\\data\\";

    BST obj;
    int option, val;

    //Open text file and read data to test with
    fstream myFileTest(thePath + "datatest.txt", ios_base::in);
    int searchForNode1, searchForNode2, nodeToDelete;

    myFileTest >> searchForNode1 >> searchForNode2 >> nodeToDelete;

    cout << "Sorted Binary Trees!\n";

    cout << "MENU \n \n";

    do {

        cout << "\n\n";
        cout << "Choose an option, 0 to stop \n";
        cout << " 1. Read Nodes from file \n";
        cout << " 2. Search Node \n";
        cout << " 3. Delete Node \n";
        cout << " 4. Print BST values \n";
        cout << " 5. Height of tree \n";
        cout << " 6. Clear the screen \n";
        cout << " 0. Exit \n";

        cin >> option;
        TreeNode* new_node = new TreeNode(); //create the instance in the heap-memory (pointer) - can be seen global and stays in memory

        switch (option) {
        case 0:
			break;
        case 1:
            obj.readFromFileData(thePath);  //read the initial values from a text file C:\\data\\data.txt
            break;
        case 2:
            //search for first node
            cout << "SEARCH FOR " << searchForNode1 << " \n";

			val =  searchForNode1;

            new_node = obj.searchForNode(val);              //iterative search
            //new_node = obj.searchForNodeIt(obj.root,val)  //recursive search - you can decide whether you want to do an iterative or recursive search
            if (new_node != NULL) {
                cout << " Value found \n";
            }
            else {
                cout << " Value not found \n";
            }

            //search for second node
            cout << "SEARCH FOR " << searchForNode2 << " \n";
            val = searchForNode2;

            new_node = obj.searchForNode(val);              //iterative search
            //new_node = obj.searchForNodeIt(obj.root,val)  //recursive search - you may decide between iterative and recursive search
            if (new_node != NULL) {
                cout << " Value found \n";
            }
            else {
                cout << " Value not found \n";
            }
			break;

        case 3:
            cout << "DELETE NODE " << nodeToDelete << " \n"; break;
            val = nodeToDelete;
            new_node = obj.searchForNode(val);
            if (new_node != NULL) {
                obj.deleteNode(obj.root, val);
                cout << "OBJECT DELETED \n";
            }
            else {
                cout << "OBJECT NOT FOUND \n";
            }
            break;

        case 4:
            cout << "PRINT BST VALUES \n";
            //obj.print2D(obj.root, 5);

            cout << "PRINT INORDER TRAVERSAL\n";
            obj.printInorder(obj.root);
            cout << "\n\n";

            cout << "PRINT PREORDER TRAVERSAL\n";
            obj.printPreorder(obj.root);
            cout << "\n\n";

            cout << "PRINT POSTORDER TRAVERSAL \n";
            obj.printPostorder(obj.root);
            cout << "\n\n";
            break;

        case 5:
            cout << "HEIGHT OF TREE \n";
            cout << obj.heightOfTree(obj.root);
            cout << "\n\n";
            break;

        case 6:
			system("cls");
			break;

		default:
			cout << "Select from the menu \n";
			break;
        }

    } while (option != 0);

    return 0;
}
anonomyss (32)
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
 
#include <iostream>
#include <fstream>
#include <string>
#include<vector>

using namespace std;

class TreeNode
{
//keep this class as is
public:

    int value;          //key or data
    TreeNode* left;
    TreeNode* right;

    //constructors

    TreeNode() {
        value = 0;
        left = NULL;
        right = NULL;
    } //default constructor

    TreeNode(int v) {
        value = v;
        left = NULL;
        right = NULL;
    } //parametrized constructor

}; //TreeNode


the first part
seeplus (6590)
Well for traversals, you use something like in general (NOT tried)

1
2
3
4
5
6
7
 
void printInorder(TreeNode* root) {
   if (root) {
      printInorder(root->left);
      std::cout << root->data << " ";
      printInorder(root->right);
   }
}


and similar for pre-order and post-order:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void printPreorder(TreeNode *root) {
   if (root) {
      std::cout << root->data << " ";
      printPreorder(root->left);
      printPreorder(root->right);
   }
}

void printPostorder(TreeNode *root) {
  if (root) {
      printPostorder(root->left);
      printPostorder(root->right);
      std::cout << root->data << " ";
   }
}


The difference between these is the ordering of the 2 recursive calls and the std::cout statement.

Also in C++ use nullptr instead of NULL.

1
2
3
4
5
6
7
 
bool isTreeEmpty()
    {
        if (root == NULL)
            return true;   //the tree is empty
        else
            return false;  //the tree is not empty
    }


becomes:

1
2
 
bool isTreeEmpty() {
    return root == nullptr;


Re tree height. This is done similar to displaying a tree. Something like [NOT tried]:

1
2
3
 
int heightOfTree(TreeNode* root) {
    return root ? 1 + std::max(heightOfTree(root->left), heightOfTree(root->right)) : 0;
}

Last edited on
seeplus (6590)
Also note that BST should have a destructor that removes all nodes and frees all allocated memory.

There are no copy constructor and copy assignment provided. If these are not needed for this exercise then to avoid unwanted incorrect copies/assignments being done (default is a shallow copy whereas a deep copy is required) then these should be defined and marked as deleted. Something like:

1
2
3
 
BST (const BST&) = delete;
BST (BST&&) = delete;
BST& operator=(BST) = delete;


anonomyss (32)
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
 
int main()
{
	//do not change anything in main()
    string thePath = "C:\\data\\";

    BST obj;
    int option, val;

    //Open text file and read data to test with
    fstream myFileTest(thePath + "datatest.txt", ios_base::in);
    int searchForNode1, searchForNode2, nodeToDelete;

    myFileTest >> searchForNode1 >> searchForNode2 >> nodeToDelete;

    cout << "Sorted Binary Trees!\n";

    cout << "MENU \n \n";

    do {

        cout << "\n\n";
        cout << "Choose an option, 0 to stop \n";
        cout << " 1. Read Nodes from file \n";
        cout << " 2. Search Node \n";
        cout << " 3. Delete Node \n";
        cout << " 4. Print BST values \n";
        cout << " 5. Height of tree \n";
        cout << " 6. Clear the screen \n";
        cout << " 0. Exit \n";

        cin >> option;
        TreeNode* new_node = new TreeNode(); //create the instance in the heap-memory (pointer) - can be seen global and stays in memory

        switch (option) {
        case 0:
			break;
        case 1:
            obj.readFromFileData(thePath);  //read the initial values from a text file C:\\data\\data.txt
            break;
        case 2:
            //search for first node
            cout << "SEARCH FOR " << searchForNode1 << " \n";

			val =  searchForNode1;

            new_node = obj.searchForNode(val);              //iterative search
            //new_node = obj.searchForNodeIt(obj.root,val)  //recursive search - you can decide whether you want to do an iterative or recursive search
            if (new_node != NULL) {
                cout << " Value found \n";
            }
            else {
                cout << " Value not found \n";
            }

            //search for second node
            cout << "SEARCH FOR " << searchForNode2 << " \n";
            val = searchForNode2;

            new_node = obj.searchForNode(val);              //iterative search
            //new_node = obj.searchForNodeIt(obj.root,val)  //recursive search - you may decide between iterative and recursive search
            if (new_node != NULL) {
                cout << " Value found \n";
            }
            else {
                cout << " Value not found \n";
            }
			break;

        case 3:
            cout << "DELETE NODE " << nodeToDelete << " \n"; break;
            val = nodeToDelete;
            new_node = obj.searchForNode(val);
            if (new_node != NULL) {
                obj.deleteNode(obj.root, val);
                cout << "OBJECT DELETED \n";
            }
            else {
                cout << "OBJECT NOT FOUND \n";
            }
            break;

        case 4:
            cout << "PRINT BST VALUES \n";
            //obj.print2D(obj.root, 5);

            cout << "PRINT INORDER TRAVERSAL\n";
            obj.printInorder(obj.root);
            cout << "\n\n";

            cout << "PRINT PREORDER TRAVERSAL\n";
            obj.printPreorder(obj.root);
            cout << "\n\n";

            cout << "PRINT POSTORDER TRAVERSAL \n";
            obj.printPostorder(obj.root);
            cout << "\n\n";
            break;

        case 5:
            cout << "HEIGHT OF TREE \n";
            cout << obj.heightOfTree(obj.root);
            cout << "\n\n";
            break;

        case 6:
			system("cls");
			break;

		default:
			cout << "Select from the menu \n";
			break;
        }

    } while (option != 0);

    return 0;
}


and

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
 
class BST
{
public:
    TreeNode* root;

    //member functions

    BST() {
        root = NULL;
    }

    bool isTreeEmpty()
    {
       return root == nullptr;
    }

    void insertNode(TreeNode* new_node) {
        if (root == NULL) {
            root = new_node;
         } //insert the root node
        else {
            TreeNode* temp = root;
            while (temp != NULL) {
                if (new_node->value == temp->value) {
                    cout << "Value Already exist," <<
                        "Insert another value!" << endl;
                    return;
                }
                else if ((new_node->value < temp->value) && (temp->left == NULL)) {
                    temp->left = new_node;  //insert value to the left
                    break;
                }
                else if (new_node->value < temp->value) {
                    temp = temp->left;
                }
                else if ((new_node->value > temp->value) && (temp->right == NULL)) {
                    temp->right = new_node;  //insert value to the right
                    break;
                }
                else {
                    temp = temp->right;
                }
            }
        }
    } //insertNode

    int heightOfTree(TreeNode* root)

    {

     return root ? 1 + std::max(heightOfTree(root->left), heightOfTree(root->right)) : 0;

    }
};


Im getting an error that from the main() - Class BST has no member named 'readFromFileData'/'searchForNode'/'deleteNode'/'printInorder'/'printPreorder' etc
seeplus (6590)
Im getting an error that from the main() - Class BST has no member named 'readFromFileData'/'searchForNode'/'deleteNode'/'printInorder'/'printPreorder' etc


For the code posted just above, this is correct as the class BST now doesn't contain these functions. The original posted code did, however....
anonomyss (32)
Alright I've fixed that now I got 3 errors,

insertNode was not declared in this scope

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void readFromFileData(string thePath) {
        //Open text file and read data into an array
		//Do not change anything
        fstream myFile(thePath + "data.txt", ios_base::in);
        int nextVal;
        if (myFile.is_open()) {
            string tp;
            while (getline(myFile, tp)) {
                myFile >> nextVal;
                TreeNode* new_node = new TreeNode(); //create the instance in the heap-memory (pointer) - can be seen global and stays in memory
                new_node->value = nextVal;
                insertNode(new_node);
            }
        }
    }

};


Root was not declared in this scope

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
TreeNode *searchForNode(int v) {
        if (root == NULL) {
            return root;
        }
        else {
            TreeNode* temp = root;
            while (temp != NULL) {
                if (v == temp->value) {
                    return temp;
                }
                else if (v < temp->value) {
                    temp = temp->left;
                }
                else {
                    temp = temp->right;
                }
            }
            return NULL;
        }
    }


and expected declaration before '}' token

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
 
class BST
{
public:
    TreeNode* root;

    //member functions

    BST() {
        root = NULL;
    }

    bool isTreeEmpty()
    {
        return root = nullptr;
    }

    void insertNode(TreeNode* new_node) {
        if (root == NULL) {
            root = new_node;
         } //insert the root node
        else {
            TreeNode* temp = root;
            while (temp != NULL) {
                if (new_node->value == temp->value) {
                    cout << "Value Already exist," <<
                        "Insert another value!" << endl;
                    return;
                }
                else if ((new_node->value < temp->value) && (temp->left == NULL)) {
                    temp->left = new_node;  //insert value to the left
                    break;
                }
                else if (new_node->value < temp->value) {
                    temp = temp->left;
                }
                else if ((new_node->value > temp->value) && (temp->right == NULL)) {
                    temp->right = new_node;  //insert value to the right
                    break;
                }
                else {
                    temp = temp->right;
                }
            }
        }
    } //insertNode

    int heightOfTree(TreeNode* root)

    {
        return root ? 1 + std::max(heightOfTree(root->left), heightOfTree(root->right)) : 0;

    }
    };


    void printPreorder(TreeNode* root) //(current node, Left, Right)
    {
         if (root) {
      std::cout << root->data << " ";
      printPreorder(root->left);
      printPreorder(root->right);
   }

    }//printPreorder

    void printInorder(TreeNode* root) //  (Left, current node, Right)
    {
         if (root) {
      printInorder(root->left);
      std::cout << root->data << " ";
      printInorder(root->right);
   }

    } //printInorder

    void printPostorder(TreeNode* root) //left, right, root
    {
           if (root) {
      printPostorder(root->left);
      printPostorder(root->right);
      std::cout << root->data << " ";
   }

    }// printPostorder

    TreeNode *searchForNode(int v) {
        if (root == NULL) {
            return root;
        }
        else {
            TreeNode* temp = root;
            while (temp != NULL) {
                if (v == temp->value) {
                    return temp;
                }
                else if (v < temp->value) {
                    temp = temp->left;
                }
                else {
                    temp = temp->right;
                }
            }
            return NULL;
        }
    }

    TreeNode* minValueNode(TreeNode* node) {
        TreeNode* current = node;
        /* loop down to find the leftmost leaf */
        while (current->left != NULL) {
            current = current->left;
        }
        return current;
    }



    TreeNode* deleteNode(TreeNode* r, int v) {
        // base case
        if (r == NULL) {
            return NULL;
        }
        // If the key to be deleted is smaller than the root's key,
        // then it lies in left subtree
        else if (v < r->value) {
            r->left = deleteNode(r->left, v);
        }
        // If the key to be deleted is greater than the root's key,
        // then it lies in right subtree
        else if (v > r->value) {
            r->right = deleteNode(r->right, v);
        }
        // if key is same as root's key, then This is the node to be deleted
        else {
            // node with only one child or no child
            if (r->left == NULL) {
                TreeNode* temp = r->right;
                delete r;
                return temp;
            }
            else if (r->right == NULL) {
                TreeNode* temp = r->left;
                delete r;
                return temp;
            }
            else {
                // node with two children: Get the inorder successor (smallest
                // in the right subtree)
                TreeNode* temp = minValueNode(r->right);
                // Copy the inorder successor's content to this node
                r->value = temp->value;
                // Delete the inorder successor
                r->right = deleteNode(r->right, temp->value);
                //deleteNode(r->right, temp->value);
            }
        }
        return r;
    }

    void readFromFileData(string thePath) {
        //Open text file and read data into an array
		//Do not change anything
        fstream myFile(thePath + "data.txt", ios_base::in);
        int nextVal;
        if (myFile.is_open()) {
            string tp;
            while (getline(myFile, tp)) {
                myFile >> nextVal;
                TreeNode* new_node = new TreeNode(); //create the instance in the heap-memory (pointer) - can be seen global and stays in memory
                new_node->value = nextVal;
                insertNode(new_node);
            }
        }
    }

};


seeplus (6590)
Consider L53...
anonomyss (32)
Thank you seeplus, I have fixed the issues, code is working.
Topic archived. No new replies allowed.