getting the correct parent in a bst

Question

atticusr5 0 Junior Poster

12 Years Ago

Hello all,

I am trying to debug some code that I have come across. It is an array based BST, and I can not figure out why the parent's are not being recorded correctly. Essentially the first few inserts work, and then the parents become incorrect. Can anyone give me some guidance as to where to look. Any "big" errors that I have misses?

Thanks in advance, the code and data is below:

//Kaylee Nichols
//Assignment 9
//4-15-2011
//Binary Search Tree


# include <iostream>
# include <fstream>
# include <cstring>
# include <iomanip>
 #include <cstdlib>
using namespace std;

//global variables
const int PRECISION_SIZE = 2;

const int SET_WIDTH_20 = 20;
const int SET_WIDTH_10 = 10;
const int SET_WIDTH_15 = 15;


///////////////////////////////////////////////////////////////////////////
			//Structs
///////////////////////////////////////////////////////////////////////////

const int FNAME_SIZE = 6;
typedef char Fname_t[FNAME_SIZE];

const int LNAME_SIZE = 11;
typedef char Lname_t[LNAME_SIZE];

typedef int AcctID_t;
typedef double Bal_t;

//files
const int FILE_CHAR_SIZE = 51;
typedef char FileName_t[FILE_CHAR_SIZE];

typedef fstream AccountFile_t;
typedef fstream PrinterFile_t;

struct Account_t
{
        Fname_t fname;
        Lname_t lname;
        AcctID_t acctID;
        Bal_t bal;
};//end Account_t

typedef int Addr_t;

const Addr_t MAXNODES = 20;

struct Node_t
{
	Account_t Account;
	Addr_t Left;
	Addr_t Right;
};//end Node_t

typedef Node_t Tree_t[MAXNODES];
const Addr_t NIL = -1;




///////////////////////////////////////////////////////////////////////////
			//Function Prototypes
///////////////////////////////////////////////////////////////////////////
void Display (Tree_t Tree, Addr_t Root, Addr_t Avail);
void NLR (Tree_t Tree, Addr_t Root);
void Add (Tree_t & Tree, Addr_t & Root, Addr_t & Avail, Account_t TheAccount);
bool Search (Tree_t Tree, Addr_t Root, Addr_t & Parent, Account_t & TheAccount);
void Insert (Tree_t & Tree, Addr_t & Root, Addr_t Parent, Addr_t & Avail, Account_t TheAccount);
void Load (Tree_t & Tree, Addr_t & Root, Addr_t & Avail);


///////////////////////////////////////////////////////////////////////////
			//Main
///////////////////////////////////////////////////////////////////////////

int main()
{	
	Tree_t BankOfRockHill;
	Addr_t Root = NIL;
	//Addr_t Root = 0;	
	Addr_t Avail = 0;
	Load(BankOfRockHill, Root, Avail);
	//Display (BankOfRockHill, Root, Avail);
	//NLR (BankOfRH,Root, Avail);
	//LNR ();
}//end main

///////////////////////////////////////////////////////////////////////////
			//Structs
///////////////////////////////////////////////////////////////////////////


void Display (Tree_t Tree, Addr_t Root, Addr_t Avail)
{	

	cout << setw(SET_WIDTH_15) << "fname"
	     << setw(SET_WIDTH_15) << "lname" 
             << setw(SET_WIDTH_15) << "acctID"
	     << setw(SET_WIDTH_15) << "bal"
	     << setw(SET_WIDTH_15) << "Left"
	     << setw(SET_WIDTH_15) << "Right"
	     << endl;

	for (int i = 0; i <MAXNODES; i++)
	{
	cout << setw(SET_WIDTH_15) << Tree[i].Account.fname 
	     << setw(SET_WIDTH_15) << Tree[i].Account.lname 
             << setw(SET_WIDTH_15) << Tree[i].Account.acctID
	     << setw(SET_WIDTH_15) << Tree[i].Account.bal
	     << setw(SET_WIDTH_15) << Tree[i].Left
	     << setw(SET_WIDTH_15) << Tree[i].Right
	     << setw(SET_WIDTH_15) << i
	     << endl;
	}
}//end Display

void NLR (Tree_t Tree, Addr_t Root)
{
	/*if (Root != NIL)
	{
		Display(Tree, Root);//N ->
		NLR (Tree, Tree[Root].Left);//L->
		NLR(Tree, Tree[Root].Right);//R->
	}//end if*/
}//end NLR


bool Search (Tree_t Tree, Addr_t Root, Addr_t & Parent, Account_t & TheAccount)
{
	bool SearchFound = false;

		if (TheAccount.acctID < Tree[Root].Account.acctID)//search to left
		{

			Parent = Root;


			if ( ( Parent != NIL) && ( (Tree[Parent].Left != NIL) || (Tree[Parent].Right != NIL) ))
			{
				Root = Tree[Parent].Left;
				SearchFound = Search (Tree, Root, Parent, TheAccount);
			}
		}
		else if (TheAccount.acctID > Tree[Root].Account.acctID)
		{
			
			Parent = Root;

			if ( ( Parent != NIL) && ( (Tree[Parent].Left != NIL) || (Tree[Parent].Right != NIL) ))
			{
				Root = Tree[Parent].Right;
				SearchFound = Search (Tree, Root, Parent, TheAccount);
			}
		}
		
		else
		{
			//cout << "Search: Root is " << Root << "Search's else.";
			SearchFound = true;
			TheAccount = Tree[Root].Account;
		}//end if	
	return SearchFound;
}//end search



void Insert (Tree_t & Tree, Addr_t & Root, Addr_t Parent, Addr_t & Avail, Account_t TheAccount)
{
	Addr_t Curr;
	Curr = Avail;
	Avail = Avail + 1;
	Tree[Curr].Account = TheAccount;

	Tree[Curr].Left = NIL;
	Tree[Curr].Right = NIL;

	if (Parent != NIL)
	{
		if (TheAccount.acctID < Tree[Parent].Account.acctID)
		{
			Tree[Parent].Left = Curr;
		}
		else
		{
			Tree[Parent].Right =Curr;
		
		}//end inner if
	}
	else//parent == NIL, tree is empty
	{
		Root = Curr;
			
	}//end outer if


	cout << setw(SET_WIDTH_15) << Tree[Curr].Account.acctID
	     << setw(SET_WIDTH_15) << Avail -1	
	     << setw(SET_WIDTH_15) << Parent
	     << setw(SET_WIDTH_15) << Tree[Curr].Left
	     << setw(SET_WIDTH_15) << Tree[Curr].Right
	     << endl;

}//end insert


void Add (Tree_t & Tree, Addr_t & Root, Addr_t & Avail, Account_t TheAccount)
{
	Addr_t Parent;
	Parent = NIL;	
	bool AddFound = false;
	//cout << "Root is " << Root << "This is add." << endl;
	AddFound = Search (Tree, Root, Parent, TheAccount);
	//cout << "Root is " << Root cout<<"root: "<<Root<<" Avail: "<<Avail<<endl;<< "IF you see this, then search worked." << endl;
	if (!AddFound)
	{
		//cout << "Account Inserted" << endl;
		Insert (Tree, Root, Parent, Avail, TheAccount);
	}
	else
	{
		cout << "Duplicate. Account Not inserted." << endl;
	}//end if
}//end add


void Load (Tree_t & Tree, Addr_t & Root, Addr_t & Avail)
{
	FileName_t FileName;
	AccountFile_t AccountFile;

	for (int i = 0; i <= MAXNODES; i++)
	{
		Tree[i].Right = NIL;
		Tree[i].Left = NIL;
	}

	cout << "Please enter the name of the accout file to read: ";
	cin >> FileName;

	AccountFile.open(FileName, ios::in);

	Account_t TempAccount;
	
	if ( AccountFile.fail() )
	{
		cout << "Account File did not open." << endl;
		exit(0);
	}//end load

	cout << setw(SET_WIDTH_15) << "acctID"
	     << setw(SET_WIDTH_15) << "Avail"	
	     << setw(SET_WIDTH_15) << "Parent"
	     << setw(SET_WIDTH_15) << "Left"
	     << setw(SET_WIDTH_15) << "Right"
	     << endl;

	

	AccountFile >> TempAccount.fname >> TempAccount.lname >> TempAccount.acctID >> TempAccount.bal;

	while (!AccountFile.eof())
	{	
		Add (Tree, Root, Avail, TempAccount);
		AccountFile >> TempAccount.fname >> TempAccount.lname >> TempAccount.acctID >> TempAccount.bal;

	}//end while	

	
}//end load

data:

Kayle Nichols 39867 1500.00
Amy Campbell 60794 454.33
Brian Campbell 58674 49684.44
Blake Campbell 58392 68.99
Cindy Prince 23453 66666.33
Dale Nichols 39852 5632.22
Marty Long 56875 4432222.54
Alex Long 53433 685.55
Alan Long 11009 5634.33
Laura Nichols 45832 100000.00
Kelsy Nichols 56343 684894.33
Kari Chris 39485 354.33
Dana Hall 56786 2345.44

c++

4 Contributors
3 Replies
146 Views
17 Hours Discussion Span
Latest Post 12 Years Ago Latest Post by mike_2000_17

All 3 Replies

Ancient Dragon 5,243 Achieved Level 70

12 Years Ago

>>typedef int Addr_t;

Why are you assuming addresses are integers? They aren't. Redefine that as typedef char* Addr_t; or typedef Tree* Addr_t , or whatever data type it is. If you need a generic pointer than typedef void* Addr_t; should do it, then you can typecast it to the appropriate type.

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.

nezachem 616 Practically a Posting Shark · Answer 1 · 2011-04-18T01:09:35+00:00

The problem is in the Search function, specifically at lines 144 and 155. Can you explain the logic there?

mike_2000_17 2,669 21st Century Viking Team Colleague Featured Poster · Answer 2 · 2011-04-18T08:33:19+00:00

The error is in lines 144 and 155. In the first case, you are accessing the Left node, but the checked condition involved a logical OR expression, which means if Right node is valid (not NIL) then you proceed to access the Left node which may or may not be valid. Vice versa on line 155. Take out the check of the Right node on line 144 and take out the check of the Left node on line 155. That should help.

getting the correct parent in a bst

Recommended Answers Collapse Answers

All 3 Replies

Recommended Answers