Binary Search Tree

Binary Search Tree is a binary tree where left child of a node is less than the key of the Parent node and the key in the right child is greater than the parent node.We can design many kind of BST(Binary Search Tree) for some nodes or values.And there average searching time may be different.In Binary Search tree searching is easy. Time complexity of searching in case BST is nlogn.

Binary Tree

Traversal of a Binary Tree: The traversal of binary tree invloves visiting each node in the tree exactly once. Binary tree traversal is usefull in many applications.There are 3 popular method of Binary tree traversal.These methods are:-
1) Inorder Traversal.(Left,Root,Right)
2) Preorder Traversal.(Root,Left,Right)
3) Postorder Traversal.(Left,Right,Root)

 For the above tree:   Inorder Traversal is    5 , 10 , 12 , 20 , 30.
                                    Preorder Traversal is   20 , 10 , 5 , 12 , 30.           

                                    Postorder Traversal is   5 , 12 , 10 , 30 , 20.

 Click here to download the of BST implementation using C++

Stack implementation using C++

stack example

First of all,what is stack? A stack is a data structure in which addition of new element or deletion of existing element always takes place at the same end. The end is often known as Top of Stack. For example a no. of books kept one above another, if we have to keep a new book there, we will kept it above all the books and suppose we have to take out a book at first we will pick the book which is at the top.

Insertion Sort algorithm in C++

Insertion Sort is a sorting algorithm used to sort an array element. From the name of the algorithm itself we can make out that here sorting is done with the help of insertion. Now suppose we are provided with a list of number e.g    18  16  14  17  8 . We have to arrange this number in a sorted order. In Insertion sort what it does that it will  pick the number present at the beginning of the given array say A, and place it in another array say B. And  then next number of the array A is picked up as a Key. Now it will compare  with the number present in array B if it is larger than that number then it will inserted in array B after the smaller number present in the array or if it is smaller than the existing number then it will be placed before the existing element of B. Similarly now the 3rd element is taken up as a Key and same comparison is done again. For rest of the element of array A same comparison is done.Have a look at this example.
       
         

Linked List Implementation using C++

A Linked List is a sequential storage data structure. It provides a more flexible storage system. Linked List overcome the limitations of arrays. In case of array,on writing a program we had to decide the maximum amount of memory that would be needed for our arrays. If the number of element store in the array is less than the maximum size declare then left space is wasted. Linked List overcome this limitation by providing sequential storage mode. A Linked List consist of sequential node that are linked with each other. Each node in a Linked List has two parts. First part contain the data and second part contain the address of the next node.

Merge Sort program in c in a simple way:

/*Merge Sort program in c in a simple way*/

#include<stdio.h>

#include<conio.h>

#include<math.h>

void merge(int a[],int p,int q,int r);

void mergesort(int a[],int p,int r)

{

int q;

if(p<r)

{

  q=floor((p+r)/2);

  mergesort(a,p,q);

  mergesort(a,q+1,r);

  merge(a,p,q,r);

  }

}

int b[5];

void merge(int a[],int p,int q,int r)

{

int i,j,k;

k=0;

i=p;

j=q+1;

while(i<=q && j<=r)

{

if(a[i]<a[j])

b[k++]=a[i++];

else

b[k++]=a[j++];

}

while(i<=q)

b[k++]=a[i++];

while(j<=r)

b[k++]=a[j++];

for(i=r;i>=p;i--)

{

a[i]=b[--k];

}

}

void main()

{

int a[]={12,17,8,6,2};

int i;

clrscr();

mergesort(a,0,5);

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

{

printf("%d\t",a[i]);

}

getch();

}

Simple Linked List Program to add a node

1.Simple linkedlist program to add a node at the front using c++ class.

//this is just a basic program to understand how a node is added into a linkedlist. 

#include<iostream.h>

#include<conio.h>

class node

{

public:

int data;

node *next;

node()

{

data=0;

next=NULL;

}

node(int x)

{

data=x;

next=NULL;

}

};

class linked_list

{

node *head;

public:

int addNodeAtFront(node &n);

void display();

linked_list()

{

head=NULL;

}

};

int linked_list::addNodeAtFront(node &n)           /*method declaraction*/

{

int i=0;

n.next=head;                                                /*here adress inside the head is now given to next

head=&n;                                                                  pointer of node class*/

i=1;

return i;

}

void linked_list::display()

{

node *ptr=head;

while(ptr!=NULL)

  {

  cout<<"\t"<<ptr->data;

  ptr=ptr->next;

  }

}

void main()

{

int x,q;

linked_list l;

clrscr();

cout<<"Enter a value:\t";               

cin>>x;

node n(x);

q=l.addNodeAtFront(n);           /*call to addNodeAtFront method of class Linked_list*/

if(q==1)

  {

  cout<<"Inserted";

  l.display();

  }

 getch(); 

}