Help extracting nodes from binary search tree
Jan 31, 2013 at 8:02pm UTC
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?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
#include <iostream>
#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;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
#include <iostream>
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<<getHeight(root)<<endl;
}
void extractmin()
{
extractMin(root);
}
};
Last edited on Feb 1, 2013 at 2:06am UTC
Topic archived. No new replies allowed.