So I have a program that reads data/text files, with 1 number on each line and makes a binary search tree from it. When i insert a node, there should be two data variables updated, searchcost and key.. Key being the actual number of the element, and the searchcost is 1+the depth of the node. For data files that have numbers up to a certain amount insert works. But if it has numbers above say..3047 then the insert function gives a stack overflow error. Here is the insert method. Debugging says its coming from

t = new BinaryNode(x,count);

but I have no clue why.

BinaryNode *BinarySearchTree::insert(int x,
BinaryNode *t) 
{
static long count;
count++;



if (t == NULL){ t = new BinaryNode(x,count);
count=0;
}
else if (x < t->key){
	t->left = insert(x, t->left);

}
else if (x > t->key){
	
t->right = insert(x, t->right);

}
else
throw DuplicateItem();
return t;
}

Recommended Answers

All 15 Replies

>>static long count;
>>count++;

Your program is incrementing an uninitialized integer and then you use that integer later on in the function. initialize it to 0 static long count = 0;

>>static long count;
>>count++;

Your program is incrementing an uninitialized integer and then you use that integer later on in the function. initialize it to 0 static long count = 0;

I think it sets it to 0 by default but just for conventions sake I set it to 0. However i still get the stack overflow error. The funny thing is that when I enter in a list with 4095 numbers in random order, it does not give me a stack overflow...however when i enter in a list with 4095 numbers in increasing order (linear tree) it does....I'm pretty confused =/

Post entire code so that we can compile and test it.

Post entire code so that we can compile and test it.

Heh...its pretty long... the file 12l is the text document with 4095 numbers in increasing order. Just enter in "12l.txt" when the prompt comes up.

nvm

nvm

Oh here are the 4095 numbers in random order...As you can see it works with that.

You need to also post RuntimeException.h and its corresponding *.cpp file if there is one.

Whoops, must've missed it.

using vc++ 2008 express I get a lot of these warnings
warning C4290: C++ exception specification ignored except to indicate a function is not __declspec(nothrow)

The Parser.h you include in main.cpp -- it that one of your header files? There is also one in the Windows SDK, which is the one that vc++ 2008 express is picking up.

using vc++ 2008 express I get a lot of these warnings
warning C4290: C++ exception specification ignored except to indicate a function is not __declspec(nothrow)

The Parser.h you include in main.cpp -- it that one of your header files? There is also one in the Windows SDK, which is the one that vc++ 2008 express is picking up.

Parser.h is from another project so I don't even need that for my header. Actually i don't need "Evaluator.h" either...both are from another project. About the warnings...I just ignore them since the program works for the most part..

any more problems running it??

One of the problems is that when the current value (509) is less than the value at the root (913) there is no provision to insert the new value at the root of the list. Instead, it inserts it at t->left, but it should be added at t. Learning to format your program better to make it more readable might help you understand what is going on

BinaryNode *BinarySearchTree::insert(int x,
BinaryNode *t) 
{
    static long count=0;
    count++;
    if (t == NULL)
    { 
        t = new BinaryNode(x,count);
        count=0;
    }
// t->key == 913 and x = 509
    else if (x < t->key)
    {
      // this is wrong when x < t->key
	    t->left = insert(x, t->left);

    }
    else if (x > t->key)
    {
	
        t->right = insert(x, t->right);

    }
    else
        throw DuplicateItem();
    return t;
}

One of the problems is that when the current value (509) is less than the value at the root (913) there is no provision to insert the new value at the root of the list. Instead, it inserts it at t->left, but it should be added at t. Learning to format your program better to make it more readable might help you understand what is going on

BinaryNode *BinarySearchTree::insert(int x,
BinaryNode *t) 
{
    static long count=0;
    count++;
    if (t == NULL)
    { 
        t = new BinaryNode(x,count);
        count=0;
    }
// t->key == 913 and x = 509
    else if (x < t->key)
    {
      // this is wrong when x < t->key
	    t->left = insert(x, t->left);

    }
    else if (x > t->key)
    {
	
        t->right = insert(x, t->right);

    }
    else
        throw DuplicateItem();
    return t;
}

Its supposed to insert in the order that the list is given in...So 503 would be to the left of 913. Its not making a linear list with the random list. It works with the random list... However, its screwing up on the other list, 12l.txt...the one that starts with 1 and goes to 4095 in that respective order.

Ok, sorry I misunderstood. I won't be able to look at it again for the next 36 hours (sleep + work + honey-do-list).

Ok, sorry I misunderstood. I won't be able to look at it again for the next 36 hours (sleep + work + honey-do-list).

Thats cool, I understand..Unfortunately for me I need to get this done by Sunday and this is the only me stopping me from finishing it..programming wise. Out of 36 data test files, 12l is the only one that doesn't work =/.

I think i figured out the problem. Its making a 4095 number linear tree, with 4095 recursive calls and thus overflowing the stack....Now how to fix that is the next problem.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.