OK, first of all, thanks to everyone who helped me out with my Isomorphism problem - it finally works. Now, the other part of my homework I'm having trouble with is this:
Write an implementation of the set class, with associated iterators using a binary search tree. Add to each node a link to the parent node.
I don't want to post the whole code here - it's about 140 lines, and it would violate our homework policy.
Basically, it looks like my remove method is faulty; I'll include the struct definition, the class definition, and my two remove method definitions: -
template <typename T>
-
struct TreeNode {
-
T data;
-
TreeNode *left, *right, *parent;
-
~TreeNode() {
-
delete left;
-
delete right;
-
parent = 0;
-
}
-
};
-
-
template <typename T>
-
class BSTreeSet {
-
/*friend ostream& operator<<(ostream& out, const BSTreeSet<T> BST) {
-
BST.inorderPrint(out);
-
return out;
-
}*/
-
-
public:
-
BSTreeSet();
-
BSTreeSet(T initRoot);
-
~BSTreeSet() { delete root; }
-
bool insert(T obj);
-
void remove(T obj);
-
bool contains(T obj);
-
bool isEmpty() const { return root == NULL; };
-
void inorderPrint(ostream& out);
-
-
private:
-
bool insertHelper(TreeNode<T> *node, T obj);
-
void removeHelper(TreeNode<T> *node, T obj);
-
bool containsHelper(TreeNode<T> *node, T obj);
-
void IOPrint(TreeNode<T> *node, ostream& out);
-
TreeNode<T> *root;
-
};
-
-
template <typename T>
-
void BSTreeSet<T>::remove(T obj) {
-
return removeHelper(root, obj);
-
}
-
-
template <typename T>
-
void BSTreeSet<T>::removeHelper(TreeNode<T> *node, T obj) {
-
if (node == NULL) return;
-
if (node->data < obj) removeHelper(node->right, obj);
-
else if (node->data > obj) removeHelper(node->left, obj);
-
else if (node->left != NULL && node->right != NULL) {
-
TreeNode<T> *temp = node->right;
-
while (temp->left != NULL) temp = temp->left;
-
node->data = temp->data;
-
removeHelper(temp, temp->data);
-
} else {
-
TreeNode<T> *old = node;
-
node = (node->left != NULL) ? node->left : node->right;
-
delete old;
-
}
-
}
My test program generates a tree at random and displays its contents (all of which seems to be properly functioning). I then intentionally insert the value 20, to test my contains() method and my remove() method. It looks like contains() works, but I get:
Aborted (core dumped)
at that point in the program. Any ideas?
36 5878
Sure enough, when I stop using the .remove method in my driver program, everything works just fine.
I also have not yet bothered adding the iterators - that'll be tomorrows fun project.
UPDATE:
So I missed the & several places in the book's code. After adding these in the appropriate places to insert, contains, and remove, every thing's working as expected. :\
I'd still like to keep this thread alive, as I'll probably need a hand implementing the iterator.
OK, I've thought of the algorithm for ++ and -- on my iterator (which was the main problem in this assignment), but I'm having trouble actually inserting the iterator (and const_iterator) into my BSTreeSet class. Here's the class definitions: - class const_iterator {
-
public:
-
const_iterator() : current(NULL) { }
-
const T & operator*() const { return retrieve(); }
-
-
const_iterator& operator++() {
-
// Code removed to follow Guidelines
-
}
-
-
const_iterator operator++(int) {
-
const_iterator old = *this;
-
++(*this);
-
return old;
-
}
-
-
const_iterator& operator--() {
-
// Code removed to follow Guidelines
-
}
-
-
const_iterator operator--(int) {
-
const_iterator old = *this;
-
--(*this);
-
return old;
-
}
-
-
bool operator==(const const_iterator & rhs) const {
-
return current = rhs.current;
-
}
-
-
bool operator!=(const const_iterator & rhs) const {
-
return !(*this == rhs);
-
}
-
-
protected:
-
TreeNode<T> *current;
-
T & retrieve() const {
-
return current->data;
-
}
-
const_iterator(TreeNode<T> *t) : current(t) { }
-
friend class BSTreeSet<T>;
-
};
-
-
class iterator : public const_iterator {
-
public:
-
iterator() { }
-
-
T& operator*() { return retrieve(); }
-
const T& operator*() const { return const_iterator::operator*(); }
-
-
iterator& operator++() {
-
// Code removed to follow Guidelines
-
}
-
-
iterator operator++(int) {
-
iterator old = *this;
-
++(*this);
-
return old;
-
}
-
-
iterator& operator--() {
-
// Code removed to follow Guidelines
-
}
-
-
iterator operator--(int) {
-
iterator old = *this;
-
--(*this);
-
return old;
-
}
-
-
protected:
-
iterator(TreeNode<T> *t) : const_iterator(t) { }
-
friend class BSTreeSet<T>;
-
};
Now, most of this code is modified code from the Linked List class shown earlier in my book. Basically, the errors I'm getting are saying that the iterator class cannot see current, despite the fact that iterator is a subclass of const_iterator, and that current is protected in const_iterator. The verbose error list is:
$ g++ BSTSTest.cpp -o BSTest.exe
In file included from BSTSTest.cpp:2:
BSTree.h: In member function `T& BSTreeSet<T>::iterator::operator*()':
BSTree.h:93: error: there are no arguments to `retrieve' that depend on a templa
te parameter, so a declaration of `retrieve' must be available
BSTree.h:93: error: (if you use `-fpermissive', G++ will accept your code, but a
llowing the use of an undeclared name is deprecated)
BSTree.h: In member function `BSTreeSet<T>::iterator& BSTreeSet<T>::iterator::op
erator++()':
BSTree.h:97: error: `current' undeclared (first use this function)
BSTree.h:97: error: (Each undeclared identifier is reported only once for each f
unction it appears in.)
BSTree.h: In member function `BSTreeSet<T>::iterator& BSTreeSet<T>::iterator::op
erator--()':
BSTree.h:120: error: `current' undeclared (first use this function)
BSTSTest.cpp: In function `int main()':
BSTree.h:23: error: `class BSTreeSet<int>::const_iterator' is private
BSTSTest.cpp:25: error: within this context
BSTree.h: In member function `bool BSTreeSet<T>::const_iterator::operator==(cons
t BSTreeSet<T>::const_iterator&) const [with T = int]':
BSTree.h:77: instantiated from `bool BSTreeSet<T>::const_iterator::operator!=(
const BSTreeSet<T>::const_iterator&) const [with T = int]'
BSTSTest.cpp:25: instantiated from here
BSTree.h:73: error: assignment of data-member `BSTreeSet<int>::const_iterator::c
urrent' in read-only structure
BSTree.h: In member function `BSTreeSet<T>::const_iterator& BSTreeSet<T>::const_
iterator::operator++() [with T = int]':
BSTree.h:47: instantiated from `BSTreeSet<T>::const_iterator BSTreeSet<T>::con
st_iterator::operator++(int) [with T = int]'
BSTSTest.cpp:25: instantiated from here
BSTree.h:30: error: cannot call member function `TreeNode<T>* BSTreeSet<T>::find
Min(TreeNode<T>*) const [with T = int]' without object
BTW: Banfa, if you read this, this was the same problem I was having waaaaay back in my very first thread on Trees, back in October, which we never figured out.
Shouldn't these classes be template classes?
Savage
Shouldn't these classes be template classes?
Savage
Yea, you use T sometimes but I don't see a template. Also, in your == operator you put a single equal sign instead of a double one.
UPDATE:
OK. I've fixed all the errors so far, gotten iterators working, gotten .begin() and .end() to work, and I've successfully tested the ++ operators using a for...loop: - for (itr = BSTS.begin(); itr != BSTS.end(); itr++)
-
cout << *itr << " ";
I have yet to test .find(), .erase(), and .insert() using the iterators. So far, I have been using Tree-style inserts and erases, so the iterator style functions may give me trouble.
Again, thank you ALL for your help.
UPDATE:
OK. I've fixed all the errors so far, gotten iterators working, gotten .begin() and .end() to work, and I've successfully tested the ++ operators using a for...loop: - for (itr = BSTS.begin(); itr != BSTS.end(); itr++)
-
cout << *itr << " ";
I have yet to test .find(), .erase(), and .insert() using the iterators. So far, I have been using Tree-style inserts and erases, so the iterator style functions may give me trouble.
Again, thank you ALL for your help.
If you get stuck feel free to post.Someone will(probably) give you a hand.
Savage
OK. Here's where I'm at:
Iterators are working OK. I'm required to write the following functions: - iterator find(T obj); // returns an iterator pointing to the node containing obj
-
iterator erase(iterator pos); // erases the node pointed to by pos, and returns an iterator pointing to the node before pos.
-
iterator erase(iterator from, iterator to); // erases the nodes between from and to, and returns an iterator pointing to the node before from.
-
pair<iterator, bool> insert(T obj); // Insert obj into the set. The pair returned includes the iterator pointing to the node now containing obj and true if the insertion was successful, or the node already containing obj and false if the insertion failed.
-
pair<iterator, bool> insert(iterator hint, T obj); // Insert obj into the set. The return value is identical to the one-parameter insert above. The hint argument supposedly indicates the node to which obj should be added (i.e. the parent of the new node). If this hint is bad, the one-parameter insert is called.
I'm pretty sure find() is working, so I won't bother including that. However, the inserts and erases are throwing segfault errors and core dumps all over the place. Here are the definitions of these functions, and a few others that are also used: - //*******************************************************************************
-
// The following methods are INSIDE the BSTreeSet class definition
-
//*******************************************************************************
-
iterator erase (iterator pos) {
-
iterator* ret = new iterator(pos);
-
(*ret)++; // NOTE: I realize this advances the iterator forward, rather than backwards, but I'll be able to fix this by reversing the logic of ++.
-
cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
-
erase(*pos);
-
return (*ret);
-
}
-
-
iterator erase (iterator from, iterator to) {
-
iterator *ret = new iterator(to);
-
(*ret)++; // NOTE: I realize this advances the iterator forward, rather than backwards, but I'll be able to fix this by reversing the logic of ++.
-
while (from != to) {
-
T temp = *from;
-
from++;
-
erase(temp);
-
}
-
erase(*to);
-
return (*ret);
-
}
-
-
//*******************************************************************************
-
// The following methods are OUTSIDE the BSTreeSet class definition
-
//*******************************************************************************
-
-
template <typename T>
-
void BSTreeSet<T>::erase(T obj) {
-
removeHelper(root, obj);
-
}
-
-
template <typename T>
-
void BSTreeSet<T>::removeHelper(TreeNode<T> * & node, T obj) {
-
if (node == NULL) return;
-
if (node->data < obj) removeHelper(node->right, obj);
-
else if (node->data > obj) removeHelper(node->left, obj);
-
else if (node->left != NULL && node->right != NULL) {
-
TreeNode<T> *temp = node->right;
-
while (temp->left != NULL) temp = temp->left;
-
node->data = temp->data;
-
removeHelper(temp, node->data);
-
} else {
-
TreeNode<T> *old = node;
-
node = (node->left != NULL) ? node->left : node->right;
-
node->parent = old->parent;
-
delete old;
-
}
-
}
Phew...that's a lot of code. Anyway, I'm fairly sure the problem has to do with my removeHelper. In order to support the iterator's ++, I've added a TreeNode<T> *parent link to each TreeNode. The removeHelper method was written before this parent link was added, and there may be some logic missing in creating parent links, though as you can see (at line 46 here) I've added in at least one case of the parent link changing. I'm going to see what I can do with that while I wait for a response.
As always, THANK YOU SO MUCH for any advice/help.
Let's start with this: - iterator erase (iterator pos) {
-
-
iterator* ret = new iterator(pos);
-
-
(*ret)++; // NOTE: I realize this advances the iterator forward, rather than backwards, but I'll be able to fix this by reversing the logic of ++.
-
-
cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
-
erase(*pos);
-
-
return (*ret);
-
-
}
You are returning a pointer which points to function local dynamically allocated iterator.Allocated memory is on heap(and it's never freed as I can see),but pointer is on stack.Function ends,local stack variables are deallocated,and as a result you got yourself my personal favorite,damn, cursed, bloody seg error.
You need to find a way around this.Perhaps a pointer to a iterator as a function argument or new member of the BSTreeSet class.
Savage
Unfortunately, I cannot change the function header - it must return an iterator, and the argument must be an iterator. I had thought dynamically allocation the iterator would mean that it would not be destroyed, so that when I return the dereferenced pointer, that copy would be returned. The pointer (res) is indeed de-allocated, but the object I created shouldn't be. Maybe I can access the return value as: - BSTreeSet<int>::iterator itr = &BSTS.erase(pos);
but in order for this to work, the function itself has to work :\.
EDIT: After further research, I found that the erase functions have to return an iterator pointing to the node AFTER the deletions, so the ++ is correct in the above code.
OK, for Savage's suggestion:
I looked up the erase methods for the list class, provided in my book: - iterator erase(iterator itr) {
-
Node *p = itr.current;
-
iterator retVal(p->next);
-
/* List-style deletion here... */
-
delete p;
-
size--;
-
-
return retVal;
-
}
-
-
iterator erase(iterator start, iterator end) {
-
for (interator itr = from; itr != to; )
-
itr = erase(itr);
-
-
return to;
-
}
The main point is that the top function is returning retVal, which is a local object. This code is PROVIDED BY THE BOOK, which means it should probably work. Also, I didn't realize that the node pointed to by to in the second erase was not to be deleted. So I've changed the erase functions to this: - iterator erase (iterator pos) {
-
iterator ret(pos);
-
ret++;
-
//cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
-
erase(*pos);
-
return ret;
-
}
-
-
iterator erase(iterator from, iterator to) {
-
for (interator itr = from; itr != to; )
-
itr = erase(itr);
-
-
return to;
-
}
Unfortunately, I cannot change the function header - it must return an iterator, and the argument must be an iterator. I had thought dynamically allocation the iterator would mean that it would not be destroyed, so that when I return the dereferenced pointer, that copy would be returned. The pointer (res) is indeed de-allocated, but the object I created shouldn't be. Maybe I can access the return value as: - BSTreeSet<int>::iterator itr = &BSTS.erase(pos);
but in order for this to work, the function itself has to work :\.
I'm not sure about that.
Object is not destroyed,but without a pointer that has pointed to it you cannot access it.
I'm suprised that your compiler didn't gaved you a warning,something like:
Temporary allocated variable returned from function.
I know when I make such mistake on bc32 or VC,it throws this warning.
Have you tried adding a iterator member to BSTreeSet class?
Savage
OK, for Savage's suggestion:
I looked up the erase methods for the list class, provided in my book: - iterator erase(iterator itr) {
-
Node *p = itr.current;
-
iterator retVal(p->next);
-
/* List-style deletion here... */
-
delete p;
-
size--;
-
-
return retVal;
-
}
-
-
iterator erase(iterator start, iterator end) {
-
for (interator itr = from; itr != to; )
-
itr = erase(itr);
-
-
return to;
-
}
The main point is that the top function is returning retVal, which is a local object. This code is PROVIDED BY THE BOOK, which means it should probably work. Also, I didn't realize that the node pointed to by to in the second erase was not to be deleted. So I've changed the erase functions to this: - iterator erase (iterator pos) {
-
iterator ret(pos);
-
ret++;
-
//cout << "*pos == " << (*pos) << " and *ret == " << *(*ret) << endl;
-
erase(*pos);
-
return ret;
-
}
-
-
iterator erase(iterator from, iterator to) {
-
for (interator itr = from; itr != to; )
-
itr = erase(itr);
-
-
return to;
-
}
It can return local variable,but not one allocated on the heap.(without a seg offcourse)
Savage
I'm not sure there should be any need to add an iterator member to the tree...what would it be used for? Basically, I'm modeling the set off the list provided in the book (because they're both STL-style), and there's no need for an iterator member in List.
UPDATE: It looks like insert is actually working correctly. I'm going to go back and get rid of any code I have for inserts, because I'm getting a sickly feeling that I'm stretching the homework guidelines to their limits.
I'm not sure there should be any need to add an iterator member to the tree...what would it be used for? Basically, I'm modeling the set off the list provided in the book (because they're both STL-style), and there's no need for an iterator member in List.
Does erase works now?
I thought to follow your previous erase idea.So instead of having a local temporary allocated iterator,you could have in class a pointer to a iterator which then can easily be manipulated without segs,but if erase now works then it has no use.
Savage
erase still doesn't work. I'm not quite clear on how using a member of the Set class will help me in erase(iterator). What you're saying is:
1) I set this member iterator to the node after pos.
2) I delete the element at pos.
3) I return a copy of the member iterator.
Right?
I'm still pretty sure there's a problem in my actual deletion of the element...represented by the function removeHelper(TreeNode * &, T obj).
erase still doesn't work. I'm not quite clear on how using a member of the Set class will help me in erase(iterator). What you're saying is:
1) I set this member iterator to the node after pos.
2) I delete the element at pos.
3) I return a copy of the member iterator.
Right?
I'm still pretty sure there's a problem in my actual deletion of the element...represented by the function removeHelper(TreeNode * &, T obj).
Yes,something like that.
About removeHelper,you never delete temp.
Savage
I assume you're talking about temp in the fourth if clause, - else if (node->left != NULL && node->right != NULL)
The node pointed to by temp should be deleted in the recursive call at the end of this clause: - removeHelper(node->right, node->data);
unless I'm mistaken.
I realized that, in removeHelper, once the fourth if clause fails (where we test for node being a full node (i.e. having both children)), I assumed that node had at least one child. But node could be a leaf. So I've added a clause, and it now looks like this: - void removeHelper(TreeNode * & node, T obj) {
-
if (node == NULL) return; // Value not found.
-
if (node->data < obj) removeHelper(node->right, obj); // Value not here; remove from right subtree.
-
else if (node->data > obj) removeHelper(node->left, obj); // Value not here; remove from left subtree.
-
else if (node->left != NULL && node->right != NULL) { // Value found! node has 2 children.
-
TreeNode *temp = node->right;
-
while (temp->left != NULL) temp = temp->left;
-
node->data = temp->data;
-
removeHelper(node->right, node->data);
-
} else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) { // node has 1 child.
-
TreeNode *old = node;
-
node = (node->left != NULL) ? node->left : node->right;
-
node->parent = old->parent;
-
delete old;
-
} else delete node; // node is a leaf, and can be directly deleted.
-
}
Errors were not fixed.
For the record, here's my test program and my results: - #include <iostream>
-
#include "BSTreeSet.h"
-
using namespace std;
-
-
int main() {
-
srand((unsigned)time(NULL));
-
BSTreeSet<int> BSTS;
-
int delay;
-
for (int i = 0; i < 10; i++)
-
BSTS.insert(rand() % 100+1);
-
-
pair<BSTreeSet<int>::iterator, bool> myPair = BSTS.insert(32);
-
if(myPair.second) {
-
cout << "32 was inserted correctly. " << *(myPair.first) << endl;
-
} else {
-
cout << "32 was NOT inserted correctly. " << *(myPair.first) << endl;
-
}
-
-
BSTreeSet<int>::const_iterator itr;
-
-
for (itr = BSTS.begin(); itr != BSTS.end(); ++itr) {
-
cout << *itr << " ";
-
}
-
cout << endl;
-
-
/*BSTreeSet<int>::iterator from = BSTS.begin();
-
BSTreeSet<int>::iterator to = BSTS.begin();
-
for (int i = 0; i < 3; i++) to++;
-
-
BSTreeSet<int>::iterator after = BSTS.erase(from, to);
-
-
cout << *after << endl;*/
-
-
BSTreeSet<int>::iterator test;
-
cout << "Which value should I search for? ";
-
int val;
-
cin >> val;
-
-
test = BSTS.find(val);
-
cout << *test << endl;
-
-
test = BSTS.erase(test);
-
/*cin >> val;
-
for (itr = BSTS.begin(); itr != BSTS.end(); ++itr) {
-
cout << *itr << " ";
-
cin >> val;
-
}*/
-
-
cout << endl;
-
-
return 0;
-
}
$ g++ BSTSTest.cpp -o BSTest.exe
$ BSTest
32 was inserted correctly. 32
8 14 16 24 32 37 44 63 76 87 97
Which value should I search for? 16
16
27 [main] BSTest 460 _cygtls::handle_exceptions: Error while dumping state
(probably corrupted stack)
Segmentation fault (core dumped)
UPDATE: Crap, insert is not working properly, like I thought it was. The iterator it returns within the pair only points to the correct place sometimes. At other times, it was pointing 1 ahead, then 2 ahead, then at the min value...no clue. I'm going to try to work on this; in the meantime, here's the insert code again:
ANOTHER UPDATE:
Fixed it. I was making the iterator portion of the pair based on node rather than temp. Re-removing the method definition...
This is getting messy, eh?
I've narrowed the problem down to this function: - void removeHelper(TreeNode * & node, T obj) {
-
if (node == NULL) return; // Value not found.
-
if (node->data < obj) removeHelper(node->right, obj); // Value not here; remove from right subtree.
-
else if (node->data > obj) removeHelper(node->left, obj); // Value not here; remove from left subtree.
-
else if (node->left != NULL && node->right != NULL) { // Value found! node has 2 children.
-
TreeNode *temp = node->right;
-
while (temp->left != NULL) temp = temp->left;
-
node->data = temp->data;
-
removeHelper(node->right, node->data);
-
} else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) {
-
TreeNode *old = node;
-
node = (node->left != NULL) ? node->left : node->right;
-
node->parent = old->parent;
-
delete old;
-
} else delete node;
-
}
I wrote an explicit remove function which takes a T value and calls removeHelper with root and that value. In my driver program, I ignored erase and used remove - the same error occured. That means the problem shouldn't be in erase() - it must be in removeHelper().
After some more testing, I think the problem is in the portions of code where the value has been found, and has either 1 child or is a leaf. The portion where a node has 2 children seems to work until the point where you need to erase the now-repeat value (which, by definition, has either 1 child or is a leaf - thus the error).
My code has become VERY messy, but here's what I'm working with right now: - void removeHelper(TreeNode * & node, T obj) {
-
cout << "Entering removeHelper..." << endl;
-
if (node == NULL) { // Value not found.
-
cout << "Value not found." << endl;
-
return;
-
}
-
if (node->data < obj) { // Value not here; remove from right subtree.
-
cout << "Moving to right subtree - currently at " << node->data << endl;
-
removeHelper(node->right, obj);
-
}
-
else if (node->data > obj) { // Value not here; remove from left subtree.
-
cout << "Moving to left subtree - currently at " << node->data << endl;
-
removeHelper(node->left, obj);
-
}
-
else if ((node->left != NULL) && (node->right != NULL)) { // Value found! node has 2 children.
-
cout << "The value has been found, and has 2 children. The value is " << node->data << endl;
-
TreeNode *temp = node->right;
-
while (temp->left != NULL) temp = temp->left;
-
node->data = temp->data;
-
removeHelper(node->right, node->data);
-
} else if ((node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL)) {
-
cout << "The value has been found, and only has one child. The value is " << node->data << endl;
-
TreeNode *old = node;
-
if (node->left == NULL) {
-
if ((old->parent)->right == node) {
-
node = node->right;
-
(old->parent)->right = node;
-
} else {
-
node = node->right;
-
(old->parent)->left = node;
-
}
-
} else {
-
if ((old->parent)->right == node) {
-
node = node->left;
-
(old->parent)->right = node;
-
} else {
-
node = node->left;
-
(old->parent)->left = node;
-
}
-
}
-
node->parent = old->parent;
-
delete old;
-
} else {
-
cout << "The value has been found, and is a leaf. The value is " << node->data << endl;
-
if ((node->parent)->left == node) {
-
TreeNode *temp = node->parent;
-
(node->parent)->left == NULL;
-
delete temp;
-
} else {
-
TreeNode *temp = node->parent;
-
(node->parent)->right == NULL;
-
delete temp;
-
}
-
}
-
}
As you can see, there's about 32487632948 cout statements so I can see exactly what's happening.
LOL,isn't TreeNode a template struct,I don't see T in your function call?
Savage
I moved the TreeNode definition inside the BSTreeSet class definition, along with every single function, so you barely see any T's anywhere anymore. It's still compiling correctly, though.
Bah, I can't stand it. I took the remove function straight out of the book for Binary Search Trees, added the parent modifications, and it still segfaults on me. What the heck?
I'm about ready to give up on this - as of right now, I have 4 hours to complete this. I don't think it's happening.
Bah, I can't stand it. I took the remove function straight out of the book for Binary Search Trees, added the parent modifications, and it still segfaults on me. What the heck?
I'm about ready to give up on this - as of right now, I have 4 hours to complete this. I don't think it's happening.
I think i got it Gannon.
It's the parent variable of TreeNode.
That's what producing a seg.
Savage
That's what I think, too. If I didn't have that parent link, there wouldn't be a problem with segfault errors. However, in order to implement the incrementation operators in my iterator classes, I need that parent link - it is also dictated in the book. There are other methods of incrementation, but the one I was told to implement was the one with the parent link.
That's what I think, too. If I didn't have that parent link, there wouldn't be a problem with segfault errors. However, in order to implement the incrementation operators in my iterator classes, I need that parent link - it is also dictated in the book. There are other methods of incrementation, but the one I was told to implement was the one with the parent link.
It works:(!!)
in create initialize parent to NULL,in insert I have added these lines: - if ((*temp)->data < obj)
-
{
-
insert(&(*temp)->right, obj);
-
(*temp)->right->parent=(*temp);//<------
-
-
}
-
-
else if (obj < (*temp)->data)
-
{
-
-
insert(&(*temp)->left, obj);
-
(*temp)->left->parent=(*temp);//<------
-
}
-
else{
-
insert(&(*temp)->left, obj);
-
(*temp)->left->parent=(*temp);//<-----
-
}
-
And it runs without seg on VC.I sure hope it works on your compiler.
Savage
Unfortunately, no, it doesn't work for me. The homework was due today, so I turned in what I had - partial credit should be better than a 0. I did end up getting most of it working, though, so maybe I'll get a high grade anyway. We'll see.
Thanks SO MUCH for your help, Savage.
Unfortunately, no, it doesn't work for me. The homework was due today, so I turned in what I had - partial credit should be better than a 0. I did end up getting most of it working, though, so maybe I'll get a high grade anyway. We'll see.
Thanks SO MUCH for your help, Savage.
I don't understand,this should work.
Have you tried with other compilers?
Are you sure that it's still the parent variable the one producing a seg?
Perhaps,it's something else..
I hope that you will get a high mark..
It's all STL's standards fault.It's to messy. :D
Savage
Actually, the STL set uses a different traversal method, so I suspect it's not messy. I haven't tried other compilers...but we're supposed to be using g++, and that's what was throwing errors. Maybe I'll try in Visual C++ (I think my laptop has that...)
Actually, the STL set uses a different traversal method, so I suspect it's not messy. I haven't tried other compilers...but we're supposed to be using g++, and that's what was throwing errors. Maybe I'll try in Visual C++ (I think my laptop has that...)
I'm just looking to blame something for this slight failure. :D
Savage
Sign in to post your reply or Sign up for a free account.
Similar topics
by: j |
last post by:
Hi,
Anyone out there with binary search tree experience. Working on a
project due tomorrow and really stuck. We need a function that splits
a binary tree into a bigger one and smaller one(for a...
|
by: tsunami |
last post by:
hi all;
I have an array and want to insert all the elements from this array to
a binary search tree.That array is an object of the class of a
stringtype which includes overloaded "< > = =="...
|
by: Tarique Jawed |
last post by:
Alright I needed some help regarding a removal of a binary search
tree. Yes its for a class, and yes I have tried working on it on my
own, so no patronizing please. I have most of the code working,...
|
by: mathon |
last post by:
Hello,
im currently implementing a binary search tree means, that a greater
number than root will be added as right child and a less number as left
child. My insert function looks currently like...
|
by: mathon |
last post by:
hi,
now i facing a problem which i do not know how to solve it...:(
My binary search tree structures stores a double number in every node,
whereby a higher number is appended as right child...
|
by: hn.ft.pris |
last post by:
I have the following code:
Tree.h defines a simple binary search tree node structure
########## FILE Tree.h ################
#ifndef TREE_H
#define TREE_H
//using namespace std;
template...
|
by: pankajit09 |
last post by:
Hello,
I have a textbox in which I have to enter a string of numbers.
The numbers are to be converted in to a Binary Search Tree and then I have to determine whether the BST is a -->
1....
|
by: gekko3558 |
last post by:
I am writing a simple binary search tree (nodes are int nodes) with a BSTNode class and a BST class. I have followed the instructions from my C++ book, and now I am trying to get a remove method...
|
by: Defected |
last post by:
Hi,
How i can create a Binary Search Tree with a class ?
thanks
|
by: Defected |
last post by:
Hi,
How i can implement a main function with this Binary Search Tree.
thanks for help.
is this code corrected ?
#include<iostream>
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
| |