Please create a class diagram and test chart (showing test input and the delivered output) for Bintree.cpp.

Bintree.cpp---------------------------------------------------------------------------------------------------------------------

#include #include

using namespace std;

class TreeNode1 { public: void insert_node(TreeNode1* new_node); void print_nodes() const; bool find(string value) const; private: string data; TreeNode1* left; TreeNode1* right; TreeNode1* parent; friend class BinarySearchTree; friend class TreeIterator; };

class TreeIterator { public: TreeIterator(TreeNode1* root); string get(); TreeNode1* next(); private: TreeNode1* current; };

class BinarySearchTree { public: BinarySearchTree(); void insert(string data); void erase(string data); int count(string data) const; void print() const; TreeIterator& begin(); private: TreeNode1* root; };

BinarySearchTree::BinarySearchTree() { root = NULL; }

void BinarySearchTree::print() const { if (root != NULL) root->print_nodes(); }

void BinarySearchTree::insert(string data) { TreeNode1* new_node = new TreeNode1; new_node->data = data; new_node->left = NULL; new_node->right = NULL; new_node->parent = NULL; if (root == NULL) root = new_node; else root->insert_node(new_node); }

void TreeNode1::insert_node(TreeNode1* new_node) { if (new_node->data < data) { if (left == NULL) { left = new_node; new_node->parent = this; } else left->insert_node(new_node); } else if (data < new_node->data) { if (right == NULL) { right = new_node; new_node->parent = this; } else right->insert_node(new_node); } }

int BinarySearchTree::count(string data) const { if (root == NULL) return 0; else if (root->find(data)) return 1; else return 0; }

void BinarySearchTree::erase(string data) { // Find node to be removed

TreeNode1* to_be_removed = root; bool found = false; while (!found && to_be_removed != NULL) { if (to_be_removed->data < data) { to_be_removed = to_be_removed->right; } else if (data < to_be_removed->data) { to_be_removed = to_be_removed->left; } else found = true; }

if (!found) return;

// to_be_removed contains data // If one of the children is empty, use the other

if (to_be_removed->left == NULL || to_be_removed->right == NULL) { TreeNode1* new_child; if (to_be_removed->left == NULL) new_child = to_be_removed->right; else new_child = to_be_removed->left; if (to_be_removed->parent == NULL) // Found in root root = new_child; else if (to_be_removed->parent->left == to_be_removed) to_be_removed->parent->left = new_child; else to_be_removed->parent->right = new_child; // assign parent if(new_child != NULL) // to_be_removed can be leaf node new_child->parent = to_be_removed->parent; // free memory delete to_be_removed; return; }

// Neither subtree is empty

// Find smallest element of the right subtree

TreeNode1* smallest = to_be_removed->right; while (smallest->left != NULL) smallest = smallest->left; // smallest contains smallest child in right subtree

// Move contents, unlink child to_be_removed->data = smallest->data; if (smallest->parent == to_be_removed) smallest->parent->right = smallest->right; else smallest->parent->left = smallest->right;

// set parent link if (smallest->right != NULL) // smallest can be leaf node smallest->right->parent = smallest->parent; // free memory delete smallest; }

bool TreeNode1::find(string value) const { if (value < data) { if (left == NULL) return false; else return left->find(value); } else if (data < value) { if (right == NULL) return false; else return right->find(value); } else return true; }

void TreeNode1::print_nodes() const { if (left != NULL) left->print_nodes(); cout << data << " "; if (right != NULL) right->print_nodes(); }

TreeIterator& BinarySearchTree::begin() { // create new iterator from root TreeIterator* iter = new TreeIterator(root); return *iter; }

TreeIterator::TreeIterator(TreeNode1* root) { // initailize current node current = root; // set left most node as current node if (current != NULL) { while (current->left != NULL) current = current->left; } }

string TreeIterator::get() { if (current != NULL) { return current->data; } return ""; }

TreeNode1* TreeIterator::next() { if (current == NULL) return NULL; // If the current node has a right child, // then the next node is the leftmost leave of the right child if (current->right != NULL) { current = current->right; while (current->left != NULL) current = current->left; } else { // If the current node does not have a right child, // keep moving up to the parent until the previously // traversed node is a left child while (current->parent != NULL && current->parent->left != current) current = current->parent; // The next node is the parent of this left child current = current->parent; } return current; }

int main() { BinarySearchTree t; t.insert("D"); t.insert("B"); t.insert("A"); t.insert("C"); t.insert("F"); t.insert("E"); t.insert("I"); t.insert("G"); t.insert("H"); t.insert("J");

cout << "Print tree from iterator:" << endl; TreeIterator iter = t.begin(); do { cout << iter.get() << " "; } while (iter.next() != NULL); cout << endl;

t.erase("A"); // Removing leaf t.erase("B"); // Removing element with one child t.erase("F"); // Removing element with two children t.erase("D"); // Removing root t.print(); cout << t.count("E") << " "; cout << t.count("F") << " "; cout << "Print tree from iterator after delete:" << endl; iter = t.begin(); do { cout << iter.get() << " "; } while (iter.next() != NULL); cout << endl;

return 0;

update.