Data Structure LAb 10
Source Code:
#include <iostream>
using namespace std;
struct tree
{
int num;
tree*left=NULL;
tree*right=NULL;
};tree*root=NULL;
tree*nodeptr=NULL;
//add tree
void add(int n)
{
tree* t=new tree;
t->num=n;
t->left=NULL;
t->right=NULL;
bool flag=false;
if(root==NULL)
{
root=t;
flag=true;
}
else
{
nodeptr=root;
while(nodeptr!=NULL)
{
if(n<nodeptr->num)
{
if(nodeptr->left!=NULL)
{
nodeptr=nodeptr->left;
}
else
{
nodeptr->left=t;
flag=true;
break;
}
}
else if(n>nodeptr->num)
{
if(nodeptr->right!=NULL)
{
nodeptr=nodeptr->right;
}
else
{
flag=true;
nodeptr->right=t;
break;
}
}
else
{
cout<<"Duplicate NUmber \n";
break;
}
}
}
if(flag==true)
cout<<"Value is entered \n";
else
cout<<" Not Entered \n";
}
//.search
void search(int n)
{
tree*temp=root;
bool flag=false;
int countnode=0;
while(temp!=NULL)
{
countnode++;
if(temp->num==n)
{flag=true;
break;
}
else if(n<temp->num)
{
temp=temp->left;
}
else
{
temp=temp->right;
}
}
if(flag==true)
cout<<"Value is found at the node no "<<countnode<<endl;
else
cout<<"Not found \n";
}
//Max min
void min(tree*root) {
if (root == NULL) {
cout << "Tree is Empty" << endl;
}
else {
tree *nodeptr = root;
while (nodeptr->left != NULL) {
nodeptr = nodeptr->left;
}
cout << "Minimum Value in the Tree is : " << nodeptr->num << endl;
}
}
void max(tree*root) {
if (root == NULL) {
cout << "Tree is Empty" << endl;
}
else {
tree *nodeptr = root;
while (nodeptr->right != NULL) {
nodeptr = nodeptr->right;
}
cout << "Maximum Value in the Tree is : " << nodeptr->num << endl;
}
}
//delete
tree *Delete(tree *nodeptr, int data) {
bool flag=false;
if (nodeptr == NULL)
return nodeptr;
else if (data < nodeptr->num)
nodeptr->left = Delete(nodeptr->left, data);
else if (data > nodeptr->num)
nodeptr->right = Delete(nodeptr->right, data);
else {
if (root == nodeptr && nodeptr->left == NULL && nodeptr->right == NULL) {
cout << "Root Null" << endl;
root = NULL;
}
if (nodeptr->left == NULL && nodeptr->right == NULL) {
cout << "Left Right Null" << endl;
delete nodeptr;
flag=true;
nodeptr = NULL;
}
else if (nodeptr->left == NULL) {
cout << "Left is null" << endl;
tree *temp = nodeptr;
if (nodeptr == root) {
cout << "Root left" << endl;
root = nodeptr->right;
}
nodeptr = nodeptr->right;
delete temp;
flag=true;
}
else if (nodeptr->right == NULL) {
cout << "Right is Null" << endl;
tree *temp = nodeptr;
if (nodeptr == root) {
cout << "Root left" << endl;
root = nodeptr->left;
}
nodeptr = nodeptr->left;
delete temp;
flag=true;
}
else {
cout << "Else is running" << endl;
tree *temp = nodeptr->right;
while (temp->left) {
temp = temp->left;
}
nodeptr->num = temp->num;
nodeptr->right = Delete(nodeptr->right, temp->num);
}
}
if(flag==true)
cout<<"Deleted Sucessfully \n";
else
cout<<"VAlue not found \n";
return nodeptr;
}
// void display
void display(tree* ndeptr)
{
if (root == NULL) {
cout << "Tree is empty" << endl;
}
else {
if (ndeptr != NULL) {
display(ndeptr->left);
cout << ndeptr->num << " ";
display(ndeptr->right);
}
else {
return;
}
}
}
int main()
{
int ch;
do{
cout<<"*******************************\n";
cout<<" BInary Search Tree \n";
cout<<"*******************************\n";
cout<<"1: Enter NUmber in TRee \n";
cout<<"2: Find a node In tree \n";
cout<<"3: Find MAx And Min number of Tree \n";
cout<<"4: Delete Node From Tree \n";
cout<<"5: display all \n";
cout<<"6: Exit \n";
cout<<"*******************************\n";
cout<<"ENter Choice: ";
cin>>ch;
switch(ch)
{case 1:
{ int num;
cout<<"Enter Number: ";
cin>>num;
add(num);
break;
}
case 2:
{
int num;
cout<<" FInd The Number you want to find: ";
cin>>num;
search(num);
break;
}
case 3:
{
min(root);
max(root);
break;
}
case 4:
{ int num;
cout<<"Enter NUmber to delete: ";
cin>>num;
Delete(root,num);
break;
}
case 5:
{
display(root);
cout<<endl;
break;
}
default:
cout<<"Invalid \n";
}
}while(ch!=6);
}
Comments
Post a Comment