c++ program question: DESCRIPTION General Write a program that will maintain ban
ID: 3701968 • Letter: C
Question
c++ program question:
DESCRIPTION
General
Write a program that will maintain bank accounts using a binary search tree. It will also maintain a log file (Log.txt). Initially, the program will input bank accounts from an unordered master file (Master.txt) and will create the binary search tree representing the accounts. This needn’t be a balanced tree.
After building the tree, the program will output the contents of the binary search tree to the log file (Log.txt).
After the tree is built, it will read transactions from a transaction file (Transaction.txt) one at a time and perform the transaction on the binary search tree.
For each transaction, it will log the following to the log file: It will output a line containing the contents of the transaction to be performed. After the transaction is completed, it will output the contents of the whole binary search tree to the log file.
After all transactions are done, it will store the updated tree into an ordered master file (OrderedMaster.txt) in order of account numbers and will delete the tree.
Then it will read the accounts from the ordered master file (OrderedMaster.txt) and create a balance binary search tree.
After the balanced tree is built, it will log the contents of the balanced binary search tree to the log file.
Files
The program will make use of the following files in performing its tasks. Each of the file and the way it is used is described below:
Master File
The master (Master.txt) file will contain the account data in no particular order. For each account, it will contain the account id, the account name and the current balance.
The program will read data from the master (Master.txt) file and build a binary search tree. This tree need not be a balanced tree.
Transaction File
The transaction file (Transaction.txt) will contain a set of transactions. Each transaction will consist of a one letter transaction type, an account id, the account name and a plus or minus amount. The transaction types will include the following:
I will imply an insert transaction.
U will imply an update transaction.
D will imply a delete transaction
After building the binary search tree as described above, the program will input transactions from the transaction file one at a time and will update the accounts accordingly.
For an Insert (I) transaction, the program will add a new account (node) in the binary search tree.
For a Delete (D) transaction, the program will delete an account (node) from the binary search tree.
For an Update (U) transaction, the program will update the balance in the corresponding account (node) in the binary search tree. For a plus amount, it will add the given amount to the existing balance. For a minus amount, it will subtract the given amount from the existing balance.
Ordered Master File
Initially, the ordered master (OrderedMaster.txt) file will not exist.
When all transactions are completed, the program will output the contents of the binary search tree to the ordered master (OrderedMaster.txt) file using In-Order traversal (see sample code below). This will result in the file OrderedMaster.txt containing the account data in order by account id. For each account, it will contain the account id, the account name and the current balance.
Log File
Log File Contents
The program will log information to a log (Log.txt) file as described below.
Before starting any updates, the program will output the following to the log (Log.txt) file:
It will output the contents of the whole binary search tree.
Then for each update, it will output the following to the log file:
Before the update, it will output a line containing the contents of the update to be performed.
After the update, it will output the contents of the whole binary search tree.
After all updates are completed, it will store the contents of the tree to the ordered master (OrderedMaster.txt) file using In-Order traversal and will delete the existing tree.
Then it will input the contents of the tree from the ordered master (OrderedMaster.txt) file and build a new balanced binary search tree.
After building the balanced binary search tree, it will output the following to the log file.
the contents of the whole balanced binary search tree.
Log File Format
For logging the contents of an update, it will output one line of text containing transaction type, account id, account name and the amount value to the log (Log.txt) file.
For logging the contents of the whole binary search tree, it will output the contents of the binary search tree to the log (Log.txt) file in Reverse In-Order traversal using levels It will output only the id and the balance for each account. For each account, it will output two lines: one line for account id and the second for account balance. It will output the tree making using of the level information so that the output will appear as a tree lying sideways (see sample code below).
TEST DATA
Use the data below for a test run.
Master File:
27183 Teresa Wong 1234.56
12345 Jeff Lee 211.22
31456 Jack Smith 1200.00
14142 James Bond 1500.00
31623 Norris Hunt 1500.00
10203 Mindy Ho 2000.00
20103 Ed Sullivan 3000.00
30102 Ray Baldwin 3824.36
30201 Susan Woo 9646.75
22345 Norma Patel 2496.24
Transaction File
U 31623 Norris Hunt -1500.00
I 20301 Joe Hammil +500.00
I 31416 Becky Wu +100.00
U 10203 Mindy Ho -2000.00
U 14142 James Bond +1500.00
U 27183 Teresa Wong -1234.56
I 10101 Judy Malik +1000.00
I 32123 John Doe +900.00
I 22222 Joanne Doe +2750.02
D 31623 Norris Hunt 0
D 10203 Mindy Ho 0
D 27183 Teresa Wong 0
IMPLEMENTATION
Bianary Search Tree
Use a binary search tree for keeping accounts.
Class
Encapsulate the binary search tree in a class that provides the methods needed.
Account Id
Use the data type long for storing account id.
Algorithm For Storing And Restoring The Tree
When all transactions are completed, the program will do the following:
Determine the total number of nodes in the tree (i.e. node count).
Save the node count in ordered master (OrderedMaster.txt) file.
Following the count, save the contents of the updated binary search tree in ordered master (OrderedMaster.txt) file using In-order traversal by id. (Do not save the link values).
Make the root of the tree equals NULL. This will de-link the whole tree from the root.
Input the node count from the ordered master (OrderedMaster.txt) file.
Using the node count and data from the ordered master (OrderedMaster.txt) file, create a new balanced binary search tree.
Log the contents of the binary search tree in Reverse In-order Traversal. Use a different amount of indentation at each level of the tree so that data will appear in the file as a tree lying sideways. For each node, log only the id and the balance.
SAMPLE CODE
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
using namespace std;
struct RecType
{
int id;
string firstName;
string lastName;
double amount;
};
struct NodeType;
typedef NodeType * NodePtr;
struct NodeType
{
int id;
string firstName;
string lastName;
double amount;
NodePtr llink;
NodePtr rlink;
};
class BinTree
{
private:
NodePtr root;
ifstream fin;
ofstream fout;
void rinsert (NodePtr & nodep, RecType rec);
void rupdate (NodePtr nodep, RecType rec );
void rremove (NodePtr & nodep, RecType rec );
void rdisplay (NodePtr nodep, int level);
void rfdisplay (NodePtr nodep, int level, ofstream & fout);
void rstore (NodePtr nodep);
void rrestore (NodePtr & nodep, int count);
int rcountNodes (NodePtr nodep);
public:
BinTree ( );
void insert ( RecType rec );
void update ( RecType rec );
void remove ( RecType rec );
void display ();
void fdisplay (ofstream & fout);
void store ( );
void restore ();
int countNodes ();
};
//The constructor
BinTree ::BinTree ( )
{
root = NULL;
}
//Inserting a node in the tree
void BinTree ::insert (RecType rec )
{
rinsert (root, rec);
}
void BinTree ::rinsert (NodePtr & nodeptr, RecType rec)
{
if (nodeptr == NULL) // reached not found
{
// create the node and link it
nodeptr = new NodeType;
nodeptr->id = rec.id;
nodeptr->firstName = rec.firstName;
nodeptr->lastName = rec.lastName;
nodeptr->amount = rec.amount;
nodeptr->llink = NULL;
nodeptr->rlink= NULL;
}
else if (rec.id < nodeptr->id)
rinsert(nodeptr->llink, rec);
else
rinsert (nodeptr->rlink, rec);
}
//Updating a node in the tree
void BinTree ::update (RecType rec )
{
rupdate (root, rec);
}
void BinTree ::rupdate (NodePtr nodep, RecType rec)
{
}
//Removing a node from the tree
void BinTree ::remove (RecType rec )
{
rremove (root, rec);
}
void BinTree ::rremove (NodePtr & nodep, RecType rec)
{
}
//Displaying the tree in reverse in order traversal with levels
void BinTree::display ()
{
rdisplay (root, 1);
}
void BinTree::rdisplay (NodePtr nodep, int level)
{
if (nodep != NULL)
{
rdisplay (nodep->rlink, level + 1);
cout << setw (7 * level) << nodep->id <<endl;
rdisplay (nodep->llink, level + 1);
}
}
//Logging the tree in reverse In-order traversal with levels
void BinTree::fdisplay (ofstream & fout)
{
rfdisplay (root, 1, fout);
}
void BinTree::rfdisplay (NodePtr nodep, int level, ofstream & fout)
{
if (nodep != NULL)
{
rfdisplay (nodep->rlink, level + 1,fout);
fout << setw (7 * level) << nodep->id <<endl;
rfdisplay (nodep->llink, level + 1,fout);
}
}
//Storing the tree to a file OrderedMaster.txt
void BinTree::store ()
{
fout.open("OrderedMaster.txt",ios::out );
//save the node count as the first number in the file
int count = countNodes();
fout << count << endl;
//save the tree
rstore (root);
fout.close();
}
void BinTree::rstore (NodePtr nodep)
{
if (nodep != NULL)
{
rstore (nodep->llink);
fout << nodep->id << " "
<< nodep->firstName << " "
<< nodep->lastName << " "
<< nodep->amount << endl;
rstore (nodep->rlink);
}
}
//Restoring the tree from a file OrderedMaster.txt
void BinTree::restore ()
{
fin.open("OrderedMaster.txt",ios::in );
//input node count. This was stored as the first number in file.
int count;
fin >> count;
//restore the tree
rrestore (root,count);
fin.close();
}
void BinTree::rrestore (NodePtr & nodep, int count)
{
Explanation / Answer
#include <iostream>
#include <fstream>
#include <iomanip> //Manipulating input output
#include <string>
using namespace std;
struct RecType
{
int id;
string firstName;
string lastName;
double amount;
};
struct NodeType;
typedef NodeType * NodePtr;
struct NodeType
{
int id;
string firstName;
string lastName;
double amount;
NodePtr llink;
NodePtr rlink;
};
class BinTree
{
private:
NodePtr root;
ifstream fin; //file handling class
ofstream fout;//file handling class
void rinsert (NodePtr & nodep, RecType rec); //method for inserting the Node(NodePtr will point to the current node) with its depth and its type
void rupdate (NodePtr nodep, RecType rec ); //method for updating the Node with its depth and node type
void rremove (NodePtr & nodep, RecType rec ); //method for deleting the node along with its contents
void rdisplay (NodePtr nodep, int level);//method for displaying the contents on the log.txt
void rfdisplay (NodePtr nodep, int level, ofstream & fout);
void rstore (NodePtr nodep);
void rrestore (NodePtr & nodep, int count);
int rcountNodes (NodePtr nodep);
public:
BinTree ( );
void insert ( RecType rec );
void update ( RecType rec );
void remove ( RecType rec );
void display ();
void fdisplay (ofstream & fout);
void store ( );
void restore ();
int countNodes ();
};
//The constructor
BinTree ::BinTree ( )
{
root = NULL;
}
//Inserting a node in the tree
void BinTree ::insert (RecType rec )
{
rinsert (root, rec);
}
void BinTree ::rinsert (NodePtr & nodeptr, RecType rec)
{
if (nodeptr == NULL) // reached not found
{
// create the node and link it
nodeptr = new NodeType;
nodeptr->id = rec.id;
nodeptr->firstName = rec.firstName;
nodeptr->lastName = rec.lastName;
nodeptr->amount = rec.amount;
nodeptr->llink = NULL;
nodeptr->rlink= NULL;
}
else if (rec.id < nodeptr->id)
rinsert(nodeptr->llink, rec);
else
rinsert (nodeptr->rlink, rec);
}
//Updating a node in the tree
void BinTree ::update (RecType rec )
{
rupdate (root, rec);
}
void BinTree ::rupdate (NodePtr nodep, RecType rec)
{
}
//Removing a node from the tree
void BinTree ::remove (RecType rec )
{
rremove (root, rec);
}
void BinTree ::rremove (NodePtr & nodep, RecType rec)
{
}
//Displaying the tree in reverse in order traversal with levels
void BinTree::display ()
{
rdisplay (root, 1);
}
void BinTree::rdisplay (NodePtr nodep, int level)
{
if (nodep != NULL)
{
rdisplay (nodep->rlink, level + 1);
cout << setw (7 * level) << nodep->id <<endl;
rdisplay (nodep->llink, level + 1);
}
}
//Logging the tree in reverse In-order traversal with levels
void BinTree::fdisplay (ofstream & fout)
{
rfdisplay (root, 1, fout);
}
void BinTree::rfdisplay (NodePtr nodep, int level, ofstream & fout)
{
if (nodep != NULL)
{
rfdisplay (nodep->rlink, level + 1,fout);
fout << setw (7 * level) << nodep->id <<endl;
rfdisplay (nodep->llink, level + 1,fout);
}
}
//Storing the tree to a file OrderedMaster.txt
void BinTree::store ()
{
fout.open("OrderedMaster.txt",ios::out );
//save the node count as the first number in the file
int count = countNodes();
fout << count << endl;
//save the tree
rstore (root);
fout.close();
}
void BinTree::rstore (NodePtr nodep)
{
if (nodep != NULL)
{
rstore (nodep->llink);
fout << nodep->id << " "
<< nodep->firstName << " "
<< nodep->lastName << " "
<< nodep->amount << endl;
rstore (nodep->rlink);
}
}
//Restoring the tree from a file OrderedMaster.txt
void BinTree::restore ()
{
fin.open("OrderedMaster.txt",ios::in );
//input node count. This was stored as the first number in file.
int count;
fin >> count;
//restore the tree
rrestore (root,count);
fin.close();
}
void BinTree::rrestore (NodePtr & nodep, int count)
{
if (count > 0)
{
//create a node
nodep = new NodeType;
nodep->llink = NULL;
nodep->rlink = NULL;
//create and fill the left subtree
if ( (count % 2) == 0)
rrestore (nodep->llink, ((count-1)/2) + 1);
else
rrestore (nodep->llink, count/2);
//fill in the node
fin >> nodep->id >> nodep->firstName >> nodep->lastName >> nodep->amount;
//create and fill the right subtree
if ( (count % 2) == 0)
rrestore (nodep->rlink, ((count-1)/2) );
else
rrestore (nodep->rlink, count/2);
}
}
//Counting nodes
int BinTree::rcountNodes (NodePtr nodep )
{
if (nodep != NULL)
{
return (rcountNodes (nodep->llink) + rcountNodes(nodep->rlink) + 1);
}
else
return 0;
}
int BinTree::countNodes ()
{
return rcountNodes (root);
}
void main ( )
{
BinTree tree;
ofstream fout (c:\Log.txt”);
ifstream finMaster (c:\Master.txt”);
ifstream finTransaction (c:\Transaction.txt”);
ifstream finOrderedMaster (c:\OrderedMaster.txt”);
RecType r;
finMaster >> r.id;
while (!finMaster.eof( ) )
{
finMaster >> r.firstName;
finMaster >> r.lastName;
finMaster >> r.amount;
tree.insert(r);
finMaster >> r.id;
}
//display the tree
tree.display();
tree.fdisplay(fout);
//store the tree
tree.store();
//restore the tree
tree.restore();
//display the restored tree.
tree.display();
tree.fdisplay(fout);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.