C++

Forum

 
Removing function that isn't properly reattaching nodes

mistabob (35)
please help! This should just be a simple algorithm error!


this is a continuation of this post: http://cplusplus.com/forum/general/87357/

This is the last problem I'm having: my removing function is removing the correct node, but is not handling the reattachment of nodes and is causing seg faults, through I believe null dereference.

Here's my 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
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
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
 
#ifndef BST_H
#define BST_H

#include "Node.h"
#include <string>
#include <iostream>
#include <iomanip>

using std::ostream;
using std::istream;
using std::setw;
using std::endl;



template <typename T>
class BST
{
public:
	enum direction {left, right, none};
int counter;
Node<T>* root;
void BSTcopy(Node<T>* &copy, Node<T>* original);
void displayHelper(ostream& out, Node<T>* node, int level, direction d);
void insertHelper(Node<T> * root, Node<T>* newNode);
int heightHelper(Node<T>* base);


BST();
BST(const BST<T> &bst);
const BST<T>& operator=(const BST<T> &bst);
~BST();
void insert(T data);
T find(T key);
T remove (T key);
void display (ostream &out);
void inorderDisplay (ostream &out);
int count();
};

template <typename T>
BST<T>::BST()
{
	root = NULL;
	counter = 0;
}

template <typename T>
void BST<T>::BSTcopy(Node<T>* &copy, Node<T>* original)
{
	if(original == NULL)
	{
		copy = NULL;
	}
	else
	{
		Node<T>* copy;
		copy->data = original->data;
		BSTcopy(copy->Left, original->getLeft());
		BSTcopy(copy->Right, original->getRight());
	}
}

template <typename T>
BST<T>::BST(const BST<T> & bst)
{
	this->BSTcopy(this->root, bst.root);
	this->counter = bst.counter ;
}

template <typename T>
BST<T>::~BST()
{
	delete root;
}


template <typename T>
int BST<T>::count()
{
	return counter;
}

template <typename T>
 void BST<T>::displayHelper( ostream& out, Node<T>* node, int level, direction d)
 {
         if ( node != NULL )
         {
                 displayHelper( out, node->getLeft(), level-1, left);
                 out << endl;
                 out << setw(5*level) <<  node->getData();
                 if ( d == right )
                 out <<  "/";// << endl;
                 else if ( d == left )
                 out <<  "\\";// << endl;
                 else
                 out <<  "-";
                 out << endl;
                 displayHelper( out, node->getRight(), level-1, right);
                 out << endl;
         }
 }

 template <typename T>
 int BST<T>::heightHelper( Node<T>* base)
 {
	 int left;
	 int right;
	 if(base == T())
	 {
		 return -1;
	 }
	 left = heightHelper(base->Left);
	 right = heightHelper(base->Right);

	 if(left > right)
	 {
		 return (left + 1);
	 }
	 else
	 {
		 return (right + 1);
	 }
 }


template <typename T>
void BST<T>::display(ostream & out)
{
	displayHelper(out, this->root, heightHelper(this->root), none);
}


template <typename T>
T BST<T>::find(T key)
{
	return (root->find(key));
}



template <typename T>
void BST<T>::inorderDisplay(ostream & out)
{
	if(root == T())
	{
		return;
	}
	inorderDisplay(root.getLeft());
	root.getData();
	inorderDisplay(root.getRight());
}

template <typename T>
void BST<T>::insertHelper(Node<T> * root, Node<T>* newNode)
{
	if(newNode->data < root->data)
	{ cout << "000";
		if(root->Left == NULL)
		{
			root->Left = newNode;
			cout << "001";
			return;
		}
		else
		{ cout << "002";
		insertHelper(root->Left, newNode);
		}
	}
	else if(newNode->data > root->data)
	{cout << "003";
		if(root->Right == NULL)
		{ cout << "004";
			root->Right = newNode;
			return;
		}
		else
		{cout << "005";
			insertHelper(root->Right, newNode);
		}
	}
}



template <typename T>
void BST<T>::insert(T data)
{
	counter++;
	if(root == NULL)
	{
		Node<T>* isempty;
		isempty = new Node<T>;
		isempty->setData(data);
		root = isempty;
	}
	 else
	{
		Node<T>* newNode;
		newNode = new Node<T>;
		newNode->setData(data);
		insertHelper(this->root, newNode);
	}
	
}


template <typename T>
const BST<T>& BST<T>::operator=(const BST<T>&bst)
{
	this->BSTcopy(this->root, bst.root);
	this->counter = bst.counter ;
}


template <typename T>
T BST<T>::remove (T key)
{
	counter--;
	bool found = 0;
	Node<T>* curr;
	Node<T>* parent;
	curr = root;

	while(curr != NULL)
	{
		if(curr->data == key)
		{
			found = 1;
			break;
		}
		else
		{
			parent = curr;
			if(key > curr->data)
			{
				curr = curr->Right;
			}
			else
			{
				curr = curr->Left;
			}
		}
	}
	
	if(!found)
	{
		return T();
	}

	if((curr->Left == NULL && curr->Right != NULL) || (curr->Left != NULL && curr->Right == NULL))
	{
		if(curr->Left == NULL && curr->Right != NULL)
		{
			if(parent->Left == curr)
			{
				parent->Left = curr->Right;
				delete curr;
				return key;
			}
			else
			{
				parent->Right = curr->Right;
				delete curr;
				return key;
			}
		}
		else
		{
			if(parent->Left == curr)
			{
				parent->Left = curr->Left;
				delete curr;
				return key;
			}
			else
			{
				parent->Right = curr->Left;
				delete curr;
				return key;
			}
		}
	}

	if(curr->Left == NULL && curr->Right == NULL)
		{
			if(parent->Left == curr)
			{
				parent->Left = NULL;
			}
			else
			{
				parent->Right == NULL;
			}
	delete curr;
	return key;
		}


	if(curr->Left != NULL && curr->Right != NULL)
	{
		Node<T>* chkr;
		chkr = curr->Right;
		if((chkr->Left == NULL) && (chkr->Right == NULL))
		{
			curr = chkr;
			delete chkr;
			curr->Right = NULL;
		}
		else
		{
			if((curr->Right)->Left != NULL)
			{
				Node<T>* lcurr;
				Node<T>* lcurrp;
				lcurrp = curr->Right;
				lcurr = (curr->Right)->Left;
				while(lcurr->Left != NULL)
				{
					lcurrp = lcurr;
					lcurr = lcurr->Left;
				}
				curr->data = lcurr->data;
				delete lcurr;
				lcurrp->Left = NULL;
				return key;
			}
			else
			{
				Node<T>* tmp;
				tmp = curr->Right;
				curr->data = tmp->data;
				curr->Right = tmp->Right;
				delete tmp;
				return key;
			}
		}
	}

}

#endif



and here's my Node.h, although I believe this to be working correctly:

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
 
#ifndef NODE_H
#define	NODE_H	


#include <iostream>
//#include "LinkedList.h"


using namespace std;

template <typename T>
class Node
{
public:
T data;
Node<T> * Left;
Node<T> * Right;
int position;
T find(T key);

	Node();
	~Node();
	Node (T newData, Node< T > *newLeft=NULL, Node<T>* newRight=NULL);
	void setData(T newdata);
	void setLeft (Node< T > *newLeft);
	void setRight (Node<T>* newRight);
	T getData ();
	Node< T > * getRight ();
	Node<T>* getLeft();

};

template <typename T>
Node<T>::Node()
{
data = T();
Left = NULL;
Right = NULL;
}

template <typename T>
Node<T>::Node(T newData, Node<T>* newLeft, Node<T>* newRight)
{
	data = newData;
	Left = newLeft;
	Right = newRight;
}

template <typename T>
T Node<T>::getData()
{
	return data;
}
template <typename T>
Node<T>* Node<T>::getLeft() 
{
	return Left;
}

template <typename T>
Node<T>* Node<T>::getRight() 
{
	return Right;
}

template <typename T>
Node<T>::~Node()
{
	delete Left;
	delete Right;
}

template <typename T>
void Node<T>::setData(T newData)
{
	data = newData;
}
template <typename T>
void Node<T>::setLeft(Node<T>* newLeft)
{
	Left = newLeft;
}

template <typename T>
void Node<T>::setRight(Node<T>* newRight)
{
	Right = newRight;
}


template <typename T>
T Node<T>::find(T key)
{
	if(this->data == key)
	{
		return key;
	}
	else if(this->Left == NULL && this->Right == NULL)
	{
		return T();
	}

	if(key > this->data)
	{
		if(this->Right == NULL)
		{
			return T();
		}
		else
		{
		 return	this->Right->find(key);
		}
	}
	else if(key < this->data)
	{
		if(this->Left == NULL)
		{
			return T();
		}
		else
		{
		return	this->Left->find(key);
		}
	}
	
}

#endif



What am I doing wrong here? This seemed simple enough, cycle to the data in question, and based on it's children, attach it's children to it's parent.
Last edited on
mistabob (35)
update: Fixed remove, but I'm STILL dereferencing a NULL pointer somewhere. Please help!

updated code:

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
 
#ifndef BST_H
#define BST_H

#include "Node.h"
#include <string>
#include <iostream>
#include <iomanip>

using std::ostream;
using std::istream;
using std::setw;
using std::endl;



template <typename T>
class BST
{
public:
	enum direction {left, right, none};
int counter;
Node<T>* root;
void BSTcopy(Node<T>* &copy, Node<T>* original);
void displayHelper(ostream& out, Node<T>* node, int level, direction d);
void insertHelper(Node<T> * root, Node<T>* newNode);
int heightHelper(Node<T>* base);
Node<T>* removeHelper(T key, Node<T>* node, T &removed);
Node<T>* removeNode(Node<T>* node);

BST();
BST(const BST<T> &bst);
const BST<T>& operator=(const BST<T> &bst);
~BST();
void insert(T data);
T find(T key);
T remove (T key);
void display (ostream &out);
void inorderDisplay (ostream &out);
int count();
};

template <typename T>
BST<T>::BST()
{
	root = NULL;
	counter = 0;
}

template <typename T>
void BST<T>::BSTcopy(Node<T>* &copy, Node<T>* original)
{
	if(original == NULL)
	{
		copy = NULL;
	}
	else
	{
		Node<T>* copy;
		copy->data = original->data;
		BSTcopy(copy->Left, original->getLeft());
		BSTcopy(copy->Right, original->getRight());
	}
}

template <typename T>
BST<T>::BST(const BST<T> & bst)
{
	this->BSTcopy(this->root, bst.root);
	this->counter = bst.counter ;
}

template <typename T>
BST<T>::~BST()
{
	delete root;
}


template <typename T>
int BST<T>::count()
{
	return counter;
}

template <typename T>
 void BST<T>::displayHelper( ostream& out, Node<T>* node, int level, direction d)
 {
         if ( node != NULL )
         {
                 displayHelper( out, node->getLeft(), level-1, left);
                 out << endl;
                 out << setw(5*level) <<  node->getData();
                 if ( d == right )
                 out <<  "/";// << endl;
                 else if ( d == left )
                 out <<  "\\";// << endl;
                 else
                 out <<  "-";
                 out << endl;
                 displayHelper( out, node->getRight(), level-1, right);
                 out << endl;
         }
 }

 template <typename T>
 int BST<T>::heightHelper( Node<T>* base)
 {
	 int left;
	 int right;
	 if(base == T())
	 {
		 return -1;
	 }
	 left = heightHelper(base->Left);
	 right = heightHelper(base->Right);

	 if(left > right)
	 {
		 return (left + 1);
	 }
	 else
	 {
		 return (right + 1);
	 }
 }


template <typename T>
void BST<T>::display(ostream & out)
{
	displayHelper(out, this->root, heightHelper(this->root), none);
}


template <typename T>
T BST<T>::find(T key)
{
	return (root->find(key));
}



template <typename T>
void BST<T>::inorderDisplay(ostream & out)
{
	if(root == T())
	{
		return;
	}
	inorderDisplay(root.getLeft());
	root.getData();
	inorderDisplay(root.getRight());
}

template <typename T>
void BST<T>::insertHelper(Node<T> * root, Node<T>* newNode)
{
	if(newNode->data < root->data)
	{ cout << "000";
		if(root->Left == NULL)
		{
			root->Left = newNode;
			cout << "001";
			return;
		}
		else
		{ cout << "002";
		insertHelper(root->Left, newNode);
		}
	}
	else if(newNode->data > root->data)
	{cout << "003";
		if(root->Right == NULL)
		{ cout << "004";
			root->Right = newNode;
			return;
		}
		else
		{cout << "005";
			insertHelper(root->Right, newNode);
		}
	}
}



template <typename T>
void BST<T>::insert(T data)
{
	counter++;
	if(root == NULL)
	{
		Node<T>* isempty;
		isempty = new Node<T>;
		isempty->setData(data);
		root = isempty;
	}
	 else
	{
		Node<T>* newNode;
		newNode = new Node<T>;
		newNode->setData(data);
		insertHelper(this->root, newNode);
	}
	
}


template <typename T>
const BST<T>& BST<T>::operator=(const BST<T>&bst)
{
	this->BSTcopy(this->root, bst.root);
	this->counter = bst.counter ;
}



template <typename T>
T BST<T>::remove(T key)
{
    T removed = T();
    root = removeHelper(key, root, removed);
    return removed;
}

template <typename T>
Node<T>* BST<T>::removeHelper(T key, Node<T>* node, T &removed)
{
    if( node != NULL)
    {
        if(node->getData() == key)
        {
            removed = node->getData();
            counter--;
            node = removeNode(node);
        }
        else if( node->getData() > key)
        {
            node->setLeft(removeHelper(key, node->getLeft(), removed));
        }
        else
        {
            node->setRight(removeHelper(key, node->getRight(), removed));
        }
    }
    return node;
}

template <typename T>
Node<T>* BST<T>::removeNode(Node<T>* node)
{
   
    if (node->getLeft() == NULL && node->getRight() == NULL) 
    {
        
        delete node;
        node = NULL;
    }
    else if(node->getLeft() == NULL)
    {
       
        Node<T>* temp = node->getRight();
        delete node;
        node = temp;
        temp = NULL;
    }
    else if(node->getRight() == NULL)
    {
        
        Node<T>* temp = node->getLeft();
        delete node;
        node = temp;
        temp = NULL;
    }
    else
    {
        
        Node<T>* right = node->getRight();
        Node<T>* orig = node->getRight();
        node->setData(right->getData());
        if(right != orig)
            node->setRight(right);
    }
    return node;
}


#endif
mistabob (35)
Anyone? I've got 50 minutes left to fix this last problem, and I'm so close....
TheIdeasMan (6817)
Well, time is nearly up, but for next time you really need to learn to use a debugger. It's the easiest way, and is what professional programmers do. Can you imagine a coder at work saying to his / her mates, can you help me with this - I am so close?

Also, people don't really want to look through 100's of LOC, to see what the problem is.
Last edited on
mistabob (35)
what do you mean, debugger? To the best of my knowledge the compiler won't find this type of error.
TheIdeasMan (6817)
There are two sorts of errors, compilation errors, and logical errors.

Debugging is not finding compilation errors, the compiler does that.

You can find logical errors by running a debugging program. If you have an IDE, this should be easy. Run the program in debug mode - yo can set breakpoints, have a watch list of variables - keep track of how the variable values change as you step through the code 1 line at a time. From this you can deduce where it all goes wrong.

If you don't have an IDE, (compiling from the shell) then you need to learn a command line debugger like gdb, this is generally harder than using the IDE.

HTH
Topic archived. No new replies allowed.