Binary Search Tree

[oamsath]

Hello.

I'm trying to complete the code for BST ..I'm finding trouble with the delete function ..

input :: integer
process :: deletes the node containing that integer
output :: void

i've to consider the following cases :
1 - node is the root .. therefore I've to delete it (no parents)
2 - node has only one child .. therefore I've to link it with child and delete it
3 - node has two children .. therefore I've to do two things
(i) find the replacement ( easy : go one step left then many steps right untill NULL is found and its value is stored in original node value )
(ii) set the pointer pointing to the replacement to NULL (can't do)

can anyone help me ??

I've searched many books including data structures but couldn't find an answer.
if anyone already written the code paste it here (even without commenting) and i will understand it.

thanks in advance.

[oamsath]

Update :

I've done all the testcases .. except one

I need a function that when sent a pointer to a certain node ( with no children ) it deletes it and set its parent to null

thanks

[jsmith]

Take a pointer "prev" to the root node. Do a depth-first search until
prev->left or prev->right is equal to the pointer passed to your function.
Now prev points to the parent of the node you want to delete.

[oamsath]

can you paste your code here 4 me ?

it is a bit hard for me (i'm only begining in data structures)..

And it is due to end in 48 hours :(

[Maimaje Bello Abdullahi]

#include<iostream>
using namespace std;


struct Tree
{
Tree *left;
int value;
Tree *right;
};

Tree *root;

void Inorder();
void Preorder();
void Postorder();
void create(Tree *ptr,Tree *newnode);
struct Tree *stree(Tree *root,Tree *r,char info);
void Display(Tree *r,int rt);


int main(void)
{
char s, ans;
root = NULL;

do
{
cout<<"Enter a letter: ";
cin>>s;
root=stree(root, root, s);

cout<<"\nDo u want to continue: ";
cin>>ans;

}while(ans !='n');

Display(root, 0);

return 0;
}

void Display(Tree *r,int rt)
{
int i;

if(!r)
return;

Display(r->right,rt+1);

for(i=0;i<rt;++i)
{
cout<<" ";
cout<<r->value;
Display(r->left,rt+1);
}
}

struct Tree *stree(Tree *root,Tree *r,char info)
{
if(!r)
{
r = new Tree[sizeof(struct Tree)];
if(!r)
{
cout << "Out of Memory\n";
exit(0);
}
r->left = NULL;
r->right = NULL;
r->value = info;

if(!root)
return r;
}
/* first entry */
if(info < root->value)
{
root->left = r;
}
else
root->right = r;

return r;


if(info < r->value)

stree(r, r->left, info);
else
stree(r, r->right, info);

return root;
}


void create(Tree *ptr,Tree *newnode)
{
if(newnode->value<=ptr->value)
{
if(ptr->left != NULL)
{
create(ptr->left,newnode);
}
else
{
ptr->left = newnode;
}
if(ptr->right != NULL)
{
create(ptr->right,newnode);
}
else
{
ptr->right = newnode;
}
}
}

void Inorder()
{
Tree *ptr;

if(ptr)
{
ptr->left;
cout<<ptr->value;
ptr->right;
}
}
void Preorder()
{
Tree *ptr;

if(ptr)
{
cout<<ptr->value;
ptr->left;
ptr->right;
}
}

void Postorder()
{
Tree *ptr;

if(ptr)
{
ptr->left;
ptr->right;
cout<<ptr->value;
}
}


I think this may help you