Adding following functions to bst

Implement the following 3 member functions:

void remove(const T& data);

function removes the node containing data

int depth(const T& data);

function returns the depth of the node with value of data. If no such node exist function returns -1

BST(const BST& rhs);

copy constructor duplicates rhs into current object

The starter file is:

//starter.h

#include #include

/*forward declaration*/ template class Queue;

template class BST{ struct Node{ T data_; Node* left_; Node* right_; Node(const T& data,Node* lt=nullptr,Node* rt=nullptr){ data_=data; left_=lt; right_=rt; } }; Node* root_;

void printPreOrder(Node* subroot)const{ if(subroot){ std::cout << subroot->data_ << " "; printPreOrder(subroot->left_); printPreOrder(subroot->right_); } } void printInOrder(Node* subroot)const{ if(subroot){ printInOrder(subroot->left_); std::cout << subroot->data_ << " "; printInOrder(subroot->right_); } } void destroy(Node* subroot){ if(subroot){ destroy(subroot->left_); destroy(subroot->right_); delete subroot; } } bool isSame(const Node* left, const Node* right) const;

/*used by print() to print all nodes at same level*/ void printLine(Node* data[],int numNodes,int width) const{ int half=width/2; int firsthalf=width%2?half+1:half;

if(numNodes > 1){ for(int i=0;idata_; std::cout << std::left <data_; } } else{ std::cout << std::left <

}

public: BST(){ root_=nullptr; }

/* Lab 7: Implement these 3 functions. */ BST(const BST& rhs){ } void remove(const T& data){ }

int depth(const T& data){ }

void printPreOrder() const{ printPreOrder(root_); std::cout << std::endl; } void printInOrder() const{ printInOrder(root_); std::cout << std::endl; }

void insert(const T& data){ if(root_==nullptr){ root_=new Node(data); } else{

Node* curr=root_; while(curr != nullptr){ if(data < curr->data_){ //go left if(curr->left_){ curr=curr->left_; } else{ curr->left_=new Node(data); curr=nullptr; } } else{ //go right if(curr->right_){ curr=curr->right_; } else{ curr->right_=new Node(data); curr=nullptr; } } }

}

}

bool operator==(const BST& rhs) const; void print() const{ struct Output{ Node* node_; int lvl_; int position_; Output(Node* n=nullptr,int l=0, int p=0){ node_=n; lvl_=l; position_=p; } void set(Node* n=nullptr,int l=0, int p=0){ node_=n; lvl_=l; position_=p; } }; Queue

theNodes; Node* line[16]; if(root_){ for(int i=0;i<16;i++){ line[i]=nullptr; } theNodes.enqueue(Output(root_,0,0)); int currline=0; int width=80; int numInLine=1; while(theNodes.isEmpty()==false){ Output curr=theNodes.front(); if(curr.node_->left_) theNodes.enqueue(Output(curr.node_->left_,curr.lvl_+1,curr.position_*2)); if(curr.node_->right_) theNodes.enqueue(Output(curr.node_->right_,curr.lvl_+1,curr.position_*2+1)); theNodes.dequeue();

if(curr.lvl_>currline){ printLine(line,numInLine,width); width=width/2; numInLine=numInLine*2; for(int i=0;i<16;i++){ line[i]=nullptr; } currline++;

} line[curr.position_]=curr.node_; } printLine(line,numInLine,width); std::cout << std::endl;

} else{ std::cout << "tree is empty" << std::endl; } } ~BST(){ destroy(root_); } };

template class Queue{ T* theQueue_; int capacity_; int used_; int front_; int back_; void grow(){ T* tmp=new T[capacity_*2]; int j; for(int i=0,j=front_;i

} bool isEmpty() const{ return used_==0; } ~Queue(){ delete [] theQueue_; } };

The tester file is :

#include"starter.h"

#include

/************************************************************/ /* Lab tester */ /* To compile: */ /* g++ lab7tester.cpp -std=c++0x */ /* To run: */ /* ./a.out */ /************************************************************/

template bool BST::operator==(const BST& rhs) const{ return isSame(root_,rhs.root_); }

template bool BST::isSame(const typename BST::Node* left, const typename BST::Node* right) const{ bool rc; if(!left && !right){ rc=true; } else if(left && right){ if(left->data_ == right->data_){ rc=isSame(left->left_,right->left_) && isSame(left->right_,right->right_); } else{ rc=false; } } else{ rc=false; } return rc; }

int main(void){ const int numTrees = 11; const int numNodes = 19; BST testTree[numTrees]; BST correctTree[numTrees]; BST correctCopies[numTrees]; int dataset[numNodes]={18,8,28,4,10,20,34,2,6,14,24,32,36,12,16,22,26,30,38};

int resultset[numTrees][numNodes]={ {}, {8}, {28}, {18,8,28,4,10,20,34,6,14,24,32,36,12,16,22,26,30,38}, //remove 2: a leaf {18,8,28,4,10,20,34,2,6,14,24,36,12,16,22,26,30,38}, //remove 32: node with only left child {18,8,28,4,10,20,34,2,6,14,24,32,12,16,22,26,30,38}, //remove 36: node with only right child {18,8,28,4,20,34,2,6,14,24,32,36,12,16,22,26,30,38}, //remove 10: node with right child, right child has subtree {18,8,30,4,10,20,34,2,6,14,24,32,36,12,16,22,26,38}, //remove 28: node with 2 children, inorder successor has no children {18,8,28,6,10,20,34,2,14,24,32,36,12,16,22,26,30,38}, //remove 4: node with 2 children, inorder successor is right child {18,10,28,4,20,34,2,6,14,24,32,36,12,16,22,26,30,38}, //remove 8: node with 2 children, inorder successor is right child who has children {20,8,28,4,10,34,2,6,14,24,32,36,12,16,22,26,30,38} //remove 18: remove the root };

BST* copies[numTrees]; int removeValues[numTrees]={18,18,18,2,32,36,10,28,4,8,18}; testTree[0].insert(18); //tree with just root correctCopies[0].insert(18); int depthTest[numNodes+10]={18,8,28,4,10,20,34,2,6,14,24,32,36,12,16,22,26,30,38, 1, 5, 7, 11,13,19,21,25,40, 31}; int correctDepth[numNodes+10]{0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, -1, -1, -1,-1,-1,-1,-1,-1,-1,-1}; testTree[1].insert(18); //tree with root + left child testTree[1].insert(8); correctCopies[1].insert(18); correctCopies[1].insert(8);

testTree[2].insert(18); //tree with root + right child testTree[2].insert(28); correctCopies[2].insert(18); correctCopies[2].insert(28); //create the 8 identical trees for(int i=3;i

//create the trees with the correct results correctTree[1].insert(resultset[1][0]); correctTree[2].insert(resultset[2][0]);

for(int i=3;i

} } bool passtest=true;

std::cout << "Test depth()" << std::endl; for(int i=0;i(testTree[i]); } for(int i=0;iprint(); std::cout << std::endl << std::endl; std::cout << "Correct Tree:" << std::endl; correctCopies[i].print(); passtest=false; } }

std::cout << "Test remove(): " << std::endl; //remove one node from each tree for(int i=0;passtest && i

for(int i=0;passtest && i

std::cout << "Make sure deep copies were made: " << std::endl; //use copy constructor to create duplicates of every tree for(int i=0;passtest && iprint(); std::cout << std::endl << std::endl; std::cout << "Correct Tree:" << std::endl; correctCopies[i].print(); passtest=false; } }

if(passtest){ std::cout << "Lab 7 tests successfully completed" << std::endl; return 0; } else{ std::cout << "Lab 7 tests were not completed" << std::endl; return 1; } }