Tree traversal (preorder,inorder,postorder) using linklist (c++)

#include<iostream>
using namespace std;

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

/**********Element insertion*****************/

node* insert(node *root,int data)
{
    if(root==NULL)
    {
        root=new node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
    {
        root->left=insert(root->left,data);
    }
    else
    {
        root->right=insert(root->right,data);
    }
    return root;
}

/*************Printing in preorder*************/

void preorder(node *root)
{
    if(root==NULL)
    return;

    cout<<" "<<root->data;
    preorder(root->left);
    preorder(root->right);
}

/**************printing in inorder************/

void inorder(node *root)
{
    if(root==NULL)
    return;

    inorder(root->left);
    cout<<" "<<root->data;
    inorder(root->right);
}

/**********printing in postorder************/

void postorder(node *root)
{
    if(root==NULL)
    return;
    postorder(root->left);
    postorder(root->right);
    cout<<" "<<root->data;

}

/**************Driver Function***********/
int main()
{
    node *root=NULL;

    root=insert(root,10);
    root=insert(root,20);
    root=insert(root,30);
    root=insert(root,15);
    root=insert(root,9);
    root=insert(root,25);


    cout<<"\n preorder"<<endl;
    preorder(root);
    cout<<"\n Inorder"<<endl;
    inorder(root);
    cout<<"\n Postorder"<<endl;
    postorder(root);
    cout<<endl;


    return 0;
}

output:

Read More

Implementation of queue using linklist (C++)

#include<iostream>
using namespace std;

struct queue
{
    int data;
    struct queue *next;
};

 queue *front=NULL;
 queue *rear=NULL;
    int count=0;
/**********Inserting Element in Queue******************/
void enqueue(int x)
{
  queue *temp;
  temp=new queue();
  temp->data=x;
  temp->next=NULL;
  if(front==NULL && rear==NULL)
  {
      front=rear=temp;
      count++;
  }
  else
  {
      rear->next=temp;
      rear=temp;
      count++;
  }
}
/*********displaying elements in Queue********************/

void display(int count)
{
    queue *temp;
    temp=front;
    for(int i=0;i<count;i++)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
/*******Removing element from Queue*********************/

void dequeue()
{
    if(front==NULL)
    {
        cout<<"Queue is empty"<<endl;
    }
    else
    {
        queue *temp;
        temp=front;
        front=front->next;
        delete temp;
        count--;

        cout<<" \n Item Dequeued Successfully"<<endl;
    }
}

/****************Driver Function************************/

int main()
{
    int choice;
    int x;
    do
    {
        cout<<"Enter element is Queue :"<<endl;
        cin>>x;
        enqueue(x);


    cout<<"Do you want to enQueue again?"<<endl;
    cin>>choice;
    }while(choice==1);

    cout<<"After Enqueue"<<endl;
    display(count);

    do
    {
    dequeue();
    cout<<"Do you want to DeQueue again?"<<endl;
    cin>>choice;
    }while(choice==1);

    cout<<"After dequeue"<<endl;
    display(count);

    return 0;

}

Read More

Circular queue using array(insertion, deletion)

#include <iostream>

using namespace std;

int Q[10];

int size=10;

int count=0;

int rear=0;

int front=0;

void enQ(int element)

{

   if(count==size)

   {

       cout<<"Queue Overflow"<<endl;

   }

   else

   {

       Q[rear]=element;

       rear=(rear+1)%size;

       count++;

   }

}

void DeQ()

{

    if(count==0)

    {

        cout<<"Under Flow"<<endl;

    }

    else

    {

        Q[front]=0;

        front=(front+1)%size;

        count--;

    }

}

bool isempty()

{

    if(count==0)

    {

        return true;

    }

}

int main()

{

    int element;

    int e;

    if(isempty()==true)

    {

        cout<<"Queue is empty"<<endl;

    }

    /*************Enqueue*************/

    do

    {

    cout<<"Enter element in queue:"<<endl;

    cin>>element;

    enQ(element);

    cout<<"Do you want enqueue again?" <<endl;

    cin>>e;

    }while(e==1);

    /************display*************/

    cout<<"After inserting value in circular queue"<<endl;

    for(int i=front;i<=count;i++)

    {

        cout<<Q[i]<<" ";

    }

    /***************deletion***************/

    int d;

    cout<<"Do you want to delete from the queue(1=y): "<<endl;

    cin>>d;

    if(d==1)

    {

        int c;

        do

        {

        DeQ();

        cout<<"DO you want to enqueue again?(1=y)"<<endl;

        cin>>c;

        }while(c==1);

    }

    /************display*************/

    cout<<"After Dequeuing"<<endl;

    for(int i=front;i<=count;i++)

    {

        cout<<Q[i]<<" ";

    }

    return 0;

}

Read More

Doubly Linklist (insertion,deletion of a node)

#include <iostream>
using namespace std;
struct node2
{
    int data2;
    struct node2 *previous;
    struct node2 *next2;
};
int main()
{
    node2 *head2;
    node2 *last2;
    node2 *temp2;
    last2=0;
    int choice;
    do
    {
    cout<<"Enter data in Doubly node:"<<endl;
    temp2=new node2();
    cin>>temp2->data2;
    if(last2==0)
    {
        temp2->next2=0;
        temp2->previous=0;
        last2=head2=temp2;
    }
    else
    {
        temp2->next2=0;
        temp2->previous=last2;
        last2->next2=temp2;
        last2=temp2;
    }
    cout<<"\nDo you want to create a new node (1=yes,0=NO): ";
    cin>>choice;
    }while(choice==1);
    cout<<"Printing from start"<<endl;
    temp2=head2;
    while(temp2!=0)
    {
      cout<<temp2->data2<<" ";
     temp2=temp2->next2;
    }
    cout<<"\n Printing from end"<<endl;
    temp2=last2;
    while(temp2!=0)
    {
      cout<<temp2->data2<<" ";
     temp2=temp2->previous;
    }
   /******************************************/
       do
    {
    cout<<"Enter data"<<endl;
    temp2=new node2();
    cin>>temp2->data2;
    if(last2==0)
    {
        temp2->next2=0;
        temp2->previous=0;
        last2=head2=temp2;
    }
    else
    {
        temp2->next2=head2;
        temp2->previous=0;
        head2->previous=temp2;
        head2=temp2;
    }
    cout<<"\nDo you want to create a new node (1=yes,0=NO): ";
    cin>>choice;
    }while(choice==1);
    cout<<"\n Printing from start"<<endl;
    temp2=head2;
    while(temp2!=0)
    {
      cout<<temp2->data2<<" ";
     temp2=temp2->next2;
    }
    return 0;
}

Read More

Singly Linklist in C++ (insertion at satart,middle and end. Searching in linklist. Deletion of any node)

#include <iostream>

using namespace std;
struct node
{
    int data;
    struct node *next;
};

int main()
{
    node *head;
    node *temp;
    node *last;

    last=0;
    int choice;

   do
    {
        temp=new node();
        cout<<"Enter values in a node:"<<endl;
        cin>>temp->data;
        if(last==0)
        {
            head=last=temp;

        }
        else
        {
            last->next=temp;
            last=temp;
        }
        cout<<"Enter your choice:"<<endl;
        cin>>choice;
    }while(choice==1);

        last->next=0;
        temp=head;

        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        /************insertion at the start of the node***************************/
        do{
        temp=new node();
        cout<<"Enter value at the start of the node: "<<endl;
        cin>>temp->data;

        temp->next=head;
        head=temp;

        cout<<"Enter your choice: "<<endl;
        cin>>choice;
        }while(choice==1);

        temp=head;
        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;

        }

        /************** iNSERTION AT MIDDLE OF THE LINKLIST***********/
        node *temp2;
        int location=0;

        cout<<"\n Enter your location"<<endl;
        cin>>location;

        temp=new node();
        cout<<"\n Enter data in node: "<<endl;
        cin>>temp->data;

        temp2=head;

        while(location-1>0)
        {
            location--;
            temp2=temp2->next;
        }
        temp->next=temp2->next;
        temp2->next=temp;

        temp=head;
        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }

    /**************************Search traverse*************/
    int value;
    int count=1;
    int flag=0;
    cout<<"\n Enter value you want to search in LinkList: "<<endl;
    cin>>value;
    temp=head;
    while(temp!=0)
    {
        if(temp->data==value)
        {
            cout<<"Data found successfully at index "<<count<<endl;
            flag=1;
            break;
        }
        else
        {
            temp=temp->next;
            count++;
        }
    }

    if(flag==0)
    {
        cout<<"Data not found"<<endl;
    }
    /**************************deleting node******************/
    int b=0;
    int item;
    node *temp3;
    cout<<"which data do you want to delete?"<<endl;
    cin>>item;
    temp=head;
    while(temp->next->next!=0)
    {
        if(temp->next->data==item)
        {
            cout<<"Data found successfully"<<endl;
            b=1;
            break;
        }
        else
        {
            temp=temp->next;
            temp3=temp->next;
        }
    }

    if(b==0)
    {
        cout<<"Data not found"<<endl;
    }
    else
    {
        temp->next=temp->next->next;
        delete temp3;
    }

    temp=head;
        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }


    return 0;
}

Read More

Binary Search in C++

#include <iostream>
using namespace std;

void binarysearch(int arr[],int s,int size);
void binarysearch(int arr[],int s,int size)
{
    int lower=0,higher=size-1,m;
    while(lower<=higher)
    {
        m=(lower+higher)/2;
        if(s==arr[m])
        {
        cout<<"Search found at index"<<m<<endl;
        return;
        }
        else if(s>arr[m])
            lower=m+1;
        else
            higher=m-1;
    }
    cout<<"Search not found"<<endl;
}

/******************************************/

int main()
{
    int n[5],s,size;
    cout<<"Enter value in array of type int:"<<endl;
    for(int i=0;i<5;i++)
    {
     cin>>n[i];
    }
    cout<<"Enter number in Search: ";
    cin>>s;
    size=sizeof(n)/sizeof(n[0]);
    binarysearch(n,s,size);
    return 0;
}

Read More

Selection sorting Dynamically

Worst-Complexity: n ^ 2

Average-Complexity: n ^ 2

Best-Complexity: n ^ 2

Space-Complexity:  1

#include<iostream>
using namespace std;

/*********************sorting function********************/

void selection_Sort(int arr[], int n)
{
    int i, j, min;

    for (i = 0; i < n-1; i++)
    {
        min = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min])
            min = j;

          swap(arr[min],arr[i]);
    }
} 

 /****************** Printing values*****************************/

void print_Array(int arr[], int size) 

{ 

    int i; 

    for (i=0; i < size; i++) 

        cout<<arr[i];

cout<<endl; 

} 

/**********************Driver function*************************/

int main() 

{ 

int *arr;

int n;

cout<<"How many numbers your want to sort:"<<endl;

    cin>>n;

    arr=new int[n];

    cout<<"Enter the numbers:"<<endl;

for(int i=0;i<n;i++)

{

cin>>arr[i];

}    

selection_Sort(arr, n); 

    cout<<"After sorting array: \n"<<endl; 

    print_Array(arr, n); 

    return 0; 

} 

Read More

A Program which uses linear searching? C++

Starts from the base index and compare it with the rest of the element of an array. If the serached index found, it returns 1 else it returns -1.

#include<iostream>
using namespace std;
/********************************************/

int linearSearch(int n[],int s,int size)

    {

        for(int i=0;i<size;i++)

        {

            if(n[i]==s)

            {

            return i;

            }

        }

        return -1;

    }

/*********************************************/

int main()

{

   int n[10];

   int s;

   int result;

   cout<<"Enter values in 'int' array"<<endl;

    for(int j=0;j<10;j++)

    {

    cin>>n[j];

    }

   cout<<"Enter number to search in array"<<endl;

   cin>>s;

   int size=sizeof(n)/sizeof(n[0]);

   result=linearSearch(n,s,size);

   if(result==-1)

   {

       cout<<"Value not found!"<<endl;

    }

    else

    {

    cout<<"value is on index"<<result<<endl;

    }

       return 0;

}

Read More

Quick sorting program

Worse case performance: O(n^2)
Best case performance: O(nlogn)
Average performance: O(nlogn)


#include <iostream>
void quicksort(int arr[],int low,int high);
int partition(int arr[],int low,int high);
using namespace std;
/***********************************/
int partition(int arr[],int low,int high)
{
    int pivot,i;
    pivot=arr[high];
    i=low-1;

    for(int j=low; j<high; j++)
    {
        if(arr[j]<=pivot)
        {
            i++;
            swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[high]);
    return(i+1);
}
/*********************************/
void quicksort(int arr[],int low, int high)
{
    if(low<high)
    {
    int pivot;
    pivot=partition(arr,low,high);

    quicksort(arr,low,pivot-1);
    quicksort(arr,pivot+1,high);
    }
}
/*********************************/
int main()
{
    int arr[5]={5,4,3,2,1};
    int n=5;
    cout << "Before sorting values is: ";
    for(int i=0;i<n;i++)
    {
    cout<<arr[i]<<" ";
    }
    quicksort(arr,0,n-1);
    cout<<"\n After sorting: ";
    for(int i=0;i<n;i++)
    {
    cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Read More

Insertion sorting using pointers and function

Write a program for insertion sorting. 

 

#include <iostream>

using namespace std;

void insertionSort(int *p,int size);

void insertionSort(int *p,int size)

{

    int i,j,temp;

    for(i=1;i<size;i++)

    {

        temp=p[i];

        j=i-1;

        while(j>=0 && p[j]>temp)

        {

            p[j+1]=p[j];

        j--;

        }

        p[j+1]=temp;

    }

    for(i=0;i<size;i++)

    {

        cout<<p[i]<<" ";

    }

}

int main()

{

    int n;

    int *p;

    cout<<"Enter number of element you want to store in an a array:"<<endl;

    cin>>n;

    p=new int[n];

    cout<<"Now enter the values"<<endl;

    for(int i=0;i<n;i++)

    {

        cin>>p[i];

    }

    insertionSort(p,n);

}

Insertion sorting using pointers and function

Checkout more java programs on Zamacodes.com

         

Read More