C++

Forum

 
Can't determine if countNodes() function is operable since retrieve() function doesn't seem to work

elsa (76)
BST.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
 
#pragma once
#include <iostream>
#include <fstream>
using namespace std;

class BST
{
private:
	int id;
	BST* left;
	BST* right;
	BST* tree;
	int value;
public:
	BST();
	~BST();
	void destroyTree(BST* tree);
	void insert(BST*& tree, int id);
	void searchToDelete(BST*& tree, int id);
	void deleteNode(BST*& tree);
	void getPredecessor(BST*& tree, int& id);
	void retrieveItem(int& id);
	void retrieve(BST* tree, int& id);
	void printInOrder(BST* tree);
	void printPreOrder(BST* tree);
	void printPostOrder(BST* tree);
	int lengthIs(BST* tree, int id, int level);
	unsigned int countNodes(BST* root);
};


BST.cpp

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
 
#include "BST.h"

BST::BST()
{
	tree = NULL;
	id = 0;
}

void BST::destroyTree(BST* tree)
{
	if (tree != NULL)
	{
		destroyTree(tree->left);
		destroyTree(tree->right);
		delete tree;
	}
}

BST::~BST()
{
	destroyTree(tree);
}

void BST::insert(BST*& tree, int id)
{
	if (tree == NULL)
	{
		tree = new BST;
		tree->right = NULL;
		tree->left = NULL;
		tree->id = id;
	}
	else if (id < tree->id)
		insert(tree->left, id);
	else
		insert(tree->right, id);
}

void BST::searchToDelete(BST*& tree, int id)
{
	if (id < tree->id)
		searchToDelete(tree->left, id);
	else if (id > tree->id)
		searchToDelete(tree->right, id);
	else
		deleteNode(tree);
}

void BST::deleteNode(BST*& tree)
{
	int id;
	BST* temp;
	temp = tree;

	if (tree->left == NULL)
	{
		tree = tree->right;
		delete temp;
	}
	else if (tree->right == NULL)
	{
		tree = tree->left;
		delete temp;
	}
	else
	{
		getPredecessor(tree->left, id);
		tree->id = id;
		deleteNode(tree->left);
	}
}

void BST::getPredecessor(BST*& tree, int& id)
{
	while (tree->right != NULL)
		tree = tree->right;
	id = tree->id;
}

void BST::retrieveItem(int& id)
{
	retrieve(tree, id);
}

void BST::retrieve(BST* tree, int& id)
{
	if (tree == NULL)
		cout << "No items in tree!\n\n";
	else if (id < tree->id)
		retrieve(tree->left, id);
	else if (id > tree->id)
		retrieve(tree->right, id);
	else
		cout << "Item not in tree!\n\n";
}

void BST::printInOrder(BST* tree)
{
	if (tree != NULL)
	{
		printInOrder(tree->left);
		cout << tree->id << " --> ";
		printInOrder(tree->right);
	}
}

void BST::printPreOrder(BST* tree)
{
	if (tree)
	{
		cout << tree->value << " ";
		printPreOrder(tree->left);
		printPreOrder(tree->right);
	}
}

void BST::printPostOrder(BST* tree)
{
	if (tree)
	{
		printPostOrder(tree->left);
		printPostOrder(tree->right);
		cout << tree->value << " ";
	}
}

int BST::lengthIs(BST* tree, int id, int level)
{
	{
		if (tree == NULL)
			return 0;

		if (tree->id == id)
			return level;

		int downlevel = lengthIs(tree->left, id, level + 1);
		if (downlevel != 0)
			return downlevel;

		downlevel = lengthIs(tree->right,
			id, level + 1);
		return downlevel;
	}
}

unsigned int BST::countNodes(BST* root)
{
	if (root == NULL)
		cout << "There are no nodes." << endl;
		return 0;

	int res = 0;
	if (root->left && root->right)
		res++;

	res += (countNodes(root->left) + countNodes(root->right));
	return res;
}


main.cpp

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
 
#include "BST.h"

int main()
{
	BST bst;
	BST* root = NULL;

	//insert
	cout << "Insert numbers\n";
	bst.insert(root, 7);
	bst.insert(root, 5);
	bst.insert(root, 9);
	bst.insert(root, 8);
	bst.insert(root, 2);
	bst.insert(root, 3);

	//print
	bst.printInOrder(root);
	cout << "\n\nDelete 8\n";
	bst.searchToDelete(root, 8);
	bst.printInOrder(root);

	//retrieve
	int id = 4;

	cout << "\n\nRetrieve 4\n";
	bst.retrieve(root, id); //retrieve function appears to treat tree as if it's null

	cout << endl << endl;

	bst.lengthIs(root, id, id); //lengthIs and countNodes functions don't seem to execute (maybe due to retrieve not working properly)

	bst.countNodes(root);

	cout << "we made it this far";

	return 0;
}
Last edited on
salem c (3700)
It seems to be working here.
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
 
$ valgrind ./a.out
==7214== Memcheck, a memory error detector
==7214== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==7214== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==7214== Command: ./a.out
==7214== 
Insert numbers
2 --> 3 --> 5 --> 7 --> 8 --> 9 --> 

Delete 8
2 --> 3 --> 5 --> 7 --> 9 --> 

Retrieve 4
No items in tree!



we made it this far==7214== 
==7214== HEAP SUMMARY:
==7214==     in use at exit: 72,904 bytes in 6 blocks
==7214==   total heap usage: 8 allocs, 2 frees, 73,968 bytes allocated
==7214== 
==7214== LEAK SUMMARY:
==7214==    definitely lost: 40 bytes in 1 blocks
==7214==    indirectly lost: 160 bytes in 4 blocks
==7214==      possibly lost: 0 bytes in 0 blocks
==7214==    still reachable: 72,704 bytes in 1 blocks
==7214==         suppressed: 0 bytes in 0 blocks
==7214== Rerun with --leak-check=full to see details of leaked memory
==7214== 
==7214== For counts of detected and suppressed errors, rerun with: -v
==7214== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Sure, there is a bit of memory leaking.

But there seems to be no out of bound memory access or indefinite recursion causing things to lock up.
dhayden (5798)
1
2
3
4
5
 
BST::BST()
{
	tree = NULL;
	id = 0;
}

You need to initialize members left, right, and tree. Actually, why do you even have member tree?

In deleteNode():
1
2
3
4
5
6
7
8
9
10
11
12
 
	temp = tree;

	if (tree->left == NULL)
	{
		tree = tree->right;
		delete temp;   // <<<<<<< deletes the input tree
	}
	else if (tree->right == NULL)
	{
		tree = tree->left;
		delete temp;    //   <<<<<<< deletes the input tree
	}


You will find the code easier if you have two classes: one for an individual node in the tree and one for the tree itself. That way you won't have to pass the tree to the tree when doing something to the tree.

Finally, consider a single search() method (it might be private):
1
2
3
 
// Find the pointer to the node that contains id, or the null pointer
// where ID should be inserted if it isn't present in the tree.
BSTNode * &search(BSTNode * &tree, int id);
Then searchToDelete and retrieve() can use search()
elsa (76)
My problem is with the countNodes() function. It doesn't seem to work. It displays nothing. How can I get around this? Is the countNodes() function correct to begin with? Also, retrieve() is not working correctly; the program outputs "No items in tree!" implying that the if-statement in the retrieve function is only executing the code that would be executed if the tree is null, which it shouldn't be.
Last edited on
dhayden (5798)
Line 150 in countNodes() isn't indented property. It looks like it's within the if, but in fact it isn't.

When retrieve finds the item, it prints "Item not in tree". When it doesn't find the item, it prints "No items in tree!" when it really means "I reached an empty leaf node without finding the item."

lengthIs() doesn't print anything and you don't print the return value.

CountNodes() shouldn't print anything. Since it's a recursive function, it doesn't know if it's printing the result of the first call or a recursive call. Just have it return the number of nodes.

In fact, most of the BST methods shouldn't print anything (except the print() methods of course). It's better to have them return a value indicating what they did and have the main() program print the results. That way you don't have to worry about recursive calls printing stuff.

Here is your code in one file with these changes. I've also added a debugPrint() method that prints the tree structure of the tree so you can tell if it's become inconsistent.
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
 
#include <iostream>
#include <fstream>
using namespace std;

class BST
{
private:
    int id;
    BST *left;
    BST *right;
    BST *tree;
    int value;
public:
      BST();
     ~BST();
    void destroyTree(BST * tree);
    void insert(BST * &tree, int id);
    void searchToDelete(BST * &tree, int id);
    void deleteNode(BST * &tree);
    void getPredecessor(BST * &tree, int &id);
    void retrieveItem(int &id);
    void retrieve(BST * tree, int &id);
    void printInOrder(BST * tree);
    void printPreOrder(BST * tree);
    void debugPrint(BST * tree, unsigned depth = 0);
    void printPostOrder(BST * tree);
    int lengthIs(BST * tree, int id, int level);
    unsigned int countNodes(BST * root);
};

BST::BST()
{
    tree = NULL;
    id = 0;
}

void
BST::destroyTree(BST * tree)
{
    if (tree != NULL) {
	destroyTree(tree->left);
	destroyTree(tree->right);
	delete tree;
    }
}

BST::~BST()
{
    destroyTree(tree);
}

void
BST::insert(BST * &tree, int id)
{
    if (tree == NULL) {
	tree = new BST;
	tree->right = NULL;
	tree->left = NULL;
	tree->id = id;
    } else if (id < tree->id)
	insert(tree->left, id);
    else
	insert(tree->right, id);
}

void
BST::searchToDelete(BST * &tree, int id)
{
    if (id < tree->id)
	searchToDelete(tree->left, id);
    else if (id > tree->id)
	searchToDelete(tree->right, id);
    else
	deleteNode(tree);
}

void
BST::deleteNode(BST * &tree)
{
    int id;
    BST *temp;
    temp = tree;

    if (tree->left == NULL) {
	tree = tree->right;
	delete temp;
    } else if (tree->right == NULL) {
	tree = tree->left;
	delete temp;
    } else {
	getPredecessor(tree->left, id);
	tree->id = id;
	deleteNode(tree->left);
    }
}

void
BST::getPredecessor(BST * &tree, int &id)
{
    while (tree->right != NULL)
	tree = tree->right;
    id = tree->id;
}

void
BST::retrieveItem(int &id)
{
    retrieve(tree, id);
}

void
BST::retrieve(BST * tree, int &id)
{
    if (tree == NULL) {
	cout << "Not found\n";
    } else if (id < tree->id)
	retrieve(tree->left, id);
    else if (id > tree->id)
	retrieve(tree->right, id);
    else
	cout << "Found " << id << " in tree.\n";
}

void
BST::debugPrint(BST * tree, unsigned depth)
{
    if (tree == NULL)
	return;

    debugPrint(tree->left, depth + 1);
    for (unsigned i = 0; i < depth; ++i) {
	cout << "   ";
    }
    cout << tree->id << '\n';
    debugPrint(tree->right, depth + 1);
}

void
BST::printInOrder(BST * tree)
{
    if (tree != NULL) {
	printInOrder(tree->left);
	cout << tree->id << " --> ";
	printInOrder(tree->right);
    }
}

void
BST::printPreOrder(BST * tree)
{
    if (tree) {
	cout << tree->value << " ";
	printPreOrder(tree->left);
	printPreOrder(tree->right);
    }
}

void
BST::printPostOrder(BST * tree)
{
    if (tree) {
	printPostOrder(tree->left);
	printPostOrder(tree->right);
	cout << tree->value << " ";
    }
}

int
BST::lengthIs(BST * tree, int id, int level)
{
    {
	if (tree == NULL)
	    return 0;

	if (tree->id == id)
	    return level;

	int downlevel = lengthIs(tree->left, id, level + 1);
	if (downlevel != 0)
	    return downlevel;

	downlevel = lengthIs(tree->right, id, level + 1);
	return downlevel;
    }
}

unsigned int
BST::countNodes(BST * root)
{
    if (root == NULL) {
	return 0;
    }
    int res = (1		// for the root node
	       + countNodes(root->left)		 // left tree
	       + countNodes(root->right));	 // right tree
    return res;
}

int
main()
{
    BST bst;
    BST *root = NULL;

    //insert
    cout << "Insert numbers\n";
    bst.insert(root, 7);
    bst.insert(root, 5);
    bst.insert(root, 9);
    bst.insert(root, 8);
    bst.insert(root, 2);
    bst.insert(root, 3);
    bst.debugPrint(root);

    //print
    // bst.printInOrder(root);
    cout << "\n\nDelete 8\n";
    bst.searchToDelete(root, 8);
    bst.debugPrint(root);
    // bst.printInOrder(root);

    //retrieve
    int id = 4;

    cout << "\n\nRetrieve 4\n";
    bst.retrieve(root, id);

    cout << endl << endl;

    cout << "Length to " << id << " is " << bst.lengthIs(root, id, 0) << '\n';

    cout << "CountNodes() returned " << bst.countNodes(root) << '\n';

    cout << "we made it this far";

    return 0;
}

Topic archived. No new replies allowed.