BST (Binary Search Tree) in C++

Creation of BST(binary Search Tree),Insertion at any point,Deletion At any point,Maximum Value,Minimum Value,Searching in tree 

[[Important Data Structure Codes in C++]]
Tree Non Liner Data Structure


#include<iostream.h>
#include<conio.h>
class Node{
private:
int data;
Node* right;
Node* left;
public:
Node(){
root=NULL;
right=left=NULL;
}Node *root;

void insert(int data){

Node* newnode = new Node();

newnode->data = data;
if (root == NULL){
root=newnode;
return;
}
Node *p,*q;
p=q=root;
while (q!=NULL){
p=q;
if (newnode->data> q->data)
q = q->right;
else q = q->left;
}
if (newnode->data> p->data)
p->right = newnode;
else p->left = newnode;
}

Node* remove(Node *root, int value){
Node *t;
int cmp = value - root->data;

if (cmp < 0){
t = remove(root->left, value);
root->left = t;
}
else if (cmp > 0){
t = remove(root->right, value);
root->right = t;
}
else if (root->left != NULL && root->right != NULL){
Node* minNode;
minNode = findMin(root->right);
root->data = minNode->data;
t = remove(root->right, minNode->data);
root->right = t;
}
else {

Node* nodeToDelete = root;
if (root->left == NULL) //will handle 0 children
root = root->right;
else if (root->right == NULL)
root = root->left;
else root = NULL;
delete nodeToDelete;
}

return root;
}

Node* findMin(Node* tree)
{
if (tree == NULL)
return NULL;
if (tree->left == NULL)
return tree;
return findMin(tree->left);
}

void inorder(Node *root){
if (root == NULL) return;
else {
inorder(root->left);
cout << root->data <<"  ";
inorder(root->right);
}
}



void search(Node *root,int v)
{
Node *q=root;
while(v != q->data)
{
if(v < q->data)
{
q=q->left;
}
else
{
q=q->right;
}
}
cout<<"\nNode is  found= "<<q->data<<endl;

}

Node *min_value(Node *r)
{
Node *q=r;
Node *p;
if(q!=NULL)
{
p=q;
q=q->left;
min_value(q);
 }
else
cout<<"\n Minimum Value = "<<p->data<<endl;
return q;

}

Node  *max_value(Node *r)
{
Node *q=r;
Node *p;
if(q!=NULL)
{
p=q;
q=q->right;
max_value( q);
}
else
cout<<"\n Maximum Value= "<<p->data<<endl;
return q;
}
};

void main()
{
int c,A[]={9,4,3,2,5,6,8,1,33,12,44};
Node b;
clrscr();
for(int i=0;i<=10;i++){
b.insert(A[i]); }
b.inorder(b.root);
getch();cout<<"\n\nEnter Value For Search ";cin>>c;
b.search(b.root,c); getch();
b.min_value(b.root);getch();
b.max_value(b.root);getch();
cout<<"\n\nEnter Value For Delete: ";cin>>c;
b.remove(b.root, c);
b.inorder(b.root);getch();
cout<<"\n\nInsert a New Value ";cin>>c;
b.insert(c);
b.inorder(b.root);
getch();

}



0 comments:

Post a Comment

My Instagram