Search more programs

Find Your Lab Assignment Here.

(Just click on your assignment to find the C code for problem)



Q. Write C language based code to create and operate on ADT : Binary Search Tree with unique positive integer values as Key Vaues:

 (1). Create a BST with a single node as its Root Node;
(2). Add a node with a given Key Value (give error message, if Key Value already exists, else add a node); 
(3). Given a Key Value, delete a node if it exists; else give error message that the Key Value does not exist; 
(4). Perform search for a given Key Value; if it exists, output " Element Found", else output "Doesn't Exist in the tree";
(5). Check whether it is a complete binary tree or not;
(6). Find Height of the Binary Search Tree;
(7). Find Difference b/w left and right subtree's heights;


Q. Write C language based code to create and operate on ADT : Binary Search Tree with unique positive integer values as Key Vaues:
(1). Create a BST with a single node as its Root Node;
(2). Add a node with a given Key Value (give error message, if Key Value already exists, else add a node); 
(3). Given a Key Value, delete a node if it exists; else give error message that the Key Value does not exist; 
(4). Perform search for a given Key Value; if it exists, output " Element Found", else output "Doesn't Exist in the tree";
(5). Perform In-order, Pre-order, Post-order traversal of a given BST and print Key Values in a row, separated by vertical bars; 


No comments:

C Program to construct Max Heap and Sort an Array based on Heap Sort Algorithm

".C" file is available in downloadable format at :



(Open the link and click on the download arrow on the top right to download the file.)

Given below is the code for "C Program to construct Max Heap and Sort an Array based on Heap Sort Algorithm" :

-----------------------------------------------------------------------------------

#include <stdio.h>
 
void main()
{
int heap[10], no, i, j, c, root, temp;
 
printf("\nEnter no of elements :");
scanf("%d", &no);
printf("\nEnter the nos : ");
for (i = 0; i < no; i++)
scanf("%d", &heap[i]);
for (i = 1; i < no; i++)
{
c = i;
do
{
   root = (c - 1) / 2;             
if (heap[root] < heap[c]) /* to create MAX heap array */
{
       temp = heap[root];
       heap[root] = heap[c];
       heap[c] = temp;
}
   c = root;
} while (c != 0);
}
 
printf("Here's the max Heap : ");
for (i = 0; i < no; i++)
printf("%d\t", heap[i]);
for (j = no - 1; j >= 0; j--)
{
temp = heap[0];
heap[0] = heap[j]; /* swap max element with rightmost leaf element */
heap[j] = temp;
root = 0;
do 
{
   c = 2*root + 1; /* left node of root element */
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
   root = c;
}
while (c < j);
} 
printf("\nThe sorted array is : ");
for (i = 0; i < no; i++)
printf("\t %d", heap[i]);
printf("\nComplexity :  Best case = Avg case = Worst case = O(n logn) \n");
}
No comments:

Video by distanceedjohn on Insertion in 2-3 Trees

Here's a tutorial video, that will be very helpful in understanding Insertion in 2-3 Trees.

Video by : distanceedjohn

If you already know insertion algortihm...you may pause the video, solve the question, and cross verify your answer.

1 comment:

C program for implementation of graph : Creation of adjacency matrix and checking connections

".C" file is available in downloadable format at :



(Open the link and click on the download arrow on the top right to download the file.)


Given Below is the code for implementation of stack using Linked List:



---------------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
#define M 5

void readgraph ();

int a[M][M];

void main ()
{
int s,t, choice;

printf("\nHello and Welcome to graphs.\n\n");

printf("\nFirst of all, enter the graph");
readgraph();

while (1)
{
printf("\n\n1.Check connections\n2.Exit\nYour choice : ");
scanf("%d", &choice);

switch (choice)

 {
case 1:
{
printf("\nEnter the indices to check whether points A and B are connected or not : ");
printf("\nFirst Index:   "); scanf("%d", &s);
printf("\nSecond Index:   "); scanf("%d", &t);
if ( a[s][t] == 1 )
printf("\n Yes, they are connected");

else 
printf("\n No, they are not connected");
}

case 2 : 
exit(0);

default : 
printf("\nEnter valid option");
}
}

void readgraph ()
{
int i,j, choice, num;

printf("\nWhat's the number of entries?\nWell, it's : ");
scanf("%d", &num);
printf ("\nKey in 1 for Yes and 0 for No");

for(i=1; i<=num; i++)
{
for (j=1; j<=num; j++)
{
if (i==j)
a[i][j] =0;
else
{
printf("\nIs %d connected to %d : ", i,j);
scanf("%d", &choice);
if (choice==1)
a[i][j] = 1;
else
a[i][j] = 0;
}
}
}
return;
}


1 comment:

C program for conversion of Array to Heap

Write C language based code to take an array (A) of unsorted positive integers (00 to 99) as input and construct an array B which is equivalent to Max-Heapified Left-justified, Balanced Binary Tree.

".C" file is available in downloadable format at :



(Open the link and click on the download arrow on the top right to download the file.)

Given below is the code for "C program for conversion of Array to Binary Heap" :


-----------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define MAX 20

 void maxheapify(int* , int, int);
int* buildmaxheap(int*, int);

 void main()
{
    int i, t, n;
    int *a  = malloc(MAX*sizeof(int)); //or int a[MAX];
    int *m = malloc(MAX*sizeof(int)); //or int m[MAX];
    printf("Enter no of elements in the array\n");
    scanf("%d", &n);
    printf("Enter the array\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    m = buildmaxheap(a, n);
    printf("The heap is\n");
    for (t = 0; t < n; t++) {
        printf("%d\n", m[t]);
    }
}

 int* buildmaxheap(int a[], int n)
{
    int heapsize = n;
    int j;
    for (j = n/2; j >= 0; j--)
    {
        maxheapify(a, j, heapsize);
    }
    return a;
}

 void maxheapify(int a[], int i, int heapsize)
{
    int temp, largest, left, right, k;
    left = (2*i+1);
    right = ((2*i)+2);
    if (left >= heapsize)
        return;
    else {
        if (a[left] > a[i])
            largest = left;
        else
            largest = i;
        if (right < (heapsize) && a[right] > a[largest])
            largest = right;
        if (largest!= i)
        {
            temp = a[i];
            a[i] = a[largest];
            a[largest] = temp;
          maxheapify(a, largest, heapsize);
        }
    }
}
2 comments:

C program for Advanced BST, with calculation of height and checking whether it is complete BST or not

Q. Write C language based code to create and operate on ADT : Binary Search Tree with unique positive integer values as Key Vaues:

(1). Create a BST with a single node as its Root Node;

(2). Add a node with a given Key Value (give error message, if Key Value already exists, else add a node); 

(3). Given a Key Value, delete a node if it exists; else give error message that the Key Value does not exist; 

(4). Perform search for a given Key Value; if it exists, output " Element Found", else output "Doesn't Exist in the tree";

(5). Check whether it is a complete binary tree or not;

(6). Find Height of the Binary Search Tree;

(7). Find Difference b/w left and right subtree's heights;


".C" file is available in downloadable format at :



(Open the link and click on the download arrow on the top right to download the file.)

Given below is the code for "C program for Advanced BST, with calculation of height and checking whether it is complete BST or not" :


-----------------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
#define size 30

typedef struct tree
{
int info;
struct tree* left;
struct tree* right;
}node;

node* create (node*); 
void insert (node*, node*);
node* search (node*, int);
node* del (node*, int);
node* display(node*);
int height (node*);
int diffheights ();

node* create (node* root)
{
int no,ele,i=0;
node* n=NULL;
node *key;

printf("\nNumber of entries:\t");
scanf("%d", &no);

while (i<no)
{
printf("\n----------------------------------INSERT------------------------------------");
printf("\nEnter data:\t");
scanf("%d", &ele);
if (ele> 0)
{
key= search(root, ele);
if (key==NULL)
{
n=(node*)malloc(sizeof(node));
n->info = ele;
n->left=NULL; 
n->right=NULL;

if(root==NULL)
{
printf("\nIt's the first element of the tree.");
root=n;
}
else
{
insert(n, root);
}
i++;
}
else 
printf("The node data: %d already exists in the tree.",ele);
}
else printf("\nOnly Positive integers are allowed");
}
return root;
}


void insert (node* nw, node* root)
{
node *p;
node *q;
p=root; q=root;

while(q!=NULL)
{
p=q;

if(nw->info>q->info)
q=q->right;

else
q=q->left;
}

if (p->info > nw->info)
{
p->left = nw;
}
else
{
p->right = nw;
}
}


node* search(node* root, int ele)
{
node *q;
q=root;

while((q!=NULL)&&(q->info!=ele))
{
if(q->info>ele)
q=q->left;
else
q=q->right;
}
return q;
}


node* del(node* root, int ele)
{
node* p , *q;

p=root;
while((p!=NULL)&&(p->info!=ele))
{
q=p;
if(p->info > ele)
p = p->left;

else
p=p->right;
}
if((p->right==NULL)&&(p->left==NULL))
{
if (q->info>ele)
q->left=NULL;
else
q->right=NULL;
}
if((p->left==NULL)&&(p->right!=NULL))
{
if (q->info>ele)
q->left=p->right;
else
q->right=p->right;
}
if((p->right==NULL)&&(p->left!=NULL))
{
if (q->info>ele)
q->left=p->left;
else
q->right=p->left;
}
if((p->left!=NULL)&&(p->right!=NULL))
{
node *s, *r = p->left;
while(r->right!=NULL)
{
s=r;
r=r->right;
}
p->info = r->info;
s->right = r-> left;
}
return root;
}


node* display (node* q)
{
if(q!=NULL)
 {
 q->left=display(q->left);
 printf("  |  %d  |  ", q->info);
 q->right=display(q->right);
 }
 return q;
}  

int height (node* p)
{
if(p==NULL)
return 0;

else
{
int leftheight  = height(p->left);
int rightheight = height(p->right);
if(leftheight>rightheight)
{
return leftheight+1;
}
else
{
return rightheight+1;
}
}
}

int diffheights (node* p)
{
int diff;
int leftheight  = height(p->left);
int rightheight = height(p->right);
if(leftheight>rightheight)
{
diff = (-1)*(leftheight-rightheight);
}
else
{
diff = (rightheight-leftheight);
}
return diff;
}

void main()
{
node *root=NULL, *q;
int choice, ele, h, dif;

while(1)
{
printf("\n\n\n1. Create\n2. Search\n3. Delete a node.\n4. Display (Inorder)\n5. Is it a Complete Binary Tree?\n6. Height\n7. Difference b/w left and right heights.\n8. Exit program.\n\nEnter your choice:\t");
scanf("%d", &choice);

switch(choice)
{
case 1: root=create(root); printf("\n\nCREATED"); break;

case 2: printf("Enter value to be searched:\t"); scanf("%d", &ele); q= search(root, ele); 
if(q==NULL) 
{
printf("\n%d doesn't exist in the tree.", ele);
}
else 
{
printf("\n%d found",q->info);
} break;

case 3: printf("Enter value to be deleted:\t"); 
scanf("%d", &ele); 
if(search(root, ele)==NULL) 
printf("\nERROR: The value doesnot exist"); 
else 
root = del(root, ele); printf("\nDeleted !"); break;

case 4: display (root); break;

case 5: if(root==NULL)
printf ("\nThe tree is Empty");
else
{
if(diffheights(root)) 
printf("\n Nope !"); 
else printf("\n Yes, it is.");
} 
break; 

case 6: h = height(root); printf("\nHeight = %d\n", h); break;

case 7: dif = diffheights(root);
if(dif==0) 
printf("\nIt's a complete binary tree, difference is zero!"); 
if (dif<0)
printf("Height of Left subtree is greater than Right subtree by %d", (-1)*(dif));
if(dif>0)
printf("Height of Right subtree is greater than Left subtree by %d", dif);
break;

       case 8: if(root==NULL) 
        printf("\nExiting with empty tree\n\n"); 
        else 
        {
        root->right=NULL; root->left=NULL; 
        free(root); 
        printf("\nTree Cleared !\n\n");
        } exit(0);


default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");
}


}
}
1 comment:
Subscribe to: Posts (Atom)