The easiest way, in my opinion, to do this problem, is to two small functions to the binary search tree class.

In the Ferry Problem, replace the tables or linked lists with binary search trees

binarySearchTree.h

//Header File Binary Search Tree

#ifndef H_binarySearchTree #define H_binarySearchTree #include #include #include "binaryTree.h"

//************************************************************* // Author: D.S. Malik // // This class specifies the basic operations to implement a // binary search tree. //*************************************************************

using namespace std;

template class bSearchTreeType: public binaryTreeType { public: bool search(const elemType& searchItem) const; //Function to determine if searchItem is in the binary //search tree. //Postcondition: Returns true if searchItem is found in the // binary search tree; otherwise, returns false.

void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If no node in the binary search tree has the // same info as insertItem, a node with the info insertItem // is created and inserted in the binary search tree.

void deleteNode(const elemType& deleteItem); //Function to delete deleteItem from the binary search tree //Postcondition: If a node with the same info as deleteItem // is found, it is deleted from the binary search tree.

int distance(const elemType& searchItem) const; //returns the distance of searchItem from the tree's root or //-1 if searchItem is not in the tree

private: void deleteFromTree(binaryTreeNode* &p); //Function to delete the node to which p points is deleted //from the binary search tree. //Postcondition: The node to which p points is deleted from // the binary search tree. int distance(binaryTreeNode *p, const elemType& searchItem, int distance) const; //returns the distance of searchItem from the tree's root or //-1 if searchItem is not in the tree

};

template int bSearchTreeType::distance(const elemType& searchItem) const { int _distance = 0; return distance(root, searchItem, _distance); }

template int bSearchTreeType::distance(binaryTreeNode*p, const elemType& searchItem, int _distance) const { if (p == NULL) return -1; else if (p->info < searchItem) return distance(p->rlink, searchItem, _distance + 1); else if (p->info > searchItem) return distance(p->llink, searchItem, _distance + 1); else return _distance; }

template bool bSearchTreeType:: search(const elemType& searchItem) const { binaryTreeNode *current; bool found = false;

if (root == NULL) cerr << "Cannot search the empty tree." << endl; else { current = root;

while (current != NULL && !found) { if (current->info == searchItem) found = true; else if (current->info > searchItem) current = current->llink; else current = current->rlink; }//end while }//end else

return found; }//end search

template void bSearchTreeType::insert(const elemType& insertItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent = NULL; //pointer behind current binaryTreeNode *newNode = new binaryTreeNode; assert(newNode != NULL); newNode->info = insertItem; newNode->llink = NULL; newNode->rlink = NULL;

if (root == NULL) root = newNode; else { current = root; while (current != NULL) { trailCurrent = current;

if (current->info == insertItem) { cerr << "The insert item is already in the list-"; cerr << "duplicates are not allowed." << endl; return; } else if (current->info > insertItem) current = current->llink; else current = current->rlink; }//end while

if (trailCurrent->info > insertItem) trailCurrent->llink = newNode; else trailCurrent->rlink = newNode; } }//end insert

template void bSearchTreeType::deleteNode(const elemType& deleteItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current bool found = false;

if (root == NULL) cout << "Cannot delete from the empty tree." << endl; else { current = root; trailCurrent = root;

while (current != NULL && !found) { if (current->info == deleteItem) found = true; else { trailCurrent = current;

if (current->info > deleteItem) current = current->llink; else current = current->rlink; } }//end while

if (current == NULL) cout << "The delete item is not in the tree." << endl; else if (found) { if (current == root) deleteFromTree(root); else if (trailCurrent->info > deleteItem) deleteFromTree(trailCurrent->llink); else deleteFromTree(trailCurrent->rlink); }//end if } }//end deleteNode

template void bSearchTreeType::deleteFromTree (binaryTreeNode* &p) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current binaryTreeNode *temp; //pointer to delete the node

if (p == NULL) cerr << "Error: The node to be deleted is NULL." << endl; else if(p->llink == NULL && p->rlink == NULL) { temp = p; p = NULL; delete temp; } else if(p->llink == NULL) { temp = p; p = temp->rlink; delete temp; } else if(p->rlink == NULL) { temp = p; p = temp->llink; delete temp; } else { current = p->llink; trailCurrent = NULL;

while (current->rlink != NULL) { trailCurrent = current; current = current->rlink; }//end while

p->info = current->info;

if (trailCurrent == NULL) //current did not move; //current == p->llink; adjust p p->llink = current->llink; else trailCurrent->rlink = current->llink; delete current; }//end else }//end deleteFromTree

#endif

binaryTree.h

//Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree

//************************************************************* // Author: D.S. Malik // // class binaryTreeType // This class specifies the basic operations to implement a // binary tree. //*************************************************************

#include

using namespace std;

//Definition of the node template struct binaryTreeNode { elemType info; binaryTreeNode *llink; binaryTreeNode *rlink; };

//Definition of the class template class binaryTreeType { public: const binaryTreeType& operator= (const binaryTreeType&); //Overload the assignment operator. bool isEmpty() const; //Returns true if the binary tree is empty; //otherwise, returns false. void inorderTraversal() const; //Function to do an inorder traversal of the binary tree. void preorderTraversal() const; //Function to do a preorder traversal of the binary tree. void postorderTraversal() const; //Function to do a postorder traversal of the binary tree.

int treeHeight() const; //Returns the height of the binary tree. int treeNodeCount() const; //Returns the number of nodes in the binary tree. int treeLeavesCount() const; //Returns the number of leaves in the binary tree. void destroyTree(); //Deallocates the memory space occupied by the binary tree. //Postcondition: root = NULL; binaryTreeType(const binaryTreeType& otherTree); //copy constructor binaryTreeType(); //default constructor

~binaryTreeType(); //destructor

protected: binaryTreeNode *root;

private: void copyTree(binaryTreeNode* &copiedTreeRoot, binaryTreeNode* otherTreeRoot); //Makes a copy of the binary tree to which //otherTreeRoot points. The pointer copiedTreeRoot //points to the root of the copied binary tree.

void destroy(binaryTreeNode* &p); //Function to destroy the binary tree to which p points. //Postcondition: p = NULL

void inorder(binaryTreeNode *p) const; //Function to do an inorder traversal of the binary //tree to which p points. void preorder(binaryTreeNode *p) const; //Function to do a preorder traversal of the binary //tree to which p points. void postorder(binaryTreeNode *p) const; //Function to do a postorder traversal of the binary //tree to which p points.

int height(binaryTreeNode *p) const; //Function to return the height of the binary tree //to which p points. int max(int x, int y) const; //Returns the larger of x and y. int nodeCount(binaryTreeNode *p) const; //Function to return the number of nodes in the binary //tree to which p points int leavesCount(binaryTreeNode *p) const; //Function to return the number of leaves in the binary //tree to which p points };

//Definition of member functions

template binaryTreeType::binaryTreeType() { root = NULL; }

template bool binaryTreeType::isEmpty() const { return (root == NULL); }

template void binaryTreeType::inorderTraversal() const { inorder(root); }

template void binaryTreeType::preorderTraversal() const { preorder(root); }

template void binaryTreeType::postorderTraversal() const { postorder(root); }

template int binaryTreeType::treeHeight() const { return height(root); }

template int binaryTreeType::treeNodeCount() const { return nodeCount(root); }

template int binaryTreeType::treeLeavesCount() const { return leavesCount(root); }

template void binaryTreeType::copyTree (binaryTreeNode* &copiedTreeRoot, binaryTreeNode* otherTreeRoot) { if (otherTreeRoot == NULL) copiedTreeRoot = NULL; else { copiedTreeRoot = new binaryTreeNode; copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->llink, otherTreeRoot->llink); copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink); } } //end copyTree

template void binaryTreeType::inorder(binaryTreeNode *p) const { if (p != NULL) { inorder(p->llink); cout << p->info << " "; inorder(p->rlink); } }

template void binaryTreeType::preorder(binaryTreeNode *p) const { if (p != NULL) { cout<info<<" "; preorder(p->llink); preorder(p->rlink); } }

template void binaryTreeType::postorder(binaryTreeNode *p) const { if (p != NULL) { postorder(p->llink); postorder(p->rlink); cout << p->info << " "; } }

//Overload the assignment operator template const binaryTreeType& binaryTreeType:: operator=(const binaryTreeType& otherTree) { if (this != &otherTree) //avoid self-copy { if (root != NULL) //if the binary tree is not empty, //destroy the binary tree destroy(root);

if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); }//end else

return *this; }

template void binaryTreeType::destroy(binaryTreeNode* &p) { if (p != NULL) { destroy(p->llink); destroy(p->rlink); delete p; p = NULL; } }

template void binaryTreeType::destroyTree() { destroy(root); }

//copy constructor template binaryTreeType::binaryTreeType (const binaryTreeType& otherTree) { if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); }

template binaryTreeType::~binaryTreeType() { destroy(root); }

template int binaryTreeType::height(binaryTreeNode *p) const { if (p == NULL) return 0; else return 1 + max(height(p->llink), height(p->rlink)); }

template int binaryTreeType::max(int x, int y) const { if (x >= y) return x; else return y; }

template int binaryTreeType::nodeCount(binaryTreeNode *p) const { cout << "Write the definition of the function nodeCount" << endl;

return 0; }

template int binaryTreeType::leavesCount(binaryTreeNode *p) const { cout << "Write the definition of the function leavesCount" << endl;

return 0; }

#endif