Derek Elder: start of page - work to be done

2007-12-18T01:10:23Z

start of page - work to be done

New page

__TOC__
==Tree.h==
<pre>
#include <iostream>
using namespace std;

class Student
{
private:
string m_name;
int m_age;
string m_major;
int m_test[3];
int m_id;
public:
Student(string name, int age, string major, int test[], int id);
Student();
bool readFromFile(ifstream& is);
bool readFromKeyboard();
void writeToFile(ostream& os);
void writeToScreen();
int getID() const;
};

struct TreeNode
{
Student m_student;

TreeNode* m_left;
TreeNode* m_right;
TreeNode(const Student& student, TreeNode* left = NULL, TreeNode* right = NULL);
};
ostream& operator<<(ostream& os, const TreeNode& pTree);

class Tree
{
friend ostream& operator<<(ostream& os, const Tree& tree);
public:
Tree();
Tree(const Tree& tree2);
~Tree();
bool IsEmpty() const;
int Size() const;
bool Insert(const Student& student);
bool Delete(int id);
bool Lookup(Student& student) const;
void Print() const;
Tree& operator=(const Tree& tree2);
private:
TreeNode* m_root;
int Size(TreeNode* pTree) const;
bool Insert(const Student& student, TreeNode *&pTree);
bool Delete(int id, TreeNode*& pTree);
void DeleteNode(TreeNode*& pTree);
void GetPredecessor(int id, TreeNode* pTree);
bool Lookup(Student& student, TreeNode* pTree) const;
void Print(TreeNode* pTree) const;
void Print(ostream& os, TreeNode* pTree) const;
void Clear();
void Clear(TreeNode* pTree);
void Copy(const Tree& tree2);
void Copy(TreeNode*& pThis, TreeNode* pTree2);
};
</pre>
==Tree.cpp==
<pre>
#include "Tree.h"
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
using namespace std;

//-----------------------
//-----Student Class-----
//-----------------------
Student::Student(string name, int age, string major, int test[], int id)
{
int i;

m_name = name;
m_age = age;
m_major = major;
for(i = 0;i < 3;i++)
{
m_test[i] = test[i];
}
m_id = id;
}
Student::Student()
{
int i;

m_name = "";
m_age = 0;
m_major = "";
for(i = 0;i < 3;i++)
{
m_test[i] = 0;
}
m_id = 0;
}
bool Student::readFromFile(ifstream& is)//program 3 readallmoviesfromfile
{
is>>m_name;
if(m_name == "***")
return false;
else
{
is>>m_major;
is>>m_age;
is>>m_test[0]>>m_test[1]>>m_test[2];
is>>m_id;
return true;
}
}
bool Student::readFromKeyboard()
{
cout<<"Please enter your name: ";
cin>>m_name;
cout<<"Please enter your major: ";
cin>>m_major;
cout<<"Please enter your age: ";
cin>>m_age;
cout<<"Please enter your test scores: ";
cin>>m_test[0]>>m_test[1]>>m_test[2];
cout<<"Please enter your ID: ";
cin>>m_id;
return true;
}
void Student::writeToFile(ostream& os) //no headers?
{
//ofstream Output
//ifstream Input; //open output filename
//string filename;
//cout<<"Please enter the name of your file: ";
//getline(cin,filename);
//Input.open(filename);
os<<m_name;
os<<m_major;
os<<m_age;
os<<m_test[0]<<m_test[1]<<m_test[2];
os<<m_id;
//return os;
}
void Student::writeToScreen()
{
cout<<setw(15)<<m_name<<setw(15)<<m_major<<setw(15)<<m_age<<setw(15)<<m_test[0]<<" "<<m_test[1]
<<" "<<m_test[2]<<setw(15)<<m_id<<endl;
}
int Student::getID() const
{
return m_id;
}
//-----------------------
//----TreeNode Struct----
//-----------------------
TreeNode::TreeNode(const Student& student, TreeNode* left, TreeNode* right)
:m_student(student), m_left(left), m_right(right)
{}
ostream& operator<<(ostream& os, const TreeNode& pTree)
{
//if(os == cout)
//os<<pTree->m_student.writeToScreen();
//os<<*pTree;
//else
//os<<pTree->m_student.writeToFile(os);
//cout<<*pTree;
return os;
}
//----------------------
//------Tree Class------
//----------------------
Tree::Tree()
:m_root(0)
{}
Tree::Tree(const Tree& tree2)
:m_root(0)
{}
Tree::~Tree()
{
Clear();
}
bool Tree::IsEmpty() const
{
return(m_root == 0);
}
int Tree::Size() const
{
return Size(m_root);
}
int Tree::Size(TreeNode* pTree) const
{
if(pTree == 0)
return 0;
return (1 + Size(pTree->m_left) + Size(pTree->m_right));
}
bool Tree::Insert(const Student& student)
{
return Insert(student,m_root);
}
bool Tree::Insert(const Student& student, TreeNode*& pTree)
{
if(pTree == 0)
pTree = new TreeNode(student);

else if(student.getID() < pTree->m_student.getID())
{
Insert(student, pTree->m_left);
}
else
{
Insert(student, pTree->m_right);
}
return true;
}
bool Tree::Delete(int id)
{
return Delete(id,m_root);
}
bool Tree::Delete(int id, TreeNode*& pTree)
{
if(pTree == 0)
return false;
else if(id == pTree->m_student.getID())
{
DeleteNode(pTree);
return true;
}
else if(id > pTree->m_student.getID())
return Delete(id,pTree->m_right);
else
return Delete(id,pTree->m_left);
}
void Tree::DeleteNode(TreeNode*& pTree) //pass in id?
{
cout<<"Deleting node with ID "<<pTree->m_student.getID()<<endl;
TreeNode* temp = pTree;

if(pTree->m_left == 0)
{
pTree = pTree->m_right;
delete temp;
}
else if(pTree->m_right == 0)
{
pTree = pTree->m_left;
delete temp;
}
else
{
//get appropriate data
int id = pTree->m_student.getID();
GetPredecessor(id,pTree->m_left);
//pTree->m_student.getID() = id;
Delete(id,pTree->m_left);
}
}
void Tree::GetPredecessor(int id, TreeNode* pTree) //change to id //&id //student?
{
while(pTree->m_right != 0)
{
pTree = pTree->m_right;
}
//get the data, pTree->m_student ?
id = pTree->m_student.getID();
}
bool Tree::Lookup(Student& student) const
{
return Lookup(student,m_root);
}
bool Tree::Lookup(Student& student, TreeNode* pTree) const
{
if(pTree == 0)
{
return false;
}
else if(student.getID() == pTree->m_student.getID())
{
student = pTree->m_student;

cout<<setw(15)<<"Name"<<setw(15)<<"Major"<<setw(15)<<"Age"<<setw(23)<<"Test Scores"<<setw(13)<<"ID"<<endl;
cout<<"===================================================================================="<<endl;
pTree->m_student.writeToScreen();
return true;
}
else if(student.getID() < pTree->m_student.getID())
{
return Lookup(student,pTree->m_left);
}
else
{
return Lookup(student,pTree->m_right);
}
}
ostream& operator<<(ostream& os, const Tree& tree)
{
tree.Print();
return os;
}
void Tree::Print() const
{
Print(m_root);
}
void Tree::Print(ostream& os, TreeNode* pTree) const //print in order
{
if(pTree == 0)
return;
this->Print(os,pTree->m_left);
os<<*pTree;
//os<<pTree->m_student.writeToScreen();
//os<<pTree->m_student;
Print(os,pTree->m_right);
}
void Tree::Print(TreeNode* pTree) const //rework?
{
//static int level = 0;
//level++;
if(pTree == 0)
{
//level--;
return;
}
//for(int i = 0; i <= level; i++)
//cout<<" ";
//cout<<pTree->m_student.getID()<<endl;
pTree->m_student.writeToScreen();
//pTree->m_student.writeToFile(os);
Print(pTree->m_left);
Print(pTree->m_right);
//level--;
}
void Tree::Clear()
{
Clear(m_root);
}
void Tree::Clear(TreeNode* pTree)
{
if(pTree == 0)
return;
Clear(pTree->m_left);
Clear(pTree->m_right);
delete pTree;
}
void Tree::Copy(const Tree& tree2)
{
Copy(m_root, tree2.m_root);
}
void Tree::Copy(TreeNode*& pThis, TreeNode* pTree2)
{
if(pTree2 == 0)
{
pThis = 0;
return;
}
else
{
pThis = new TreeNode(pTree2->m_student);
pThis->m_student = pTree2->m_student;
Copy(pThis->m_left, pTree2->m_left);
Copy(pThis->m_right, pTree2->m_right);
}
}
Tree& Tree::operator=(const Tree& tree2)
{
if(this != &tree2)
{
Clear();
Copy(tree2);
}
return *this;
}
</pre>
==Main.cpp==
<pre>#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include "Tree.h"
using namespace std;

void clearScreen();
//Purpose:To clear the screen.
//Precondition:None
//Postcondition:Screen is cleared.
char displayMenuAndGetSelection();
//Purpose:To display the menu and get the selection for searching.
//Precondition:None
//Postcondition:Search choice is entered and appropriate function is called.
void Pause();
//Purpose:To pause the program and allow the user a break.
//Precondition:None
//Postcondition:None
void quitProgram();
//Purpose:To inform the user the program has been terminated.
//Precondition:Correct choice is selected from the menu.
//Postcondition:Program terminated.
void Header();
//Purpose:
//Precondition:
//Postcondition:
void doInsert(Tree& tree);
//Purpose:
//Precondition:
//Postcondition:
void doDelete(Tree& tree);
//Purpose:
//Precondition:
//Postcondition:
void doSearch(Tree& tree);
//Purpose:
//Precondition:
//Postcondition:

void main()
{
bool done = false;

Tree tree1;
Tree tree3;
Student s1;

s1.readFromKeyboard();
s1.writeToKeyboard();
cin.get();

int t[3] = {80,90,100};
tree1.Insert(Student("John",23,"Biology",t,1234));
tree1.Insert(Student("Carl",67,"Business",t,7777));
tree1.Insert(Student("Barry",27,"Economics",t,9801));
tree1.Insert(Student("Mary",45,"Nursing",t,1001));
tree1.Insert(Student("Dexter",35,"Physics",t,5747));
tree1.Insert(Student("Manslowe",17,"Mathematics",t,1999));
tree1.Insert(Student(s1));

cout<<"---Tree 1---"<<endl;
Header();
tree1.Print();

Tree tree2(tree1);
tree3 = tree1;

cout<<"---Tree 3---"<<endl;
Header();
cout<<tree3;

//create output file menu option .open(c_str())
Pause();
while(!done)
{
char menuChoice = ' ';

menuChoice = displayMenuAndGetSelection();
clearScreen();
switch(menuChoice)
{
case '1':
Header();
tree1.Print();
Pause();
done = false;
break;
case '2':
doInsert(tree1);
Pause();
done = false;
break;
case '3':
doDelete(tree1); //delete does not delete the top node correctly.
Pause();
done = false;
break;
case '4':
doSearch(tree1);
Pause();
done = false;
break;
case '5':
cout<<"The size of the tree is "<<tree1.Size()<<" leaves long."<<endl;
Pause();
done = false;
break;
case '6':
quitProgram();
done = true;
break;
default:
cout<<"Incorrect choice selected"<<endl;
Pause();
done = false;
break;
}
}
}
void clearScreen()
{
system("cls");
}
char displayMenuAndGetSelection()
{
char choice;
clearScreen();
cout<<endl<<endl<<endl;
cout<<"'1' -- View the tree."<<endl<<endl;
cout<<"'2' -- Insert a new person's information into the tree."<<endl<<endl;
cout<<"'3' -- Delete a person's information from the tree."<<endl<<endl;
cout<<"'4' -- Search the tree."<<endl<<endl;
cout<<"'5' -- Count the number of people in the tree."<<endl<<endl;
cout<<"'6' -- Quit the program."<<endl<<endl;
cin>>choice;
cin.ignore(50,'\n');
return choice;
}
void Pause()
{
cout<<endl<<"Press 'ENTER' to continue..."<<endl;
cin.get();
}
void quitProgram()
{
cout<<"Program terminated, good bye!"<<endl;
}
void Header()
{
cout<<setw(15)<<"Name"<<setw(15)<<"Major"<<setw(15)<<"Age"<<setw(23)<<"Test Scores"<<setw(13)<<"ID"<<endl;
cout<<"===================================================================================="<<endl;
}
void doInsert(Tree& tree)
{
string name, major;
int age, id, test[3];

cout<<"Please enter the name of the student: ";
cin>>name;
cout<<"Please enter the age of the student: ";
cin>>age;
cout<<"Please enter the major of the student: ";
cin>>major;
cout<<"Please enter the three test scores of the student: ";
cin>>test[0]>>test[1]>>test[2];
cout<<"Please enter the ID of the student: ";
cin>>id;
tree.Insert(Student(name,age,major,test,id));
cout<<"Insert has been performed."<<endl;
cin.get();
}
void doSearch(Tree& tree)
{
string name, major;
int age = 0;
int id, test[3];

cout<<"Please enter the ID of the student you wish to find: ";
cin>>id;
if(tree.Lookup(Student(name,age,major,test,id)))
{
cout<<endl<<"The student has been found."<<endl;
}
else
cout<<"The student has not been found."<<endl;

cout<<"The search has been performed."<<endl;
cin.get();
}
void doDelete(Tree& tree)
{
int id;

cout<<"Please enter the ID of the student you wish to delete: ";
cin>>id;
if(tree.Delete(id))
cout<<"Delete has been performed."<<endl;
else
cout<<"Delete has not been performed."<<endl;
cin.get();
}
</pre>

Directory:Derek Elder/Programs/BinarySearchTree - Revision history

Derek Elder: start of page - work to be done