edelossantos
asked on
Binary Search Tree
Need code checked. Please advise. Del
#include<iostream>
using namespace std;
template<typename DataType>
class BST {
private:
class BinNode {
public:
DataType data;
BinNode *left;
BinNode *right;
BinNode(): left(0), right(0){}
BinNode(DataType item):data(item), left(0), right(0){}
typedef BinNode* BinNodePointer;
public:
BST();
bool empty() const;
bool search(const DataType& item) const;
void insert(const DataType& item);
void remove(const DataType& item);
void display(ostream& out);
private:
void search2(const DataType& item, bool& found, BinNodePointer& locPtr, BinNodePointer& parent) const;
void displayAux(ostream& out, int index, BinNodePointer& subTreeRoot);
BinNodePointer myFront;
};
template<typename DataType>
bool BST<DataType>::empty() const {
return myRoot == 0;
}
template<typename DataType>
bool BST<DataType>::search(cons t DataType& item) const {
BST<DataType>::BinNodePoin ter
locPtr = myFront;
bool found = false;
for(; ;) {
if(found || locPtr == 0) break;
if(item < locPtr->data)
locPtr = locPtr->left;
else if(locPtr->data < item)
locPtr = locPtr->right;
else found = true;
}
return found;
}
void BST<DataType>::insert(cons t DataType& item) {
BST<DataType>::BinNodePoin ter
locPtr = myRoot, parent = 0;
bool found = false;
while(!found && locPtr != 0) {
parent = locPtr;
if(item < locPtr->data)
locPtr = locPtr->left;
else if(locPtr->data < item)
locPtr = locPtr->right;
else found = true;
}
if(!found) {
locPtr = new BST<DataType>::BinNode(ite m);
if(parent == 0)
myRoot = locPtr;
else if(item < parent->data)
parent->left = locPtr;
else
parent->right = locPtr;
}
cout << "Item already in the tree. " << endl;
}
template<typename DataType>
void BST<DataType>::displayAux( ostream& out) {
int indent, BST<DataType>::BinNodePoin ter subTreeRoot) {
if(subTreeRoot != 0) {
displayAux(out, indent + B, subTreeRoot->right);
out << setw(indent) << " " << subTreeRoot->data << endl;
displayAux(out, indent + B, subTreeRoot->left);
}
}
return;
}
template<typename DataType>
void BST<DataType>::remove(cons t DataType& item) {
bool found;
BST<DataType>::BinNodePoin ter x, parent;
search2(item, found, x, parent);
if(!found) {
cout << " Item not in the BST\n";
return;
}
if(x->left != 0 && x->right !=0) {
BST<DataType>::BinNodePoin ter xSucc = x->right;
parent = x;
while(xSucc->left != 0) {
parent = xSucc;
xSucc = xSucc->left;
}
x->data = xSucc->data;
x = xSucc;
}
BST<DataType>::BinNodePoin ter
subTree = x->left;
if(subtree == 0)
subtree = x->right;
if(parent == 0)
myRoot = subtree;
else if(parent->left == x)
parent->left = subtree;
else
parent->right = subtree;
delete x;
}
template<typename DataType>
void BST<DataType>::search2(con st DataType& item, bool& found, BST<DataType>::BinNodePoin ter& locPtr,
BST<DataType>::BinNodePoin ter& parent) const {
locPtr = myRoot;
parent = 0;
found = false;
while(!found && locPtr != 0) {
if(item < locPtr->data) {
parent = locPtr;
locPtr = locPtr->left;
}
else if(locPtr->data < item) {
parent = locPtr;
locPtr = locPtr->right;
}
else
found = true;
}
return;
}
int main(void) {
BST<int> intBST;
cout << " Constructing empty BST\n";
cout << " BST " << (intBst.empty() ? "is" : "is not") << " empty\n";
cout << " Inorder Traversal of BST: \n";
intBST.inorder(cout);
cout << "\nNow insert a bunch of integers into the BST. "
"\nTry items not in the BST and some that are in it:\n";
int number;
for(;;) {
cout << "Item to insert (-999 to stop): ";
cin >> number;
if(number == -999) break;
intBst.insert(number);
}
intBST.graph(cout);
cout << "BST " << (intBST.empty() ? "is" : "is not") << empty;
cout << "Inorder Traversal of BST: \n";
intBST.inorder(cout);
cout << endl;
cout << "\n\nNow testing the search() operation."
"\nTry both items in the BST and some not in it:\n";
for(;;) {
cout << "Item to find(-999 to stop):" ;
cin >> number;
if(number == -999) break;
cout << (intBST.search(number) ? "Found" : "Not found") << endl;
}
cout << "\nNow testing the remove() operation. "
"\nTry both items in the BST and some not in it:\n";
for(;;) {
cout << "Item to remove (-999 to stop): ";
cin >> number;
if(number == -999) break;
intBST.remove(number);
intBST.graph(cout);
}
cout << "\nInorder Traversal of BST: \n";
intBST.inorder(cout);
cout << endl;
return 0;
system("pause");
}
output:
------ Build started: Project: Lab 7, Configuration: Debug Win32 ------
Compiling...
bin.cpp
c:\documents and settings\enrique\my documents\cs223_spring06 ~awanni\lab 7\bin.cpp(247) : fatal error C1075: end of file found before the left brace '{' at 'c:\documents and settings\enrique\my documents\cs223_spring06 ~awanni\lab 7\bin.cpp(7)' was matched
Build log was saved at "file://c:\Documents and Settings\Enrique\My Documents\Visual Studio 2005\Projects\Lab 7\Lab 7\Debug\BuildLog.htm"
Lab 7 - 1 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
#include<iostream>
using namespace std;
template<typename DataType>
class BST {
private:
class BinNode {
public:
DataType data;
BinNode *left;
BinNode *right;
BinNode(): left(0), right(0){}
BinNode(DataType item):data(item), left(0), right(0){}
typedef BinNode* BinNodePointer;
public:
BST();
bool empty() const;
bool search(const DataType& item) const;
void insert(const DataType& item);
void remove(const DataType& item);
void display(ostream& out);
private:
void search2(const DataType& item, bool& found, BinNodePointer& locPtr, BinNodePointer& parent) const;
void displayAux(ostream& out, int index, BinNodePointer& subTreeRoot);
BinNodePointer myFront;
};
template<typename DataType>
bool BST<DataType>::empty() const {
return myRoot == 0;
}
template<typename DataType>
bool BST<DataType>::search(cons
BST<DataType>::BinNodePoin
locPtr = myFront;
bool found = false;
for(; ;) {
if(found || locPtr == 0) break;
if(item < locPtr->data)
locPtr = locPtr->left;
else if(locPtr->data < item)
locPtr = locPtr->right;
else found = true;
}
return found;
}
void BST<DataType>::insert(cons
BST<DataType>::BinNodePoin
locPtr = myRoot, parent = 0;
bool found = false;
while(!found && locPtr != 0) {
parent = locPtr;
if(item < locPtr->data)
locPtr = locPtr->left;
else if(locPtr->data < item)
locPtr = locPtr->right;
else found = true;
}
if(!found) {
locPtr = new BST<DataType>::BinNode(ite
if(parent == 0)
myRoot = locPtr;
else if(item < parent->data)
parent->left = locPtr;
else
parent->right = locPtr;
}
cout << "Item already in the tree. " << endl;
}
template<typename DataType>
void BST<DataType>::displayAux(
int indent, BST<DataType>::BinNodePoin
if(subTreeRoot != 0) {
displayAux(out, indent + B, subTreeRoot->right);
out << setw(indent) << " " << subTreeRoot->data << endl;
displayAux(out, indent + B, subTreeRoot->left);
}
}
return;
}
template<typename DataType>
void BST<DataType>::remove(cons
bool found;
BST<DataType>::BinNodePoin
search2(item, found, x, parent);
if(!found) {
cout << " Item not in the BST\n";
return;
}
if(x->left != 0 && x->right !=0) {
BST<DataType>::BinNodePoin
parent = x;
while(xSucc->left != 0) {
parent = xSucc;
xSucc = xSucc->left;
}
x->data = xSucc->data;
x = xSucc;
}
BST<DataType>::BinNodePoin
subTree = x->left;
if(subtree == 0)
subtree = x->right;
if(parent == 0)
myRoot = subtree;
else if(parent->left == x)
parent->left = subtree;
else
parent->right = subtree;
delete x;
}
template<typename DataType>
void BST<DataType>::search2(con
BST<DataType>::BinNodePoin
locPtr = myRoot;
parent = 0;
found = false;
while(!found && locPtr != 0) {
if(item < locPtr->data) {
parent = locPtr;
locPtr = locPtr->left;
}
else if(locPtr->data < item) {
parent = locPtr;
locPtr = locPtr->right;
}
else
found = true;
}
return;
}
int main(void) {
BST<int> intBST;
cout << " Constructing empty BST\n";
cout << " BST " << (intBst.empty() ? "is" : "is not") << " empty\n";
cout << " Inorder Traversal of BST: \n";
intBST.inorder(cout);
cout << "\nNow insert a bunch of integers into the BST. "
"\nTry items not in the BST and some that are in it:\n";
int number;
for(;;) {
cout << "Item to insert (-999 to stop): ";
cin >> number;
if(number == -999) break;
intBst.insert(number);
}
intBST.graph(cout);
cout << "BST " << (intBST.empty() ? "is" : "is not") << empty;
cout << "Inorder Traversal of BST: \n";
intBST.inorder(cout);
cout << endl;
cout << "\n\nNow testing the search() operation."
"\nTry both items in the BST and some not in it:\n";
for(;;) {
cout << "Item to find(-999 to stop):" ;
cin >> number;
if(number == -999) break;
cout << (intBST.search(number) ? "Found" : "Not found") << endl;
}
cout << "\nNow testing the remove() operation. "
"\nTry both items in the BST and some not in it:\n";
for(;;) {
cout << "Item to remove (-999 to stop): ";
cin >> number;
if(number == -999) break;
intBST.remove(number);
intBST.graph(cout);
}
cout << "\nInorder Traversal of BST: \n";
intBST.inorder(cout);
cout << endl;
return 0;
system("pause");
}
output:
------ Build started: Project: Lab 7, Configuration: Debug Win32 ------
Compiling...
bin.cpp
c:\documents and settings\enrique\my documents\cs223_spring06 ~awanni\lab 7\bin.cpp(247) : fatal error C1075: end of file found before the left brace '{' at 'c:\documents and settings\enrique\my documents\cs223_spring06 ~awanni\lab 7\bin.cpp(7)' was matched
Build log was saved at "file://c:\Documents and Settings\Enrique\My Documents\Visual Studio 2005\Projects\Lab 7\Lab 7\Debug\BuildLog.htm"
Lab 7 - 1 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER