Stack Overflow?

Question

karolik 0 Newbie Poster

14 Years Ago

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;
}

c++

2 Contributors
15 Replies
140 Views
1 Day Discussion Span
Latest Post 14 Years Ago Latest Post by karolik

Ancient Dragon 5,243 Achieved Level 70

14 Years Ago

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

Edited 14 Years Ago by Ancient Dragon because: n/a

Ancient Dragon 5,243 Achieved Level 70

14 Years Ago

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

Ancient Dragon 5,243 Achieved Level 70

14 Years Ago

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

Edited 14 Years Ago by Ancient Dragon because: n/a

Ancient Dragon 5,243 Achieved Level 70

14 Years Ago

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.

Reply to this topic

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.

karolik 0 Newbie Poster · Answer 1 · 2010-04-02T09:28:11+00:00

>>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 =/

karolik 0 Newbie Poster · Answer 2 · 2010-04-02T09:51:20+00:00

karolik 0 Newbie Poster

14 Years Ago

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.

12l.txt (22.91 KB)

The attachment preview is chopped off after the first 10 KB. Please download the entire file.

BinaryNode.cpp (0.55 KB)

#include "BinaryNode.h"

long BinaryNode::size(BinaryNode *t) { //recursive
if (t == NULL)
return 0;
else
return 1 + size(t->left) + size(t->right);
}
int BinaryNode::height(BinaryNode *t) { //recursive
if (t == NULL)
return -1;
else {
int hlf = height(t->left), hrt = height(t->right);
return (hlf > hrt) ? 1+hlf : 1+hrt; // 1+max(hlf,hrt)
}
}
BinaryNode *BinaryNode::copy( ) { // recursive
BinaryNode *root = new BinaryNode(key);
if (left != NULL)
root->left = left->copy();
if (right != NULL)
root->right = right->copy();
return root;
}

BinaryNode.h (0.57 KB)

#include <cstddef> // to define NULL
#include "RuntimeException.h"
class BinaryNode {
private:
friend class BinaryTree;
friend class BinarySearchTree;

int key;
BinaryNode *left, *right;
long searchcost;
public:
BinaryNode(int el = 0, long el2 =0, BinaryNode *lt = NULL,
BinaryNode *rt = NULL) : //constructor
key(el), searchcost(el2), left(lt), right(rt) { }
// functions
BinaryNode *getLeft() { return left; }
BinaryNode *getRight() { return right; }
int getElem() { return key; }
long size(BinaryNode *t);
int height(BinaryNode *t);
BinaryNode *copy();
};

BinarySearchTree.cpp (2.19 KB)

#include "BinarySearchTree.h"
#include <iostream>
#include "RuntimeException.h"
using namespace std;

BinaryNode *BinarySearchTree::findMin(BinaryNode *t) throw(EmptyTree)

{
if (t == NULL) throw EmptyTree();
while (t->left != NULL) t = t->left;
return t;
}


BinaryNode *BinarySearchTree::find(int x, BinaryNode *t) throw(ItemNotFound )

{
while (t != NULL)
if (x < t->key) t = t->left;
else if (x > t->key) t = t->right;
else return t; // found
throw ItemNotFound();
}
BinaryNode *BinarySearchTree::insert(int x,
BinaryNode *t) 
{
static long count=0;
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;
}
BinaryNode *BinarySearchTree::removeMin(BinaryNode *t) throw(ItemNotFound)
 // private function
{
if (t == NULL) throw ItemNotFound();
if (t->left != NULL)
t->left = removeMin(t->left);
else {
BinaryNode *node = t;
t = t->right;
traverse(t);
delete node;
}
return t;
}
void BinarySearchTree::traverse(BinaryNode *t) throw(ItemNotFound)
{

	if(t!=NULL){
		t->searchcost--;
		traverse(t->left);
		traverse(t->right);

	}
}

BinaryNode *BinarySearchTree::remove(int x, BinaryNode *t) throw(ItemNotFound)
 // private function
{ if (t == NULL) throw ItemNotFound();
if (x< t->key)
t->left = remove(x, t->left);
else if (x > t->key)
t->right = remove(x, t->right);
else if (t->left != NULL && t->right != NULL) {
// item x is found; t has two children
t->key = findMin(t->right)->key;
t->right = removeMin(t->right);
} else { //t has only one child

BinaryNode *node = t;
t= (t->left != NULL) ? t->left : t->right;

traverse(t);

delete node;
}
return t;
}
void BinarySearchTree::display(BinaryNode *t) const
{
	if(t)
	{
	display(t->left);
	cout<<t->key<<"["<<t->searchcost<<"] ";
	display(t->right);


	}


}
long BinarySearchTree::sum(BinaryNode *t) const
{
static long count=0;
long count2;
if(t)
	{
	sum(t->left);
	sum(t->right);
	count=count+(t->searchcost);
	if((t->searchcost)==1){
		count2=count;
		count=0;
		return count2;
	}
	}



}

BinarySearchTree.h (1.48 KB)

#include "BinaryTree.h"

class BinarySearchTree { // uses the class BinaryNode
private: BinaryNode *root;
// some private functions will be here
public: // constructor
class EmptyTree : public RuntimeException {
	public:
		EmptyTree() : RuntimeException("tree is empty") {}
	};
class ItemNotFound : public RuntimeException {
	public:
		ItemNotFound() : RuntimeException("item not found") {}
	};
class DuplicateItem : public RuntimeException {
	public:
		DuplicateItem() : RuntimeException("duplicate item") {}
	};
BinarySearchTree( ) { root = NULL; }
~BinarySearchTree( ) { BinaryTree::deleteTree(root); root = NULL; }
long size() {return (root==NULL) ? 0 : root->size(root);}
int height() {return (root==NULL) ? 0 : root->height(root);}
BinaryNode* findMin(BinaryNode *t) throw(EmptyTree);
BinaryNode* removeMin(BinaryNode *t) throw(ItemNotFound);
BinaryNode *find(int x,BinaryNode *t) throw(ItemNotFound );
BinaryNode *insert(int x,BinaryNode *t) throw(DuplicateItem);
BinaryNode* remove(int x,BinaryNode *t) throw(ItemNotFound); 
void insert(int x) throw(DuplicateItem)
{ root = insert(x, root); }
void remove(int x) throw(ItemNotFound)
{ root = remove(x, root); }
void traverse(BinaryNode *t) throw(ItemNotFound);
BinaryNode *find(int x) throw(ItemNotFound)
{ return find(x, root); }
bool isEmpty( ){ return root == NULL; }
void display() const
{display(root);}
void display(BinaryNode *t) const;
long sum(BinaryNode *t) const;
long sum() const
{return sum(root);}
};

BinaryTree.cpp (0.38 KB)

// merge t1, t2 and root (with rootItem)
#include "BinaryTree.h"
#include <iostream>
using namespace std;



// delete a tree rooted at "root"
void BinaryTree::deleteTree(BinaryNode *root)
{ // postorder traversal
if (root == NULL) return; // nothing to delete
if (root->left != NULL)
deleteTree(root->left);
if (root->right != NULL)
deleteTree(root->right);
delete root;
}

BinaryTree.h (0.69 KB)

#include "BinaryNode.h"
class BinaryTree {
private:
BinaryNode *root;
friend class BinarySearchTree;
static void deleteTree(BinaryNode *root);
public: // class BinaryTree (cont)
BinaryTree( ) { root = NULL; }
BinaryTree(int el) { root = new BinaryNode(el); }
~BinaryTree() { deleteTree(root); root = NULL; }
// functions
BinaryNode *getRoot( ) { return root; }
bool isEmpty( ) { return root == NULL; }
int size( ) { return (root == NULL) ? 0 :
root->size(root); }
int height( ) { return (root == NULL) ? 0 :
root->height(root); }
void copy(BinaryTree& rhs) {
if (this != &rhs) {
deleteTree(root); // make tree empty
if (rhs.root != NULL) root = rhs.root->copy(); }
}







};

Main.cpp (0.84 KB)

#include "Parser.h"
#include <iostream>
#include "Evaluator.h"
#include <string>
#include <fstream>
#include "BinarySearchTree.h"

using namespace std;
int main() {
	

	
	long sum=0;
	const char *x;
	string filename;
	while(cin>>filename){
	x=filename.c_str();
	ifstream infile;
	infile.open (x, ifstream::in);
	long num;
	string line;
	const char *p;
	BinarySearchTree tree;
	 if (!infile)
     {
          cerr<<"Unable to open file"<<endl;
		           
	 }
	if (infile.is_open()){
		while (getline(infile,line)){
			p=line.c_str();
			num=atol(p);
			cout<<num<<" ";
			tree.insert(num);
			
			
		}
	}
	cout<<endl;	
	tree.display();
	
	
	sum=tree.sum();

	
	cout<<"Total number of nodes: "<<tree.size()<<endl;
	double avg;
	avg=sum/tree.size();
	cout<<"Average Search Cost: "<<avg<<endl;
	}
	return 0;
}

Edited 14 Years Ago by karolik because: n/a

karolik 0 Newbie Poster · Answer 3 · 2010-04-02T09:54:37+00:00

karolik 0 Newbie Poster

14 Years Ago

nvm

Edited 14 Years Ago by karolik because: n/a

karolik 0 Newbie Poster · Answer 4 · 2010-04-02T10:30:36+00:00

karolik 0 Newbie Poster

14 Years Ago

nvm

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

12r.txt (22.91 KB)

The attachment preview is chopped off after the first 10 KB. Please download the entire file.

karolik 0 Newbie Poster · Answer 5 · 2010-04-02T20:40:21+00:00

karolik 0 Newbie Poster

14 Years Ago

Whoops, must've missed it.

RuntimeException.h (0.42 KB)

#ifndef RUNTIMEEXCEPTION_H_
#define RUNTIMEEXCEPTION_H_

#include <string>

class RuntimeException {// generic run-time exception
 private:
   std::string errorMsg;
 public:
   RuntimeException(const std::string& err) { errorMsg = err; }
   std::string getMessage() const { return errorMsg; }
};

inline std::ostream& operator<<(std::ostream& out, const RuntimeException& e)
{
   out << e.getMessage();
   return out;
}

#endif

karolik 0 Newbie Poster · Answer 6 · 2010-04-02T21:37:29+00:00

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

karolik 0 Newbie Poster · Answer 7 · 2010-04-03T10:34:36+00:00

karolik 0 Newbie Poster

14 Years Ago

any more problems running it??

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 8 · 2010-04-03T11:27:39+00:00

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;
}

karolik 0 Newbie Poster · Answer 9 · 2010-04-03T11:40:16+00:00

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.

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 10 · 2010-04-03T11:49:20+00:00

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

karolik 0 Newbie Poster · Answer 11 · 2010-04-03T12:28:48+00:00

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.