Program In C For Insertion, Deletion And Inorder Traversal In A Binary Tree

 #include <stdio.h>
  #include <stdlib.h>

  struct treeNode {
        int data;
        struct treeNode *left, *right;
  };

  struct treeNode *root = NULL;

  /* create a new node with the given data */
  struct treeNode* createNode(int data) {
        struct treeNode *newNode;
        newNode = (struct treeNode *) malloc(sizeof (struct treeNode));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return(newNode);
  }

  /* insertion in binary search tree */
  void insertion(struct treeNode **node, int data) {
        if (*node == NULL) {
                *node = createNode(data);
        } else if (data < (*node)->data) {
                insertion(&(*node)->left, data);
        } else if (data > (*node)->data) {
                insertion(&(*node)->right, data);
        }
  }


  /* deletion in binary search tree */
  void deletion(struct treeNode **node, struct treeNode **parent, int data) {
        struct treeNode *tmpNode, *tmpParent;
        if (*node == NULL)
                return;
        if ((*node)->data == data) {
                /* deleting the leaf node */
                if (!(*node)->left && !(*node)->right) {
                        if (parent) {
                                /* delete leaf node */
                                if ((*parent)->left == *node)
                                        (*parent)->left = NULL;
                                else
                                        (*parent)->right = NULL;
                                free(*node);
                        } else {
                                /* delete root node with no children */
                                free(*node);
                        }
                /* deleting node with one child */
                } else if (!(*node)->right && (*node)->left) {
                        /* deleting node with left child alone */
                        tmpNode = *node;
                        (*parent)->right = (*node)->left;
                        free(tmpNode);
                        *node = (*parent)->right;
                } else if ((*node)->right && !(*node)->left) {
                        /* deleting node with right child alone */
                        tmpNode = *node;
                        (*parent)->left = (*node)->right;
                        free(tmpNode);
                        (*node) = (*parent)->left;
                } else if (!(*node)->right->left) {
                        /*
                         * deleting a node whose right child
                         * is the smallest node in the right
                         * subtree for the node to be deleted.
                         */

                        tmpNode = *node;

                        (*node)->right->left = (*node)->left;

                        (*parent)->left = (*node)->right;
                        free(tmpNode);
                        *node = (*parent)->left;
                } else {
                        /*
                         * Deleting a node with two children.
                         * First, find the smallest node in
                         * the right subtree.  Replace the
                         * smallest node with the node to be
                         * deleted. Then, do proper connections
                         * for the children of replaced node.
                         */
                        tmpNode = (*node)->right;
                        while (tmpNode->left) {
                                tmpParent = tmpNode;
                                tmpNode = tmpNode->left;
                        }
                        tmpParent->left = tmpNode->right;
                        tmpNode->left = (*node)->left;
                        tmpNode->right =(*node)->right;
                        free(*node);
                        *node = tmpNode;
                }
        } else if (data < (*node)->data) {
                /* traverse towards left subtree */
                deletion(&(*node)->left, node, data);
        } else if (data > (*node)->data) {
                /* traversing towards right subtree */
                deletion(&(*node)->right, node, data);
        }
  }

  /* search the given element in binary search tree */
  void findElement(struct treeNode *node, int data) {
        if (!node)
                return;
        else if (data < node->data) {
                findElement(node->left, data);
        } else if (data > node->data) {
                findElement(node->right, data);
        } else
                printf("data found: %d\n", node->data);
        return;

  }

  void traverse(struct treeNode *node) {
        if (node != NULL) {
                traverse(node->left);
                printf("%3d", node->data);
                traverse(node->right);
        }
        return;
  }

  int main() {
        int data, ch;
        while (1) {
                printf("1. Insertion in Binary Search Tree\n");
                printf("2. Deletion in Binary Search Tree\n");
                printf("3. Search Element in Binary Search Tree\n");
                printf("4. Inorder traversal\n5. Exit\n");
                printf("Enter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                while (1) {
                                printf("Enter your data:");
                                scanf("%d", &data);
                                insertion(&root, data);
                                printf("Continue Insertion(0/1):");
                                scanf("%d", &ch);
                                if (!ch)
                                        break;
                                }
                                break;
                        case 2:
                                printf("Enter your data:");
                                scanf("%d", &data);
                                deletion(&root, NULL, data);
                                break;
                        case 3:
                                printf("Enter value for data:");
                                scanf("%d", &data);
                                findElement(root, data);
                                break;
                        case 4:
                                printf("Inorder Traversal:\n");
                                traverse(root);
                                printf("\n");
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("u've entered wrong option\n");
                                break;
                }
        }
        return 0;

  }

Program In C for Depth First Search(DFS) and Breadth First Search(BFS) In A Graph

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

void create();
void dfs();
void bfs();

struct node
{
int data,status;
struct node *next;
struct link *adj;
};

struct link
{
struct node *next;
struct link *adj;
};

struct node *start,*p,*q;
struct link *l,*k;

int main()
{
int choice;
clrscr();
create();
while(1)
{

printf("\n1: DFS 2: BSF 3: Exit\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
printf("Incorrect choice!Re-enter your choice.");
getch();
}
}
return 0;
}

void create()
{
int dat,flag=0;
start=NULL;
printf("Enter the nodes in the graph(0 to end): ");
while(1)
{
scanf("%d",&dat);
if(dat==0)
break;
p=new node;
p->data=dat;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
printf("Enter the links to %d",p->data);
      printf(" (0 to end) : ");
      flag=0;
      while(1)
      {
scanf("%d",&dat);
if(dat==0)
   break;
k=new link;
k->adj=NULL;
if(flag==0)
{
   p->adj=k;
   l=k;
   flag++;
}
else
{
   l->adj=k;
   l=k;
}
q=start;
while(q!=NULL)
{
   if(q->data==dat)
      k->next=q;
   q=q->next;
}
      }
      p=p->next;
   }
   return;
}


void bfs()
{
   int qu[20],i=1,j=0;
   p=start;
   while(p!=NULL)
   {
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
 break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
printf("\nBreadth First Search Results : ");
while(qu[j]!=0)
{
printf("%d  ",qu[j]);
j++;
}
getch();
return;
}



void dfs()
{
int stack[25],top=1;
printf("\nDepth First Search Results : ");

p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
printf("%d  ",stack[top]);
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
   top++;
   stack[top]=q->data;
   q->status=1;
}
k=k->adj;
      }
   }
   getch();
   return;
}

Program In C For Insertion And Deletion In A Linked List

#include<stdio.h>
#include<alloc.h>
#include<conio.h>
struct node
{ int info;
 struct node *next;
 }*start=NULL,*current;
 void insert(int num)
 {
 struct node *new_n=(struct node*)malloc(sizeof(struct node));
 if(start==NULL)
 { start=new_n;
 new_n->info=num;
 new_n->next=NULL; }
 else
 { current=start;
 while(current->next!=NULL)
{ current=current->next;
}
current->next=new_n;
 new_n->info=num;
 new_n->next=NULL; } }
 void deletion()
 {
 printf("%d node deleted ! ",start->info);
 current=start;
 start=start->next;
 free(current);
 }
 void display( )
 { struct node *ptr;
 ptr=start;
 while(ptr!=NULL)
 { printf("%d->",ptr->info);
 ptr=ptr->next; }
 }
void main()
{
int ch,ch1=1,num,c;
clrscr();
again:
printf("Linked List Menu:\n1.Insertion(Press 1)\n2.Deletion(Press2)\n3.Display LInked List(Press 3): \n");
scanf("%d",&ch);
if(ch==1)
{ ch1=1;
while(ch1==1)
{ printf("\nEnter The Number: ");
scanf("%d",&num);
insert(num);
printf("\nLinked List After Insertion Is: \n");
display();
printf("\nDo You Wish To Insert More(Press 1 for yes): ");
scanf("%d",&ch1);}}
if(ch==2)
{ ch1=1;
while(ch1==1)
{ deletion();
printf("\nLinked List After Deletion Is: \n");
display();
printf("\nDo You Wish To Delete More(Press 1 for yes): ");
scanf("%d",&ch1);}}
if(ch==3)
{ display(); }
printf("\n1.Back To Main Menu(Press 1)\n2.Exit(Press 2):");
scanf("%d",&c);
if(c==1)
goto again;
getch();
}

Program In C For Shell Sort

#include<stdio.h>
#include<conio.h>
int main()
{
int arr[10];
int i,j,k,tmp,num;
clrscr();
printf("Enter total no. of elements : ");
scanf("%d",&num);
printf("\nEnter elements : ");
for(k=0; k<num; k++)
{
scanf("%d",&arr[k]);
}
for(i=num/2; i>0; i=i/2)
{
for(j=i; j<num; j++)
{
for(k=j-i; k>=0; k=k-i)
{
if(arr[k+i]>=arr[k])
break;
else
{
tmp=arr[k];
arr[k]=arr[k+i];
arr[k+i]=tmp;
}
}
}
}
printf(" Array After Sorting Is: :  \n");
for(k=0; k<num; k++)
printf("%d\t",arr[k]);
getch();
return 0;
}