Directory:Derek Elder/Programs/BinarySearchTree

Tree.h

#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);
};

Tree.cpp

#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;
}

Main.cpp

#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();
}