Using C++

The following functions require implementation:

//Precondition: root_ptr points to a binary tree with at least one node //Postcondition: Height of the tree is returned recursively, recall that a tree  // with one node is height of 0 and an empty tree has a height of -1 long bst_height(const binary_tree_node* root_ptr) const; //Precondition: Tree has at least one node, ie height >= 0 //Precondition: Inserts newDataItem into the binary search tree in the correct spot. void bst_insert( const Item& ,binary_tree_node*); //Precondition: root_ptr is a root pointer of a binary search tree //Postcondition: Returns true if target is in the BST, false otherwise bool in_bst(const Item& target, binary_tree_node* root_ptr); //Precondition: root_ptr is a root pointer of a binary search tree or may be // NULL for an empty tree). //Postcondition: If target was in the tree, then one copy of target has been  // removed, and root_ptr now points to the root of the new  // (smaller) binary search tree. In this case the function returns true. // If target was not in the tree, then the tree is unchanged (and the // function returns false). bool bst_remove(const Item& target, binary_tree_node*& node_ptr); //1 : tree is emtpy //2 : Tree not empty, target < than root //3 : tree not empty, target > than root //4 target == root node, do not need to check, if not < or >, than it is == //4a The root node has no left child //4bThe root does have a left child //Precondtion: root_ptr is a root pointer of a non-empty binary search tree //Postcondition: The largest item in the BST bas been removed, and the root_ptr // now points to the root of the new (smaller) BST. The reference parameter, // removed, has been set to a copy of the removed item. void bst_remove_max(binary_tree_node*& root_ptr, Item& removed);

Driver

#include  #include "bintree.h" #include "bstree.h" using namespace std; using namespace DS; int main() { bstree bst; bst.insert(5); bst.insert(15); bst.insert(25); bst.insert(22); bst.insert(-29); bst.insert(29); bst.insert(2); bst.insert(19); bst.insert(30); bst.insert(40); bst.insert(4); bst.insert(-34); bst.prettyprint(); cout << "Height:" << bst.height() << endl; cout << "Preorder:" << endl; bst.preorderprint(); cout << "Inorder:" << endl; bst.inorderprint(); cout << "Postorder:" << endl; bst.postorderprint(); cout << bst.in_bst(15) << endl; cout << bst.in_bst(30) << endl; bst.prettyprint(); cout << "==================" << endl; bst.bst_remove(25); bst.prettyprint(); cout << "==================" << endl; bst.bst_remove(29); bst.prettyprint(); cout << "==================" << endl; bst.bst_remove(5); bst.prettyprint(); cout << "==================" << endl; return 0; }

Additional Criteria

Zero credit will be earned for any lab that contains a loop.

Make sure you have no memory leaks. No usage of STL except string, queue, and iostream in the driver.

Example Output

 40 30 29 25 22 19 15 5 4 2 -29 -34 Height:5 Preorder: ->5->-29->-34->2->4->15->25->22->19->29->30->40 Inorder: ->-34->-29->2->4->5->15->19->22->25->29->30->40 Postorder: ->-34->4->2->-29->19->22->40->30->29->25->15->5 1 1 40 30 29 25 22 19 15 5 4 2 -29 -34 ================== 40 30 29 22 19 15 5 4 2 -29 -34 ================== 40 30 22 19 15 5 4 2 -29 -34 ================== 40 30 22 19 15 4 2 -29 -34 ==================