//
For More:> Sorting......, selection sort..., merge sort....., insertion Sort....., General Tree.... and many more......
#include "stdafx.h"
#include <iostream.h>
#include <process.h> //for exit(1)
#include <conio.h>
struct node{
int data;
struct node *left;
struct node *right;
};
class BST{
public:
node *tree;
BST(){
tree=NULL;
}
void createTree(node **,int item); //For Building Tree
void preOrder(node *); //For Tree Traversal
void inOrder(node *);
void postOrder(node *);
void determineHeight(node *,int *);
int totalNodes(node *);
int internalNodes(node *); //no. of non-leaf nodes
int externalNodes(node *); //no. of leaf nodes.
void removeTree(node **); //Remove tree from memory.
node **searchElement(node **,int);
void findSmallestNode(node *);
void findLargestNode(node *);
void deleteNode(int);
};
//it is used for inseting an single element in//a tree, but if calls more than once will create tree.
void BST :: createTree(node **tree,int item){
if(*tree == NULL){
*tree = new node;
(*tree)->data = item;
(*tree)->left = NULL;
(*tree)->right = NULL;
}
else{
if( (*tree)->data > item)
createTree( &((*tree)->left),item);
else
createTree( &((*tree)->right),item);
}
}
void BST :: preOrder(node *tree){
if( tree!=NULL){
cout<<" "<< tree->data;
preOrder(tree->left);
preOrder(tree->right);
}
}
void BST :: inOrder(node *tree){
if( tree!=NULL){
inOrder( tree->left);
cout<<" "<< tree->data;
inOrder(tree->right);
}
}
void BST :: postOrder(node *tree){
if( tree!=NULL){
postOrder( tree->left);
postOrder( tree->right);
cout<<" "<<tree->data;
}
}
void BST :: determineHeight(node *tree, int *height){
int left_height, right_height;
if( tree == NULL)
*height = 0;
else{
determineHeight(tree->left, &left_height);
determineHeight(tree->right, &right_height);
if( left_height > right_height)
*height = left_height + 1;
else
*height = right_height + 1;
}
}
int BST :: totalNodes(node *tree){
if( tree == NULL)
return 0;
else return( totalNodes(tree->left) + totalNodes(tree->right) + 1 );
}
int BST :: internalNodes(node *tree){
if( (tree==NULL) || (tree->left==NULL && tree->right==NULL))
return 0;
else return( internalNodes(tree->left) + internalNodes(tree->right) + 1 );
}
int BST :: externalNodes(node *tree){
if( tree==NULL )
return 0;
else
if( tree->left==NULL && tree->right==NULL)
return 1;
else return( externalNodes(tree->left) + externalNodes(tree->right));
}
void BST :: removeTree(node **tree){
if( (*tree) != NULL)
{
removeTree( &(*tree)->left );
removeTree( &(*tree)->right );
delete( *tree );
}
}
node ** BST :: searchElement(node **tree, int item){
if( ((*tree)->data == item) || ( (*tree) == NULL) )
return tree;
else if( item < (*tree)->data);
return searchElement( &(*tree)->left, item)
else return searchElement( &(*tree)->right, item)
}
void BST :: findSmallestNode(node *tree){
if( tree==NULL || tree->left==NULL)
cout<< tree->data;
else
findSmallestNode( tree->left);
}
//Finding In_order Successor of given node..//for Delete Algo.
node * find_Insucc(node *curr)
{
node *succ=curr->right; //Move to the right sub-tree.
if(succ!=NULL){
while(succ->left!=NULL) //If right sub-tree is not empty.
succ=succ->left; //move to the left-most end.
}
return(succ);
}
void BST :: findLargestNode(node *tree){
if( tree==NULL || tree->right==NULL)
cout<<tree->data;
else
findLargestNode(tree->right);
}
void BST :: deleteNode(int item){
node *curr=tree,*succ,*pred;
int flag=0,delcase;
//step to find location of node
while(curr!=NULL && flag!=1)
{
if(item < curr->data){
pred = curr;
curr = curr->left;
}
elseif(item > curr->data){
pred = curr;
curr = curr->right;
}
else{ //curr->data = item
flag=1;
}
}
if(flag==0){
cout<<"\nItem does not exist : No deletion\n";
getch();
goto end;
}
//Decide the case of deletion
if(curr->left==NULL && curr->right==NULL)
delcase=1; //Node has no child
else
if(curr->left!=NULL && curr->right!=NULL)
delcase=3; //Node contains both the child
else
delcase=2; //Node contains only one child//Deletion Case 1
if(delcase==1){
if(pred->left == curr) //if the node is a left child
pred->left=NULL; //set pointer of its parent
else
pred->right=NULL;
delete(curr); //Return deleted node to the memory bank.
}
//Deletion Case 2
if(delcase==2){
if(pred->left==curr){ //if the node is a left child
if(curr->left==NULL)
pred->left=curr->right;
else
pred->left=curr->left;
}
else{ //pred->right=curr
if(curr->left==NULL)
pred->right=curr->right;
else
pred->right=curr->left;
}
delete(curr);
}
//Deletion case 3
if(delcase==3){
succ = find_Insucc(curr); //Find the in_order successor//of the node.
int item1 = succ->data;
deleteNode(item1); //Delete the inorder successor
curr->data = item1; //Replace the data with the data of//in order successor.
}
end:
}
void main(){
BST obj;
int choice;
int height=0,total=0,n,item;
node **tmp;
while(1){
clrscr();
cout<<"*****BINARY SEARCH TREE OPERATIONS*****\n\n";
cout<<"--Binary Tree and Binary Search Tree common operations--\n";
cout<<"1) Create Tree\n";
cout<<"2) Traversal\n";
cout<<"3) Height of Tree\n";
cout<<"4) Total Nodes\n";
cout<<"5) Internal Nodes \n";
cout<<"6) External Nodes \n";
cout<<"7) Remove Tree\n";
cout<<"\n--Only Binary Search Tree Operations--\n";
cout<<"8) Insert Node\n";
cout<<"9) Search Node\n";
cout<<"10) Find Smallest Node\n";
cout<<"11) Find Largest Node\n";
cout<<"12) Delete Node\n";
cout<<"13) Exit\n";
cout<<"Enter your choice : ";
cin>>choice;
switch(choice){
case 1 : //Create Tree
cout<<"\n\n--Creating Tree--";
cout<<"\nHow many nodes u want to enter : ";
cin>>n;
for(int i=0;i<n;i++){
cout<<"Enter value : ";
cin>>item;
obj.createTree(&obj.tree,item);
}
break;
case 2 : //All Traversals
cout<<"\n\nInorder Traversal : ";
obj.inOrder(obj.tree);
cout<<"\n\nPre-order Traversal : ";
obj.preOrder(obj.tree);
cout<<"\n\nPost-order Traversal : ";
obj.postOrder(obj.tree);
getch();
break;
case 3 : //Determining Height of Tree
obj.determineHeight(obj.tree,&height);
cout<<"\n\nHeight of Tree : "<<height;
getch();
break;
case 4 : //Total nodes in a tree
total=obj.totalNodes(obj.tree);
cout<<"\n\nTotal Nodes : "<<total;
getch();
break;
case 5 : //Internal nodes in a tree
total=obj.internalNodes(obj.tree);
cout<<"\n\nInternal Nodes : "<<total;
getch();
break;
case 6 : //External nodes in a tree
total=obj.externalNodes(obj.tree);
cout<<"\n\nExternal Nodes : "<<total;
getch();
break;
case 7 : //Remove Tree from memory
obj.removeTree(&obj.tree);
cout<<"\n\nTree is removed from Memory";
getch();
break;
case 8 : //Inserting a node in a tree
cout<<"\n\n--Inserting Node in a tree--\n";
cout<<"Enter value : ";
cin>>item;
obj.createTree(&obj.tree,item);
cout<<"\nItem is inserted\n";
getch();
break;
case 9 : //Search element
cout<<"\n\n--Search Element--\n";
cout<<"Enter item to searched : ";
cin>>item;
&(*tmp) = obj.searchElement(&obj.tree,item);
if( (*tmp) == NULL)
cout<<"\nSearch Element Not Found";
else
cout<<"\nSearch Element was Found";
getch();
break;
case 10 : //Find Smallest Node
cout<<"\n\nSmallest Node is : ";
obj.findSmallestNode(obj.tree);
getch();
break;
case 11 : //Find Largest Node
cout<<"\n\nLargest Node is : ";
obj.findLargestNode(obj.tree);
getch();
break;
case 12 : //Deleting a node from a tree
cout<<"\n\n--Deleting a Node from a tree--\n";
cout<<"Enter value : ";
cin>>item;
obj.deleteNode(item);
break;
case 13 : exit(1);
}//end of switch
}
}
Dear Readers if you have any query/question feel free to ask me via comment box given below. Also Follow us on social media site and share that post with your friends. - See more at: http://onlinecomputercafe.blogspot.com
