Binary Search Tree Stack Overflow

Question

atticusr5 0 Junior Poster

14 Years Ago

Ok so I am a total newbie, and for our last programing assignment in my class we are going over Binary Search Trees. Out assignment is to take an older program and make it into a binary search tree. I am using Visual Studio and I have gotten past all the "known" build errors, and now I am incountering a stack overflow error when I run the debugger at this point in my code:

int cAccount::compID2ID(cAccount NewAccount)
{ //<---breaks here
	int count;
       count=0;

I read online and it said it was a memory error, so am I not declaring enough? I'm very lost the binary tree implementations in general and if anyone sees other errors please let me know.

Here is my source code and datafile:

Source code:

/*
	Devang N. Joshi
	CSCI 208
	Binary Search Tree
*/
//************************************************************************
//					Header Files
//************************************************************************
#include <iostream>   
#include <iomanip>   
#include <fstream>   
#include <cstring>  
using namespace std;
//************************************************************************  
//     			    Global Variables  
//************************************************************************
const int NAMESIZE=25;
const int FILENAME=51;
const int MAXNODESIZE=200;       
  
typedef char Name_t[NAMESIZE];
typedef char Filename_t[FILENAME];
typedef int ID_t;
typedef double Bal_t;
typedef fstream Infile_t;
typedef fstream Outfile_t;
typedef int Addr_t;       
 
const Addr_t NIL=-1;
const Addr_t END=-2;    
//************************************************************************
//                 Class Declerations 
//************************************************************************
class cAccount
{
	private:
		Name_t fname;
      	Name_t lname;
      	ID_t aID;
      	Bal_t aBal; 

	public:
		cAccount();                       
      	void Read (Infile_t &Infile);     
      	void Print (Outfile_t &Outfile);  
      	void Display();                   
      	int compID2ID(cAccount NewAccount);      		   
};// end cAccount       
//************************************************************************
//                 Struct Declerations
//************************************************************************
struct Node_t
{
	cAccount Account;
    Addr_t Left;  
	Addr_t Right;
	Addr_t Root;

};// end Node_t   
//************************************************************************
//				   Array Decleration
//************************************************************************
typedef Node_t Tree_t[MAXNODESIZE];    
//************************************************************************
//      	Class Function Implementations     
//************************************************************************
cAccount::cAccount()
{
	strcpy(fname,"");  //<--default constructor
    strcpy(lname,"");                                                
    aID=0;
    aBal=0;  
}// end cAccount::cAccount       
//________________________________________________________________________
void cAccount::Read(Infile_t &Infile)
{ Infile>>aID>>lname>>fname>>aBal;}// end cAccount::Read              
//________________________________________________________________________
void cAccount::Print(Outfile_t &Outfile)  
{
	Outfile<<setw(10)<<"ACCOUNT-ID: "<<aID<<endl; 
    Outfile<<setw(10)<<"ACCOUNT NAME: "<<lname<<","<<fname<<endl;      
    Outfile<<setw(10)<<"ACCOUNT BALANCE: $"<<aBal<<endl; 
    Outfile<<"------------------------------------------------"<<endl;  
}// end cAccount::Print           
//________________________________________________________________________
void cAccount::Display()
{
	cout<<setw(10)<<"ACCOUNT-ID: "<<aID<<endl;
    cout<<setw(10)<<"ACCOUNT NAME: "<<lname<<","<<fname<<endl;        
    cout<<setw(10)<<"ACCOUNT BALANCE: $"<<aBal<<endl;
    cout<<"------------------------------------------------"<<endl;       
}// end cAccount::Display       
//________________________________________________________________________
int cAccount::compID2ID(cAccount NewAccount)
{
	int count;
    count=0;       

    if(this->aID > NewAccount.aID)
    { count=-1;}// end if     

	else if(this->aID < NewAccount.aID)       
    { count=1; }// end else if       

    else
    { count=0;}//end else       

    return count;
}// end cAccount::compID2ID    
//************************************************************************
//     				       Function Prototypes 
//************************************************************************
void Insert(Tree_t &Tree, Addr_t &Root,Addr_t &Avail,cAccount NewAccount,Addr_t Parent); 
bool Search4Parent(Tree_t Tree, Addr_t Root, cAccount NewAccount, Addr_t &Parent);   
void Display(Tree_t Tree, Addr_t Root, Addr_t Avail);
void Load(Tree_t &Tree,Addr_t &Root,Addr_t &Avail);  
void Print(Tree_t Tree,Addr_t Root,Addr_t Avail); 
//************************************************************************
//  					       MAIN       
//************************************************************************
int main()
{
	 
    Addr_t Root; 
    Root=NIL; 
    Tree_t Tree; 
    Addr_t Avail;
    cAccount Account;
    Infile_t Infile;

    /* FUNCTION CALLS */

    Load(Tree,Root,Avail);
    Display(Tree,Root,Avail);
    Print(Tree,Root,Avail);
      	  
    return 0;
}// end main 
//************************************************************************ 
//     				   Function Implementations  
//************************************************************************
void Insert(Tree_t &Tree, Addr_t &Root,Addr_t &Avail,cAccount NewAccount,Addr_t Parent)
{
	Addr_t Curr;
    Curr=Avail;
    Avail=Avail+1;
    Tree[Curr].Account=NewAccount;
	Tree[Curr].Left=NIL;
	Tree[Curr].Right=NIL;
 
    if(Parent!=NIL)
    {
		if(Tree[Parent].Account.compID2ID(NewAccount)>0)
		{
			Tree[Parent].Left=Curr;
		}
		else if(Tree[Parent].Account.compID2ID(NewAccount)<0)
		{
			Tree[Parent].Right=Curr;
		}
		else
		{
			cout<<"DUPLICATE KEY...MOVING TO NEXT VALUE"<<endl;
		}//innner if
	}//outer if
};// end Insert       
//________________________________________________________________________
bool Search4Parent(Tree_t Tree, Addr_t Root, cAccount NewAccount, Addr_t &Parent)
{
	Addr_t Curr=Root;
	bool Found=false;

	if(Tree[Curr].Account.compID2ID(NewAccount)<0)
	{
		Parent=Curr;
		Search4Parent(Tree,Tree[Root].Left,NewAccount,Parent);
	}
	else if(Tree[Curr].Account.compID2ID(NewAccount)>0)
	{
		Parent=Curr;
		Search4Parent(Tree,Tree[Root].Right,NewAccount,Parent);
	}
	else
	{
		NewAccount=Tree[Curr].Account;
		Found=true;
	}

	return Found;
}// end Search4Pred       
//________________________________________________________________________
void Load(Tree_t &Tree,Addr_t &Root,Addr_t &Avail)
{
	Filename_t Filename;
    Infile_t Infile;
    Addr_t Parent; 
    Root=NIL; 
    Avail=0;
    bool Found;
    cout<<"Program Starting.........."<<endl;
    cout<<"Begining Load.........."<<endl<<endl;
    cout<<"Enter the name of the data file to be used:"<<endl;  
    cin>>Filename;
    Infile.open(Filename,ios::in);
    cAccount NewAccount; 
    NewAccount.Read(Infile);
    while(!Infile.eof())
    {
		Parent=NIL;

		Found=Search4Parent(Tree,Root,NewAccount,Parent);

		if(Found=true)
	    {
			cout<<"ERROR...DUPLICATE VALUE FOUND..."<<endl;
			cout<<"THIS VALUE WILL NOT BE ADDED..."<<endl;
			cout<<"MOVING TO NEW VALUE..."<<endl;
		}
		else
		{
			Insert(Tree,Root,Avail,NewAccount,Parent);
		}
		NewAccount.Read(Infile);
	}//while
 
    Infile.close();
    cout<<"Read Complete........."<<endl;
	cout<<"Load Complete........."<<endl;
};//end load
//________________________________________________________________________
void Display(Tree_t Tree, Addr_t Root, Addr_t Avail)
{
	Addr_t Curr;
    Curr=Root;
    Name_t choice;
    cout<<"Would you like to view the output file?"<<endl;
    cout<<"(YES or NO)"<<endl;
    cin>>choice;

    if(strcmp(choice,"YES")==0||strcmp(choice,"Yes")==0||strcmp(choice,"yes")==0) 
    {
		cout<<setw(20)<<"ACCOUNT-DATA"<<endl<<endl;       

      	while(Curr!=NIL)                                             
      	{
			Tree[Curr].Account.Display();
      	    Curr=Tree[Curr].Left;
			Curr=Tree[Curr].Right;

      	}//end while

		cout<<endl;
		cout<<"Moving to next process.........."<<endl<<endl;

     }
     else
     {
		 cout<<"Very Well.........."<<endl;
		 cout<<"Moving to next process.........."<<endl<<endl;
     }//end if
};// end Display
//________________________________________________________________________
void Print(Tree_t Tree,Addr_t Root,Addr_t Avail)
{
	Addr_t Curr;
    Curr=Root; 
    Filename_t Filename;
    Outfile_t Outfile;
    cout<<"Enter the name of the output file: "<<endl;
    cin>>Filename; 
    Outfile.open(Filename,ios::out);
    Outfile<<setw(20)<<"ACCOUNT-DATA"<<endl<<endl;

    while(Curr!=NIL)
    {
		Tree[Curr].Account.Print(Outfile);
      	Curr=Tree[Curr].Left;
		Curr=Tree[Curr].Right;

    }//end while    

    Outfile.close();
    cout<<"Write Sucessful.........."<<endl<<endl;
};// end Print
//************************************************************************
				       /* END OF SOURCE CODE */
//************************************************************************

Datafile:

31951
Walker
John
1000.98
69537
Patton
George
876.07
28542
Colt
Samuel
1234.56
28325
Bond
James
6798.00
68128
Hamilton
Alex
9000.00
44206
Lincoln
Abe
00.01
13108
Armstrong
Louis
750.00
41727
Gotti
John
5500.60
21158
Lennon
John
6969.69
52019
McCarthy
Joseph
742.02
37823
Stewart
Jon
29.98
70109
Schrute
Dwight
00.00
74746
Bob
Billy
50.50
18211
Pitt
Brad
2056.89
19724
Blitzer
Wolf
3009.10
49926
Dillinger
John
862.43

c++

3 Contributors
6 Replies
1K Views
4 Days Discussion Span
Latest Post 14 Years Ago Latest Post by mattjbond

MrSpigot 64 Junior Poster

14 Years Ago

I've barely glanced at that code but stack overflow in a binary tree application is likely to be a recursion error. i.e. one of your methods is calling itself (which is fine) but the exit condition which stops it calling itself is never being reached. See if you can find that condition and work out why it's ignored.

mattjbond 54 Junior Poster

14 Years Ago

This will likely be a duff pointer. Check your pointers...

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.

atticusr5 0 Junior Poster · Answer 1 · 2010-04-16T18:20:00+00:00

yea i ran the code again and i got an infinite loop of the error message from my load function, so i will look into it all, thanks for that guidance.

atticusr5 0 Junior Poster · Answer 2 · 2010-04-18T22:11:24+00:00

Ok so now I think I am past the stack overflow, and now I am getting a read access violation.

Here is the code:

/*
	Devang N. Joshi
	CSCI 208
	Binary Search Tree
*/
//************************************************************************
//					Header Files
//************************************************************************
#include <iostream>   
#include <iomanip>   
#include <fstream>   
#include <cstring>  
using namespace std;
//************************************************************************  
//     			    Global Variables  
//************************************************************************
const int NAMESIZE=25;
const int FILENAME=51;
const int MAXNODESIZE=200;       
  
typedef char Name_t[NAMESIZE];
typedef char Filename_t[FILENAME];
typedef int ID_t;
typedef double Bal_t;
typedef fstream Infile_t;
typedef fstream Outfile_t;
typedef int Addr_t;       
 
const Addr_t NIL=-1;
const Addr_t END=-2;    
//************************************************************************
//                 Class Declerations 
//************************************************************************
class cAccount
{
	private:
		Name_t fname;
      	Name_t lname;
      	ID_t aID;
      	Bal_t aBal; 

	public:
		cAccount();                       
      	void Read (Infile_t &Infile);     
      	void Print (Outfile_t &Outfile);  
      	void Display();                   
      	int compID2ID(cAccount NewAccount);      		   
};// end cAccount       
//************************************************************************
//                 Struct Declerations
//************************************************************************
struct Node_t
{
	cAccount Account;
    Addr_t Left;  
	Addr_t Right;

};// end Node_t   
//************************************************************************
//				   Array Decleration
//************************************************************************
typedef Node_t Tree_t[MAXNODESIZE];    
//************************************************************************
//      	Class Function Implementations     
//************************************************************************
cAccount::cAccount()
{
	strcpy(fname,"");  //<--default constructor
    strcpy(lname,"");                                                
    aID=0;
    aBal=0;  
}// end cAccount::cAccount       
//________________________________________________________________________
void cAccount::Read(Infile_t &Infile)
{ Infile>>aID>>lname>>fname>>aBal;}// end cAccount::Read              
//________________________________________________________________________
void cAccount::Print(Outfile_t &Outfile)  
{
	Outfile<<setw(10)<<"ACCOUNT-ID: "<<aID<<endl; 
    Outfile<<setw(10)<<"ACCOUNT NAME: "<<lname<<","<<fname<<endl;      
    Outfile<<setw(10)<<"ACCOUNT BALANCE: $"<<aBal<<endl; 
    Outfile<<"------------------------------------------------"<<endl;  
}// end cAccount::Print           
//________________________________________________________________________
void cAccount::Display()
{
	cout<<setw(10)<<"ACCOUNT-ID: "<<aID<<endl;
    cout<<setw(10)<<"ACCOUNT NAME: "<<lname<<","<<fname<<endl;        
    cout<<setw(10)<<"ACCOUNT BALANCE: $"<<aBal<<endl;
    cout<<"------------------------------------------------"<<endl;       
}// end cAccount::Display       
//________________________________________________________________________
int cAccount::compID2ID(cAccount NewAccount)
{
	int count;
    count=0;       

    if(this->aID > NewAccount.aID)
    { count=-1;}// end if     

	else if(this->aID < NewAccount.aID)       
    { count=1; }// end else if       

    else
    { count=0;}//end else       

    return count;
}// end cAccount::compID2ID    
//************************************************************************
//     				       Function Prototypes 
//************************************************************************
void Insert(Tree_t &Tree, Addr_t &Root, Addr_t &Avail, cAccount Account, Addr_t Parent); 
bool Search4Parent(Tree_t Tree, Addr_t Root, cAccount NewAccount, Addr_t &Parent);   
void Display(Tree_t Tree, Addr_t Root, Addr_t Avail);
void Load(Tree_t &Tree,Addr_t &Root,Addr_t &Avail);  
void Print(Tree_t Tree,Addr_t Root,Addr_t Avail); 
//************************************************************************
//  					       MAIN       
//************************************************************************
int main()
{
	 
    Addr_t Root; 
    Root=NIL; 
    Tree_t Tree; 
    Addr_t Avail;
    cAccount Account;
    Infile_t Infile;

    /* FUNCTION CALLS */

    Load(Tree,Root,Avail);
    Display(Tree,Root,Avail);
    Print(Tree,Root,Avail);
      	  
    return 0;
}// end main 
//************************************************************************ 
//     				   Function Implementations  
//************************************************************************
void Insert(Tree_t &Tree, Addr_t &Root, Addr_t &Avail, cAccount NewAccount, Addr_t Parent)

{
	Addr_t Curr;
	Curr = Avail;
	Avail = Avail +1;
	Tree[Curr].Account = NewAccount;
	Tree[Curr].Left = NIL;
	Tree[Curr].Right = NIL;

	if(Parent != NIL)
	{
		if(Tree[Parent].Account.compID2ID(NewAccount) > 0)
	    {Tree[Parent].Left = Curr;}
	    else if(Tree[Parent].Account.compID2ID(NewAccount)<0)
	    {Tree[Parent].Right = Curr;}
	    else
	    { cout<<"DUPLICATE KEY"<<endl;}//if/else
	}//if
}//Insert 
//________________________________________________________________________
bool Search4Parent(Tree_t Tree, Addr_t Root, cAccount NewAccount, Addr_t &Parent)
{
	bool Found=false;
	Addr_t Curr=Root;
	Parent=NIL;

	

	if(Tree[Curr].Account.compID2ID(NewAccount)<0)
	{
		Parent=Curr;
		Search4Parent(Tree,Tree[Root].Left,NewAccount,Parent);
	}
	else if(Tree[Curr].Account.compID2ID(NewAccount)>0)
	{
		Parent=Curr;
		Search4Parent(Tree,Tree[Root].Right,NewAccount,Parent);
	}
	else
	{
		NewAccount=Tree[Curr].Account;
		Found=true;
	}

	return Found;
}// end Search4Pred       
//________________________________________________________________________
void Load(Tree_t &Tree, Addr_t &Root, Addr_t &Avail)
{
	Addr_t Parent;
	bool Found;
	Infile_t Infile;
	char Filename[50];

	Root = NIL;
	Avail = 0;

	cout<<"Enter input data file name: "<<endl;
	cin>>Filename;

	Infile.open(Filename, ios::in);
	cAccount NewAccount;
	NewAccount.Read(Infile);

	while(!Infile.eof())
	{
		Parent = NIL;
		Found = Search4Parent(Tree,Root,NewAccount,Parent);  //check order of parameters 
			
			if(Found==true)
			{ cout<<"Duplicate Key Error"<<endl;}
			else
			{Insert(Tree,Root,Avail,NewAccount,Parent);}//if
	
			NewAccount.Read(Infile);
	}//end while
	Infile.close();
}//Load	
//________________________________________________________________________
void Display(Tree_t Tree, Addr_t Root, Addr_t Avail)
{
	Addr_t Curr;
    Curr=Root;
    Name_t choice;
    cout<<"Would you like to view the output file?"<<endl;
    cout<<"(YES or NO)"<<endl;
    cin>>choice;

    if(strcmp(choice,"YES")==0||strcmp(choice,"Yes")==0||strcmp(choice,"yes")==0) 
    {
		cout<<setw(20)<<"ACCOUNT-DATA"<<endl<<endl;       

      	while(Curr!=NIL)                                             
      	{
			Tree[Curr].Account.Display();
      	    Curr=Tree[Curr].Left;
			Curr=Tree[Curr].Right;

      	}//end while

		cout<<endl;
		cout<<"Moving to next process.........."<<endl<<endl;

     }
     else
     {
		 cout<<"Very Well.........."<<endl;
		 cout<<"Moving to next process.........."<<endl<<endl;
     }//end if
};// end Display
//________________________________________________________________________
void Print(Tree_t Tree,Addr_t Root,Addr_t Avail)
{
	Addr_t Curr;
    Curr=Root; 
    Filename_t Filename;
    Outfile_t Outfile;
    cout<<"Enter the name of the output file: "<<endl;
    cin>>Filename; 
    Outfile.open(Filename,ios::out);
    Outfile<<setw(20)<<"ACCOUNT-DATA"<<endl<<endl;

    while(Curr!=NIL)
    {
		Tree[Curr].Account.Print(Outfile);
      	Curr=Tree[Curr].Left;
		Curr=Tree[Curr].Right;

    }//end while    

    Outfile.close();
    cout<<"Write Sucessful.........."<<endl<<endl;
};// end Print
//************************************************************************
				       /* END OF SOURCE CODE */
//************************************************************************

Here is where the code is specifically breaking according to the debugger:

int cAccount::compID2ID(cAccount NewAccount)
{
	int count;
    count=0;       

    if(this->aID > NewAccount.aID) //<--breaks here
    { count=-1;}// end if

atticusr5 0 Junior Poster · Answer 3 · 2010-04-19T22:17:32+00:00

This will likely be a duff pointer. Check your pointers...

what does that mean?

mattjbond 54 Junior Poster · Answer 4 · 2010-04-20T13:47:12+00:00

You are most likely attempting to dereference a null pointer.