### Binary Search Tree Manipulation (Fresh Look Please)

After doing a lot of looking I think there is something wrong with my removemin function. Could someone look it over and see if anything is wrong.

mybst.h

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166`` ``````//*************************************************************************** // mybyst.h * // by Dr. Stockwell * // Giselle Colon * // Programming II MW 4:15 * // Due October 17, 2012 * // Assingment 4 * //*************************************************************************** #ifndef MY_BINARY_SEARCH_TREE #define MY_BINARY_SEARCH_TREE #include #include #include using namespace std; template struct BinaryNode{ T data; BinaryNode *left, *right; BinaryNode(){ left = right = 0; } BinaryNode(const T& value): data(value){ left = right = 0; } }; template class BST{ protected: BinaryNode *root; public: explicit BST(){root=0;} BinaryNode *getroot(){return root;} virtual ~BST(){nuke(root);} bool is_empty(){return root==0;} int height(){return height(root);} int height(BinaryNode *p){ if(p){ int h1 = height(p->left); int h2 = height(p->right); return h1 > h2 ? 1+h1: 1+h2; } else return 0; } void nuke(){nuke(root);} void nuke(BinaryNode * & t){ if(t){ nuke(t->left); nuke(t->right); delete t; } t=0; } int size(){return size(root);} int size(BinaryNode *t){ if(t) return 1 + size(t->left) + size(t->right); else return 0; } BinaryNode *find(T item){return find(item, root);} BinaryNode *find(T item, BinaryNode *t){ if(!t) return 0; if(t->data == item) return t; else if(item < t->data) return find(item, t->left); else return find(item, t->right); } void print_tree(){print_tree(root);} void print_tree(BinaryNode *p){ static int ct = 0; if(p){ print_tree(p->left); cout << fixed << setw(10) << p->data; if(++ct % 7 == 0) cout << endl; print_tree(p->right); } } BinaryNode *findmin(BinaryNode *t){ if(t) if(t->left) return findmin(t->left); else return t; else return 0; } BinaryNode *removemin(BinaryNode *t){ if(t){ if(t > t->right) return removemin(t->right); else return t; } else return 0; } void remove(const T& item){remove(item, root);} void remove(const T& item, BinaryNode * & t){ BinaryNode *p; if(!t){ cout << "\nError, cannot delete item, not found.\n"; return; } if(item < t->data) remove(item, t->left); else if(t->data < item) remove(item, t->right); else{ // t points to item to be deleted if(t->left != 0 && t->right != 0){ // node has 2 children p = removemin(t->data); delete p; } else{ // 1 child or none p=t; t=t->right ? t->right : t->left; delete p; } } } void dump_array(T x[], BinaryNode *p){ static int j = 0; if(p){ dump_array(x, p->left); x[j++] = p->data; dump_array(x, p->right); } } void dump_array(T x[]){ dump_array(x, root); } void insert(const T& item){insert(item, root);} void insert(const T& item, BinaryNode * & t){ if(!t){ t= new BinaryNode(item); } else{ if(item < t->data){ insert(item, t->left); } else{ if(item > t->data){ insert(item, t->right); } else{ // duplicate, do not insert it if(item == t->data){ cout << "\nDuplicate item not inserted...\n"; } else{ cout << "There was a problem." << endl; } } } } } }; #endif ``````

four.cpp

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748`` ``````//*************************************************************************** // Giselle Colon * // Programming II MW 4:15 * // Due October 17,2012 * // Assignment 4 * //*************************************************************************** // Basic binary search tree manipulation // Insert, traverse, delete #include #include "mybst.h" using namespace std; int main(){ int a = 0; int count = 0; int b[]={58,12,80,75,204,4,18,13,14,15,28,31,40}; int i = 0; cout << "Hello this is the program for binary search tree manipulation" << endl; BSTbst; bst.insert(58); bst.insert(12); bst.insert(80); bst.insert(75); bst.insert(204); bst.insert(4); bst.insert(18); bst.insert(13); bst.insert(14); bst.insert(15); bst.insert(28); bst.insert(31); bst.insert(40); bst.print_tree(); cout << endl; cout << "**********" << endl; bst.remove(12); bst.print_tree(); cout << endl; return 0; }``````
Last edited on
Topic archived. No new replies allowed.