BinarySearchTree.h

#ifndef BinarySearchTree$\_$h

#define BinarySearchTree$\_$h

#include

#include

using namespace std;

$//********$ class TreeNode template object $************$

template

struct TreeNode;

template

ostream& operator ostream& os$,$ const TreeNode& node$)$;

template

class BinarySearchTree;

template

ostream& operator ostream& os$,$ const BinarySearchTree& tree$)$;

template

class TreeNode$\{$

public:

friend ostream& operator ostream& os$,$ const TreeNode& node$)\{$

os $$ node.data ;

if$($node$.$left $!=$ NULL$)$

os node$.$left$)$;

else os ;

os ;

if$($node$.$right $!=$ NULL$)$

os node$.$right$)$;

else os ;

os ;

return os;

$\}$

TreeNode$*$ parent;

TreeNode$*$ left;

TreeNode$*$ right;

T data;

$\}$;

$//********$ The following help functions are for class TreeNode object $************$

template

bool isLeaf$($TreeNode$*$ node$)\{$

if$($node $==$ NULL$)$ return false;

return $($node$->$left $==$ NULL && node$->$right $==$ NULL$)$;

$\}$

template

bool isRight$($TreeNode$*$ node$)\{$

if$($node $==$ NULL $||$ node$->$parent $==$ NULL$)$ return false;

return node $==$ node$->$parent$->$right;

$\}$

template

bool isLeft$($TreeNode$*$ node$)\{$

if$($node $==$ NULL $||$ node$->$parent $==$ NULL$)$ return false;

return node $==$ node$->$parent$->$left;

$\}$

template

bool isRoot$($TreeNode$*$ node$)\{$

if$($node $==$ NULL$)$ return false;

return node$->$parent $==$ NULL;

$\}$

template

int treeHeight$($TreeNode$*$ node$)\{$

if$($node $==$ NULL$)$ return $-1$;

return $1+$ max$($treeHeight$($node$->$left$),$ treeHeight$($node$->$right$))$;

$\}$

template

int treeSize$($TreeNode$*$ node$)\{$

if$($node $==$ NULL$)$

return $0$;

return $1+$ treeSize$($node$->$left$)+$ treeSize$($node$->$right$)$;

$\}$

$//*****$ Public and private member functions from BinarySearchTree class $*******************************$

$//******$ Implement all the member $($public and private$)$ functions from BinarySearchTree class $**********$

$//******$ All function names explain the purpose of their function $*************************************$

template class BinarySearchTree$\{$

public:

friend ostream& operator ostream& os$,$ const BinarySearchTree& tree$)\{$

os tree$.$root$)$;

return os;

$\}$

BinarySearchTree$()$;

TreeNode$*$ search$($T& data$)$ const;

void insert$($T& data$)$;

TreeNode$*$ successor$($TreeNode$*$ node$)$ const;

bool remove$($T& data$)$;

bool isEmpty$()$ const;

int height$()$ const;

int size$()$ const;

$//$string toString$()$ const;

TreeNode$*$ getRoot$()$ const;

private:

TreeNode$*$ root;

bool remove$($TreeNode$*$ node$)$;

$\}$;

#endif $/*$ BinarySearchTree$\_$h $*/$

CSCI$251$ProjFour.cpp

#include

#include "BinarySearchTree.h$"$

using namespace std;

void menu$()\{$

cout

$"$;

cout MENU $*$

$"$;

cout Add a node $*$

$"$;

cout Remove a node $*$

$"$;

cout Search a data $*$

$"$;

cout Tree property $*$

$"$;

cout Quit $*$

$"$;

cout

$"$;

$\}$

int main$()\{$

int data;

int choice;

BinarySearchTree tree;

do$\{$

menu$()$;

cout $$ "Enter your choice: $"$;

cin $>>$ choice;

switch$($choice$)\{$

case $1$:

cout $$ "Enter an integer data that you will add to tree: $"$;

cin $>>$ data;

tree.insert$($data$)$;

cout $$ "The tree is: $"$ tree $$ endl;

break;

case $2$:

cout $$ "Enter an integer data that you will remvoe from tree: $"$;

cin $>>$ data;;

if$($tree$.$remove$($data$))$

cout $$ "Remove successfully. Now the tree is: $"$ tree $$ endl;

else

cout No such data in tree

$"$;

break;

case $3$:

cout$$ "Enter the integer data that you want to search for:

$"$;

cin $>>$ data;

if$($tree$.$search$($data$)==$ NULL$)$

cout No such data in tree

$"$;

else

cout $$ "The tree is: $"$ tree Data found in tree

$"$;

break;

case $4$:

if$($tree$.$isEmpty$())$

cout $$ "Tree is empty

$"$ ;

else$\{$

cout $$ "The tree is: $"$ tree endl;

cout $$ "Tree size: $"$ tree.size$()$ endl;

cout $$ "Tree height: $"$ tree.height$()$ endl ;

$\}$

break;

case $5$:

cout $$ "Make sure you run enough test before you turn it in

$"$;

break;

default:

cout $$ "Wrong option. Please choose from menu

$"$;

break;

$\}$

$\}$while$($choice $!=5)$;

$\}$