Homework SourseThis is a c binary search program I worked so far but still
This is a c++ binary search program I worked so far but still cant get it right.
Can anyone help me? Big thanks!!
the client should not be modified
/*
*File: client.cpp
*Author: Yingwu Zhu
*Warning: do not change this file and use it as is.
*Last Modififcation: 10/21/2016
*/
#include
#include
#include
#include
#include
#include \"bst.h\"
using namespace std;
int main(int argc, char* argv[]) {
if (argc != 2) {
cout << \"Format: \" << argv[0] << \" [data file]\" << endl;
return 0;
}
ifstream fin(argv[1]);
int cases;
fin >> cases;
int passed = 0;
for (int i = 1; i <= cases; i++) {
cout << \"Checking test case #\" << i << \" ... \";
BST T;
set S;
int n, x;
fin >> n;
bool ok = true;
vector tmp;
int rem = 0;
for (int j = 0; j < n; j++) {
fin >> x;
T.Insert(x);
S.insert(x);
ok &= (T.Search(x) && T.RecurSearch(x));
if (tmp.empty())
tmp.push_back(x);
if (rand()%10 < 3) {
T.Erase(tmp[0]);
S.erase(tmp[0]);
ok &= (T.Search(tmp[0]) == false);
tmp.pop_back();
rem++;
}
}
if (rem
ok &= (T.MaxElement() == *S.rbegin());
while (!S.empty() && !T.Empty()) {
int x = T.MinElement();
ok &= (x == *S.begin());
T.Erase(x);
S.erase(S.begin());
}
cout << (ok ? \"Passed!\" : \"Failed\") << endl;
passed += ok;
}
cout << passed << \" of \" << cases << \" test cases have passed!\ \";
if (passed == cases)
cout << endl << \"Congratulations! Good to Submit Your Code\ \";
else if ((double)passed/cases >= 0.95)
cout << endl << \"You are almost there, but need to fix some bugs.\ \";
else
cout << endl << \"Your code needs a lot of fixes for submission\ \";
return 0;
}
============================================================================
//bst.h
#ifndef _BST_H_
#define _BST_H_
#include
using namespace std;
class BST {
private:
class Node {
public:
int data;
Node* left;
Node* right;
};
Node* root; //root node pointer
//you may add your auxiliary functions here!
public:
BST(); //constructor
~BST(); //destructor
bool Empty() const;
void Insert(int val);
int MinElement() const;
int MaxElement() const;
bool Search(int val) const;
bool RecurSearch(int val) const;
void Erase(int val);
};
#endif
============================================================================
/*
bst.cpp
Subject: Binary Seach Tree
Modification Time:10/26/2016
*/
#include
#include\"bst.h\"
using namespace std;
BST::BST(){
root= NULL;
}
BST::~BST(){
delete root;
delete root->left;
delete root->right;
}
bool BST::Empty() const {
return data;
}
void BST::Insert(int val){
Node* p= new Node;
p->data= val;
Node* cur = root;
if(val < cur->data){
cur = cur -> left;
}
else{
right->next=val;
}
}
int BST::MinElement() const {
Node* cur;
while(cur->left != NULL){
cur = cur->left;
}
return(cur->data);
}
int BST::MaxElement() const{
if(root==NULL){
return 0;
}
if(root->left>root->data){
root->data=root->right;
}
else if(root->right>root->data){
root->data=root->right;
}
return root->data;
}
bool BST:: Search(int val) const{
Node* cur;
cur = root;
while(cur!=NULL){
if(cur->data == val){
return true;
}
else if(cur->data < val){
cur = cur-> right;
}
else if(cur->data > val){
cur = cur-> left;
}
}
return false;
}
bool BST:: RecurSearch(int val) const{
Node* ptr;
ptr=root;
if(this == NULL){
return false;
}
else if(val == ptr->data){
return true;
}
else if(data < ptr->data){
return RecurSearch(val);
}
else if(data > ptr->data){
return RecurSearch(val);
}
}
void BST::Erase(int val) {
Node* cur;
cur = root;
while(cur->data != val){
if(cur->data < val){
cur = cur->left;
}
else if(cur->data> val){
cur = cur->right;
}
}
if(cur->left && cur->right !=NULL){
int temp = MaxElement();
Erase(val);
cur->data = temp;
}
else if(cur->left == NULL)
int temp = cur->left;
Erase(val);
cur->data=temp;
}
else if(cur->right == NULL){
int temp = cur->right;
cur->(this);
}
else{
return NULL;
}
}
Solution
####Please attach data file which u are using to test this program OR atleast give the format for testcase#########
#ifndef _BST_H_
#define _BST_H_
using namespace std;
class BST {
class Node {
public:
int data;
Node* left;
Node* right;
};
Node* root; //root node pointer
//you may add your auxiliary functions here!
BST(); //constructor
~BST(); //destructor
bool Empty() const;
void Insert(int val);
int MinElement() const;
int MaxElement() const;
bool Search(int val) const;
bool RecurSearch(int val) const;
void Erase(int val);
using namespace std;
root= NULL;
root->left = NULL;
root->right = NULL;
delete root;
delete root->left;
delete root->right;
}
bool BST::Empty() const {
return root == NULL;
void BST::Insert(int val)
Node* t = new Node;
Node* parent;
t->data = val;
t->left = NULL;
t->right = NULL;
parent = NULL;
if(Empty())
root = t;
else
{
Node* curr;
curr = root;
while(curr)
{
parent = curr;
if(t->data > curr->data)
curr = curr->right;
else
curr = curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
int BST::MinElement() const {
Node* cur;
while(cur->left != NULL){
cur = cur->left;
}
return(cur->data);
}
int BST::MaxElement() const{
Node* cur;
while(cur->right != NULL){
cur = cur->right;
}
return(cur->data);
}
bool BST:: Search(int val) const{
Node* cur;
cur = root;
while(cur!=NULL){
if(cur->data == val){
return true;
else if(cur->data < val){
cur = cur-> right;
}
else if(cur->data > val){
cur = cur-> left;
}
}
return false;
}
bool BST:: RecurSearch(int val) const{
Node* ptr;
ptr=root;
if(this == NULL){
return false;
}
else if(val == ptr->data){
return true;
}
else if(val < ptr->data){
return RecurSearch(val);
}
else{
return RecurSearch(val);
}
void BST::Erase(int val) {
bool found = false;
if(Empty())
{
cout<<\"This tree is empty\"<<endl;
return;
}
Node* cur;
Node* parent;
cur = root;
while(cur != NULL)
{
if(cur->data == val){
found = true;
break;
}
else
{
parent = cur;
if(cur->data < val)
cur = cur->right;
else
cur = cur->left;
}
}
if(!found)
{
cout<<\"Passed Element for deletion not found\"<<endl;
return;
}
//3 cases
1) Removal of child node
2) Removal of node with single child
3) Removal of node with 2 children
//Node with single child
if((cur->left == NULL && cur->right != NULL) || (cur->left != NULL && cur->right == NULL ))
{
if(cur->left == NULL && cur->right != NULL)
{
if(parent->left == cur)
{
parent->left = cur->right;
delete cur;
}
else
{
parent->right = cur->right;
delete cur;
}
}
else //left child present and no right child
{
if(parent->left == cur)
{
parent->left = cur->left;
delete cur;
}
else
{
parent->right = cur->left;
delete cur;
}
}
return;
}
//For leaf Node
if(cur->left == NULL && cur->right == NULL)
{
if(parent->left == cur)
parent->left = NULL;
else
parent->right = NULL;
delete cur;
return;
}
//Node with two children
//replace node with smallest value in right subtree
if(cur->left != NULL && cur->right != NULL)
{
Node *checker;
checker = cur->right;
if(checker->left == NULL && checker->right == NULL)
{
cur = checker;
delete checker;
cur->right = NULL;
}
else //right child has children
{
//if the node\'s right child has a left child
// Move all the way down left to locate smallest element
if((cur->right)->left != NULL)
{
Node* lcurr;
Node* lcurrp;
lcurrp = cur->right;
lcurr = (cur->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
cur->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
Node *temp;
temp = cur->right;
cur->data = temp->data;
cur->right = temp->right;
delete temp;
}
}
return;
}
#include
#include
#include
#include
#include
#include \"bst.h\"
using namespace std;
int main(int argc, char* argv[]) {
if (argc != 2) {
cout << \"Format: \" << argv[0] << \" [data file]\" << endl;
return 0;
}
ifstream fin(argv[1]);
int cases;
fin >> cases;
int passed = 0;
for (int i = 1; i <= cases; i++) {
cout << \"Checking test case #\" << i << \" ... \";
BST T;
set S;
int n, x;
fin >> n;
bool ok = true;
vector tmp;
int rem = 0;
for (int j = 0; j < n; j++) {
fin >> x;
T.Insert(x);
S.insert(x);
ok &= (T.Search(x) && T.RecurSearch(x));
if (tmp.empty())
tmp.push_back(x);
if (rand()%10 < 3) {
T.Erase(tmp[0]);
S.erase(tmp[0]);
ok &= (T.Search(tmp[0]) == false);
tmp.pop_back();
rem++;
}
}
if (rem
ok &= (T.MaxElement() == *S.rbegin());
while (!S.empty() && !T.Empty()) {
int x = T.MinElement();
ok &= (x == *S.begin());
T.Erase(x);
S.erase(S.begin());
}
cout << (ok ? \"Passed!\" : \"Failed\") << endl;
passed += ok;
}
cout << passed << \" of \" << cases << \" test cases have passed!\ \";
if (passed == cases)
cout << endl << \"Congratulations! Good to Submit Your Code\ \";
else if ((double)passed/cases >= 0.95)
cout << endl << \"You are almost there, but need to fix some bugs.\ \";
else
cout << endl << \"Your code needs a lot of fixes for submission\ \";
return 0;
}
