Deleting from Binary search tree implementation in C++
|
Download Attachment
|
#include < iostream.h> #include < conio.h> #include < malloc.h>
struct tree { struct tree *left; int info; struct tree *right; }*root,*ptr,*newnode,*par,*stack[100],*child;
int loc=0;
void create(); void find(int); void traverse(); void del(int);
void main() { int i,item; clrscr(); for(i=0;i<5;i++) { create(); } cout<<"\nEnter the item you want to delete from tree: "; cin>>item; del(item); }
void create() { int item; cout<<"\nEnter the info: "; cin>>item; find(item); if(loc==1) { traverse(); } else { newnode=(struct tree*)malloc(sizeof(struct tree)); newnode->info=item; newnode->left=NULL; newnode->right=NULL; if(par==NULL) { root=newnode; } else if(iteminfo) { par->left=newnode; } else { par->right=newnode; } traverse(); } }
void del(int item) { struct tree *save,*suc,*parsuc,*temp; find(item); if(loc==0) { cout<<"\nItem is not in the tree"; traverse(); } else { if((ptr->right!=NULL)&&(ptr->left!=NULL)) { temp=ptr->right; save=ptr; while(temp->left!=NULL) { save=temp; temp=temp->left; } suc=temp; parsuc=save;
//ptr=suc; //par=parsuc; if((temp->left==NULL)&&(temp->right==NULL)) { child=NULL; } else if(temp->left!=NULL) { child=temp->left; } else { child=temp->right; } if(parsuc!=NULL) { if(temp==parsuc->left) { parsuc->left=child; } else { parsuc->right=child; } } else { root=child; } if(par!=NULL) { if(ptr==par->left) { par->left=suc; } else { par->right=suc; } } else { root=suc; } suc->left=ptr->left; suc->right=ptr->right; } else { if((ptr->left==NULL)&&(ptr->right==NULL)) { child=NULL; } else if(ptr->left!=NULL) { child=ptr->left; } else { child=ptr->right; } if(par!=NULL) { if(ptr==par->left) { par->left=child; } else { par->right=child; } } else { root=child; } } cout<<"\nAfter deletion tree is:\n"; traverse(); } }
void find(int item) { struct tree *save; if(root==NULL) { loc=0; par=NULL; return; } else if(item==root->info) { loc=1; ptr=root; par=NULL; return; } else if(iteminfo) { ptr=root->left; save=root; } else { ptr=root->right; save=root; }
while(ptr!=NULL) { if(item==ptr->info) { loc=1; par=save; return; } else if(iteminfo) { save=ptr; ptr=ptr->left; } else { save=ptr; ptr=ptr->right; } } loc=0; par=save; }
void traverse() { int top=0; stack[0]=NULL; ptr=root; cout<<"\nTree is:\n"; while(ptr!=NULL) { cout<info<<" "; if(ptr->right!=NULL) { top=top+1; stack[top]=ptr->right; } if(ptr->left!=NULL) { ptr=ptr->left; } else { ptr=stack[top]; top=top-1; } } getch(); }
|
|
|
|
|
Share this article
| Print |
Article read by 3099 times
|
|
|