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