so I'm writing a binary search tree and a (so far very short) program taht uses it. Here's the code as it is (excluding any functions it doesn't actually use yet)
main.cc:

#include <ctime>
#include <cstdlib>
#include <iostream>
#include "bintree.h" 

using namespace std;

int main(){
 double aipls[500];
 bst<int> k;
 int values[500];
 int c, temp;

 srand(time(NULL));
 for (int i = 0; i < 500; i++){
   values[i] = i+1;
 }
 for (int i = 0; i < 500; i++){
   for(int j = 0; j < 499; j++) {
     k.insert(values[j]);
   }
   k.insert(values[499]);
   k.clear();
 } 

 return 0;
}

and bintree.h:

#include <iostream>

using namespace std;

//returns the largest of a and b
int largest(int a, int b){
 if (a > b){
   return a;
 }
 return b;
}

template <class T>
class thing{ //a node in the binary search tree
 public:
   T value;
   thing<T> * left;
   thing<T> * right;
};

template <class T>
class bst{
 private:
   thing<T> * start;//root of the tree
   void destroy(thing<T> *);//destroys the subtree
 public:
   bst<T>();//constructor
   void insert(T);//inserts a value into the tree
   void clear();
};

template <class T>
bst<T>::bst(){
 start = NULL;
}

template <class T>
void bst<T>::clear(){
 thing<T> *p = start;
 destroy(start->right);
 destroy(start->left);
 start = NULL;
 delete p;
}

template <class T>
void bst<T>::destroy(thing<T> * p){
 if (p!=NULL){
   destroy(p->right);
   destroy(p->left);
   delete p;
 }
}

template <class T>
void bst<T>::insert(T value){
 thing<T> * p = start;
 if (start == NULL){
   start = new thing<T>;
   start->value = value;
   return;
 }

 while (true){
   if ((p->value) > value){
     if (p->left != NULL){
       p = p->left;
     } else {
       p->left = new thing<T>;
       p->left->value = value;
       return;
     }
   } else {
     if (p->right != NULL){
       p = p->right;
     } else {
       p->right = new thing<T>;
       p->right->value = value;
       return;
     }
   }
 }
}

The program should add 1-500 to the tree, clear the tree and repeat that another 499 times. I think it gives me the segfault when it tries to fill the tree again the second time, but I can't seem to find out why.

note that the clear function has been many things, this was just my latest attempt.

Can anyone help me find the error?

Segfaults are memory access violations. Try to find on exactly which row the segfault occurs by printing stuff before and after a row that you suspect may be causing the segfault, that would narrow the search down quite a bit.

The segfault occurs after running when calling k.insert after running k.clear, but I don't understand why, the tree should be in the same state as it was after running the constructor...

Edited 6 Years Ago by zoefschildpad: n/a

I feel silly, the problem is that, when creating a new node, I don't initialize it's left and right pointers. what baffles me though is that it worked just fine before clearing the tree...

the clear function is working just fine, it's the insert function that's the problem. it's not initializing the pointers of new nodes. I fixed it and it works fine now.

thanks for your help.

This question has already been answered. Start a new discussion instead.