0

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?

2
Contributors
6
Replies
7
Views
7 Years
Discussion Span
Last Post by SasseMan
0

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.

0

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 by zoefschildpad: n/a

0

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...

0

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.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.