### Help extracting nodes from binary search tree

I was wondering if you could assist me with my binary search tree. I have this code so far and I want to try and make it do two more things for me. I want it to extract the smallest number in the tree with extractMin and return that value to me, then I would like for it to also have an extract function that uses extractMin if needed but I want to be able to give it a number and it looks for that number regardless where it is in the tree and simply remove it and keeps the rest of the tree intact. I have some ideas but then I realized that I would end up losing nodes or doing too much work, etc... if I were to do that. Can anyone help?

 ``12345678910111213141516171819202122232425`` ``````#include #include "binarySearchTree.h" using namespace std; int main() { binarySearchTree tree; tree.insert(53); tree.insert(11); tree.insert(7); tree.insert(5); tree.insert(2); tree.insert(23); tree.display(); tree.height(); tree.extractmin(); //tree.remove(); return 0; }``````

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105`` ``````#include using namespace std; class binarySearchTree { private: class node { public: int data; node * left; node * right; node(int x) { data = x; left = NULL; right = NULL; } }; node * root; //recursive methods void recInsert(int x, node * &r) { if( r == NULL ) { r = new node(x); } else { if( x < r->data ) { recInsert(x, r->left); } else { recInsert(x, r->right); } } } //display items in tree rooted at r void recDisplay(node * r) { if( r != NULL ) { recDisplay(r->left); cout << r->data << endl; recDisplay(r->right); } } //return height of tree rooted at r int getHeight( node * r ) { // Max is the greatest height below (*r), temp is just used to avoid calling getHeight(r->right) twice int max=0,temp=0; // Recurse down lhs if (r->left!=NULL) max=getHeight(r->left); // Recurse down rhs if (r->right!=NULL) temp=getHeight(r->right); if (temp>max) max=temp; // Return the max return max+1; } void extractMin(node * &r) { // Recurse down lhs if (r->left!=NULL) extractMin(r->left); } public: binarySearchTree() { root = NULL; } void insert(int x) { recInsert(x, root); } //display all items in tree void display() { recDisplay(root); } void height() { cout<
Last edited on
Topic archived. No new replies allowed.