```
#include "BinarySearchTree.h"
#include <iostream>
using namespace std;
//In all of the following algorithms,
//you will see that Mr Weiss used recursive
//functions incisively and vividly!
class BinarySearchTree;
BinarySearchTree::BinarySearchTree()
{
root = new BinaryNode();
root->left = NULL;
root->right = NULL;
}
//////////////////////////
BinarySearchTree::BinarySearchTree(const BinarySearchTree & rhs){
if(this != &rhs ){
makeEmpty();
root = clone(rhs.root);
}
}
//////////////////////////
const BinarySearchTree & BinarySearchTree
::operator=(const BinarySearchTree &rhs)
{
if(this != &rhs){
makeEmpty();
root = clone(rhs.root);
}
return *this;
}
//////////////////////////
BinarySearchTree::~BinarySearchTree(){
makeEmpty();
}
//////////////////////////
const int & BinarySearchTree::findMin() const {
return findMin(root)->element;
}
//////////////////////////
const int & BinarySearchTree::findMax() const {
return findMax(root)->element;
}
//////////////////////////
bool BinarySearchTree::contains(const int & x) const {
return contains(x,root);
}
//////////////////////////
bool BinarySearchTree::isEmpty() const {
return (root == NULL);
}
//////////////////////////
void BinarySearchTree::printTree() const {
if(root==NULL)
return;
if(root->left!=NULL){
cout<<root->element;
printTree(root->left);
}
if(root->right!=NULL){
cout<<root->element;
printTree(root->right);
}
}
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
void BinarySearchTree::insert(const int & x,BinaryNode * & t) const{
if( t==NULL )
t = new BinaryNode(x,NULL,NULL);
if(x<t->element)
insert(x,t->left);
if(x>t->element)
insert(x,t->right);
}
//////////////////////////
void BinarySearchTree::remove(const int & x,BinaryNode * & t)const{
if(t==NULL)
return;
else if(x<t->element)
remove(x,t->left);
else if(t->element<x)
remove(x,t->right);
//Author used a beautiful algorithm !I can't do that!
//This tell me don't think "while" and "for" only!
//When you using recursion,you will find that "go
//to the next step" is more usefull. Weiss called
//this "making progress".
else if(t->left!=NULL && t->right!=NULL){
t->element=findMin(t->right)->element;
remove(t->element,t->right);
}
else{
BinaryNode * oldNode = t;
t=(t->left!=NULL)?t->left:t->right;
delete oldNode;
}
}
//////////////////////////
BinaryNode * BinarySearchTree::findMin(BinaryNode *t){
if(t!=NULL)
while(t->right != NULL)
t=t->left;
return t;
}
//////////////////////////
BinaryNode * BinarySearchTree::findMax(BinaryNode *t){
if(t!=NULL)
while(t->right != NULL)
t=t->right;
return t;
}
//////////////////////////
bool BinarySearchTree::contains(const int & x, BinaryNode *t)const{
if(t==NULL)
return false;
//Weiss put the following two sentences to the end of this
//codeblock with an "else".But I think put it here can make
//the code more readable.
if(x == t->element)
return true;
//When I implemented these, I haven't added
//"return" before recursive functions.
//Why must add "return" in the following sentences?
//How many times will the "return" really
//return when the promgram run?
//What will be happened,if I delete these "return"?
if(x < t->element)
return contains(x,t->left);
else if(t->element < x )
return contains(x,t->right);
}
//This method used the postorder traversal
//to make the tree empty.Postorder traversal
//means the order: left->right->root.
//////////////////////////
void BinarySearchTree::makeEmpty(BinaryNode * & t){
if(t!=NULL){
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t=NULL;
}
//////////////////////////
BinaryNode * BinarySearchTree::clone(BinaryNode *t) const{
if(t==NULL)
return NULL;
//It's great beautiful here!
return new BinaryNode (t->element,clon(t->left),clon(t->rihght) );
}
```

```
// Data Structure: Binary Search Tree
// This file is named BinarySearchTree.h
#ifndef MYT_BSTREE_H
#define MYT_BSTREE_H
class BinarySearchTree
{
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree & rhs);
~BinarySearchTree();
const int & findMin() const;
const int & findMax() const;
bool contains(const int & x) const;
bool isEmpty() const;
void printTree() const;
void makeEmpty();
void insert(const int & x);
void remove(const int & x);
const BinarySearchTree & operator=(const BinarySearchTree & rhs);
class BinaryNode
{
int element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(){}
BinaryNode(const int & theElement,BinaryNode *lt=0,
BinaryNode *rt=0)
: element(theElement),left(lt),right(rt){ }
friend class BinarySearchTree;
};
protected:
BinaryNode *root;
void insert(const int & x,BinaryNode * & t) const;
void remove(const int & x,BinaryNode * & t) const;
BinaryNode * findMin(BinaryNode *t) const;
BinaryNode * findMax(BinaryNode *t) const;
bool contains(const int & x,BinaryNode *t) const;
void makeEmpty(BinaryNode * & t);
void printTree(BinaryNode *t) const;
BinaryNode * clone(BinaryNode *t) const;
};
#endif
```