Binary Search Tree
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Binary Search Tree as PDF for free.
More details
- Words: 440
- Pages: 5
/*
C++ Program for the Binary Search Tree ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/
#include class bin_tree { private: typedef struct node { int data; struct node *lc; struct node *rc; }N; N *root; public : bin_tree() { root=NULL; } void create() { char ans; int item; /* cout<<"\n Enter the value for the root node : "; cin>>item; root = new N; root->data=item; */ while(1) { cout<<"\n\n Enter the value for the node(-999 to stop) : ";
cin>>item; if(item == -999) return; insert(root,item);
} }
void insert(N * & tn,int item) { if(tn == NULL) {
tn = new tn->data tn->lc = tn->rc =
}
N; = item; NULL; NULL;
else { if(item < tn->data) insert(tn->lc,item); else }
insert(tn->rc,item);
}
int search ( N * &parent,N * &req_node,int item) { N *temp; temp=root; parent=NULL; while(temp != NULL) { if(temp->data == item) { req_node=temp; return(1); } else if(temp->data > item) { parent=temp; temp=temp->lc; } else { parent=temp; temp=temp->rc; } } }
//
while loop ends
return(0);
void del (int item) { N *parent,*req_node,*node_suc; int search_result = 0; if(root == NULL)
cout<<"\n\n\t The tree is empty !! "; else { parent=NULL; req_node=NULL; search_result = search(parent,req_node,item);
!!";
if(search_result == 0) { cout<<"\n\n Data to be deleted was not found in the tree }
return;
/* if the node to be deleted has two children */ if(req_node->lc != NULL && req_node->rc != NULL) { parent = req_node; node_suc = req_node->rc; while(node_suc->lc != NULL) { parent = node_suc; node_suc = node_suc->lc; }
}
req_node->data = node_suc->data; req_node = node_suc;
/* if the node to be deleted has no children */ if(req_node->lc == NULL && req_node->rc == NULL) { if(parent->rc == req_node) parent->rc = NULL; else
}
parent->lc = NULL;
delete (req_node);//free(req_node); return;
/* if the node to be deleted has only right child */ if(req_node->lc == NULL && req_node->rc != NULL) { if(parent->lc == req_node) parent->lc = req_node->rc;
else
}
parent->rc = req_node->rc;
delete (req_node);//free(req_node); return;
/* if the node to be deleted has only left child */ if(req_node->lc != NULL && req_node->rc == NULL) { if(parent->lc == req_node) parent->lc = req_node->lc; else
}
parent->rc = req_node->lc;
delete (req_node);//free(req_node); return;
} // outer else ends } void inorder(N *in_root) { if(in_root == NULL) return; inorder(in_root->lc); cout<<" "<data; inorder(in_root->rc); } N * root_val() { return(root); } };
void main() { bin_tree T; int item;
cout<<"\t\t cout<<"
C++ Program for the Binary Search Tree\n" "\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n"; Creating the Binary Search Tree\n" " -----------------------------------\n\n";
T.create(); cout<<"\n\n\n is:\n\n\t";
The created Binary Search Tree according to in-order traversal
T.inorder(T.root_val()); cout<<"\n\n\n cin>>item;
Enter the item to be deleted : ";
T.del(item); cout<<"\n\n\n
The Binary Search Tree after deletion of the item is :\n\n\t";
T.inorder(T.root_val()); }
C++ Program for the Binary Search Tree ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/
#include
cin>>item; if(item == -999) return; insert(root,item);
} }
void insert(N * & tn,int item) { if(tn == NULL) {
tn = new tn->data tn->lc = tn->rc =
}
N; = item; NULL; NULL;
else { if(item < tn->data) insert(tn->lc,item); else }
insert(tn->rc,item);
}
int search ( N * &parent,N * &req_node,int item) { N *temp; temp=root; parent=NULL; while(temp != NULL) { if(temp->data == item) { req_node=temp; return(1); } else if(temp->data > item) { parent=temp; temp=temp->lc; } else { parent=temp; temp=temp->rc; } } }
//
while loop ends
return(0);
void del (int item) { N *parent,*req_node,*node_suc; int search_result = 0; if(root == NULL)
cout<<"\n\n\t The tree is empty !! "; else { parent=NULL; req_node=NULL; search_result = search(parent,req_node,item);
!!";
if(search_result == 0) { cout<<"\n\n Data to be deleted was not found in the tree }
return;
/* if the node to be deleted has two children */ if(req_node->lc != NULL && req_node->rc != NULL) { parent = req_node; node_suc = req_node->rc; while(node_suc->lc != NULL) { parent = node_suc; node_suc = node_suc->lc; }
}
req_node->data = node_suc->data; req_node = node_suc;
/* if the node to be deleted has no children */ if(req_node->lc == NULL && req_node->rc == NULL) { if(parent->rc == req_node) parent->rc = NULL; else
}
parent->lc = NULL;
delete (req_node);//free(req_node); return;
/* if the node to be deleted has only right child */ if(req_node->lc == NULL && req_node->rc != NULL) { if(parent->lc == req_node) parent->lc = req_node->rc;
else
}
parent->rc = req_node->rc;
delete (req_node);//free(req_node); return;
/* if the node to be deleted has only left child */ if(req_node->lc != NULL && req_node->rc == NULL) { if(parent->lc == req_node) parent->lc = req_node->lc; else
}
parent->rc = req_node->lc;
delete (req_node);//free(req_node); return;
} // outer else ends } void inorder(N *in_root) { if(in_root == NULL) return; inorder(in_root->lc); cout<<" "<
void main() { bin_tree T; int item;
cout<<"\t\t cout<<"
C++ Program for the Binary Search Tree\n" "\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n"; Creating the Binary Search Tree\n" " -----------------------------------\n\n";
T.create(); cout<<"\n\n\n is:\n\n\t";
The created Binary Search Tree according to in-order traversal
T.inorder(T.root_val()); cout<<"\n\n\n cin>>item;
Enter the item to be deleted : ";
T.del(item); cout<<"\n\n\n
The Binary Search Tree after deletion of the item is :\n\n\t";
T.inorder(T.root_val()); }
Related Documents
Binary Search Tree
May 2020 11
Binary Search
July 2020 13
Binary Tree
July 2020 14
Binary Search
October 2019 21
Binary Search
May 2020 11