Write a Program to implement Binary Search tree as discussed in the Lecture.
The following methods are to be implemented in the Binary Search Tree.
1) insert(key), function which inserts a new element into the tree.
2) remove(key), function which removes the key from the Binary Search Tree
follow these conditions to while removing the element.
i) if the tree-node having key is a leaf node, delete that node.
ii) replace the desired tree node with its child, if that node has only one child.
iii) If the tree node having key, has two non-empty children then use its inorder - predecessor to replace the node. Inorder - predecessor for a tree node is the right most node in its left subtree.
You need to build a binary search tree by inserting elements in the given order.
Then perform insert and remove operations on that tree based on the operation specified as a character (i - insert, d - remove).
Input:
- 1st line has number of elements to be added to the Binary Search Tree (Initial number elements - N)
- 2nd line of the input contains the elements each separated by single whitespace.
- 3rd line has number of operations to be performed (k)
- 4th line has operation, key separated by a white space (i - insert, d - remove)
Sample Input:
4
8 7 15 2
2
i 10 d 2
Output:
The program should output the post order traversal of BST after all the given operations are performed. Separate the elements with a single whitespace. Print “NULL”(without quotes), if the tree is empty.
Output for the above Sample Input:
7 10 15 8
Constraints:
Elements in the binary Search Tree are unique.
0<=N≤ 20
0<=key<=10000 (Elements in Tree)
0<=k<=10Solution -:
After deadline is over
killer, how to define member functions of a class outside the class?
ReplyDeletei am using the usual way of returntype classname member function
i am getting errors like
Program: In function 'treeNode* insert(int)':
Program:91:11: error: 'root' was not declared in this scope
Program:13:6: error: 'int treeNode::data' is private
Program:103:20: error: within this context
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:105:19: error: within this context
Program:13:6: error: 'int treeNode::data' is private
Program:108:25: error: within this context
Program:15:13: error: 'treeNode* treeNode::right' is private
Program:110:19: error: within this context
Program:115:6: error: 'cout' was not declared in this scope
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:121:22: error: within this context
Program:15:13: error: 'treeNode* treeNode::right' is private
Program:122:27: error: within this context
Program: In function 'int removeRoot()':
Program:127:22: error: 'root' was not declared in this scope
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:129:13: error: within this context
Program:15:13: error: 'treeNode* treeNode::right' is private
Program:130:18: error: within this context
Program:15:13: error: 'treeNode* treeNode::right' is private
Program:134:13: error: within this context
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:135:18: error: within this context
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:144:18: error: within this context
Program:15:13: error: 'treeNode* treeNode::right' is private
Program:145:17: error: within this context
Program:15:13: error: 'treeNode* treeNode::right' is private
Program:147:19: error: within this context
Program:13:6: error: 'int treeNode::data' is private
Program:151:11: error: within this context
Program:13:6: error: 'int treeNode::data' is private
Program:151:24: error: within this context
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:152:17: error: within this context
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:153:15: error: within this context
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:153:28: error: within this context
Program:15:13: error: 'treeNode* treeNode::right' is private
Program:155:15: error: within this context
Program:14:13: error: 'treeNode* treeNode::left' is private
Program:155:29: error: within this context
all these are scope related issues...
if you can help me with declaration of member functions used
you cannot declare them outside class.
ReplyDeleteand what is the need to declare them outside?
use friend function concept to access the class that is pre declared .
outside the class function cannot be declared however only called and overridden
okay, will give it a try.
Deletehow to use friend function i too got the above error
DeletetreeNode * binarySearchTree :: insert(int key)
ReplyDelete{
treeNode * temp, *prev;
temp = root;
prev = root;
treeNode * new_node ;
new_node = new treeNode(key);
int flag=0;
if(temp==NULL){
//tree is Empty
root = new_node;
}
while(temp!=NULL){
if(key < temp->data){
prev = temp;
temp = temp->left;
flag=1;
}
else if(key > temp->data){
prev = temp;
temp = temp->right;
flag=2;
}
else{
//key already exists
printf("key already exists\n");
delete new_node;
return NULL;
}
}
//now we assign new_node's parent
if(flag==1) prev->left = new_node;
else if(flag==2) prev->right = new_node;
//new_node->parent = prev;
return new_node;
}
/*treeNode * binarySearchTree :: int removeRoot(){
treeNode * temp = root;
if(temp==NULL) return -1;
if(temp->left==NULL){
root = temp->right;
delete temp;
return 1;
}
if(temp->right==NULL){
root = temp->left;
delete temp;
return 1;
}
else{
//find the inorder-predecessor
//right most child in the left subtree.
treeNode * pred, *predPar;
predPar = temp;
pred = temp->left;
while(pred->right!=NULL){
predPar = pred;
pred = pred->right;
}
//replace temp's data with predecessor's data
//delete predecessor
temp->data = pred->data;
if(predPar->left == pred)
predPar->left = pred->left;
else
predPar->right = pred->left;
delete pred;
return 1;
}
}*/
treeNode * binarySearchTree :: int remove(int key){
treeNode * temp,*prev;
temp=root;
prev=NULL;
int flag=0;
if(root==NULL) return -1;
while(temp!=NULL){
if(key < temp->data){
prev=temp;
temp = temp->left;
flag=1;
}
else if(key > temp->data){
prev=temp;
temp = temp->right;
flag=2;
}
else{
//found the key at temp
break;
}
}
if(temp==NULL){
//key not found
return -1;
}
if(temp==root){
//removing root
return removeRoot();
}
// deleting leaves or internal nodes
else{
if(temp->left==NULL){
if(flag==1)
prev->left = temp->right;
else if(flag==2)
prev->right = temp->right;
delete temp;
return 1;
}
if(temp->right==NULL){
if(flag==1)
prev->left = temp->left;
else if(flag==2)
prev->right = temp->left;
delete temp;
return 1;
}
//both children are not null
else{
//finding the predecessor
treeNode * pred, *predPar;
predPar = temp;
pred = temp->left;
while(pred->right!=NULL){
predPar = pred;
pred = pred->right;
}
//replace temp's data with predecessor's data
//delete predecessor
temp->data = pred->data;
if(predPar->left == pred)
predPar->left = pred->left;
else
predPar->right = pred->left;
delete pred;
return 1;
}
}
}
Program:164:32: error: expected unqualified-id before 'int'
DeleteProgram:164:32: error: expected initializer before 'int'
Inialize the function as: int binarySearchTree :: remove(int key)
Deletecode not working
ReplyDeleteif(temp==root){
ReplyDelete//removing root
return removeRoot(); // where is this function.
}
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteplease put the correct solution asap
ReplyDeletetreeNode * binarySearchTree :: insert(int key){
ReplyDeletetreeNode * temp, *prev;
temp = root;
prev = root;
treeNode * new_node ;
new_node = new treeNode(key);
int flag=0;
if(temp==NULL){
//tree is Empty
root = new_node;
}
while(temp!=NULL){
if(key < temp->data){
prev = temp;
temp = temp->left;
flag=1;
}
else if(key > temp->data){
prev = temp;
temp = temp->right;
flag=2;
}
else{
printf("Key already exist");
delete new_node;
return NULL;
}
}
//now we assign new_node's parent
if(flag==1) prev->left = new_node;
else if(flag==2) prev->right = new_node;
//new_node->parent = prev;
return new_node;
}
int binarySearchTree :: remove(int key){
treeNode * temp,*prev;
temp=root;
prev=NULL;
int flag=0;
if(root==NULL) return -1;
while(temp!=NULL){
if(key < temp->data){
prev=temp;
temp = temp->left;
flag=1;
}
else if(key > temp->data){
prev=temp;
temp = temp->right;
flag=2;
}
else{
//found the key at temp
break;
}
}
if(temp==NULL){
//key not found
return -1;
}
if(temp==root){
//removing root
// return removeRoot();
treeNode * temp = root;
if(temp==NULL) return -1;
if(temp->left==NULL){
root = temp->right;
delete temp;
return 1;
}
if(temp->right==NULL){
root = temp->left;
delete temp;
return 1;
}
else{
//find the inorder-predecessor
//right most child in the left subtree.
treeNode * pred, *predPar;
predPar = temp;
pred = temp->left;
while(pred->right!=NULL){
predPar = pred;
pred = pred->right;
}
//replace temp's data with predecessor's data
//delete predecessor
temp->data = pred->data;
if(predPar->left == pred)
predPar->left = pred->left;
else
predPar->right = pred->left;
delete pred;
return 1;
}
}
// deleting leaves or internal nodes
else{
if(temp->left==NULL){
if(flag==1)
prev->left = temp->right;
else if(flag==2)
prev->right = temp->right;
delete temp;
return 1;
}
if(temp->right==NULL){
if(flag==1)
prev->left = temp->left;
else if(flag==2)
prev->right = temp->left;
delete temp;
return 1;
}
//both children are not null
else{
//finding the predecessor
treeNode * pred, *predPar;
predPar = temp;
pred = temp->left;
while(pred->right!=NULL){
predPar = pred;
pred = pred->right;
}
//replace temp's data with predecessor's data
//delete predecessor
temp->data = pred->data;
if(predPar->left == pred)
predPar->left = pred->left;
else
predPar->right = pred->left;
delete pred;
return 1;
}
}
}