a) Implement a Binary search tree (BST) library (btree.h) with operations – create, search, insert, inorder, preorder and postorder. Write a menu driven program that performs the above operations.
Warshall algorithm #include #define MAX 100 void warshall(int graph[10][10],int n) { int dist[10][10],i,j,k; for (i=0;i<n;i++) { for (j=0;j<n;j++) { dist[i][j]=graph[i][j]; } } for (k=0;k<n;k++) { for (i=0;i<n;i++) { for (j=0;j<n;j++) { if (dist[i][k]+dist[k][j]<dist[i][j]) { dist[i][j]=dist[i][k]+dist[k][j]; } } } } printf("\nShortest distances between every pair of vertices:\n"); for (i=0;i<n;i++) { for (j=0;j<n;j++) { printf("%d\t",dist[i][j]); } printf("\n"); } } int main() { int n,i,j; printf("Enter the number of vertices: "); scanf("%d",&n); int graph[10][10]; printf("Enter the adjacency cost matrix:\n"); for (i=0;i<n;i++) { for (j=0;j<n;j++) { scanf("%d",&graph[i][j]); } } warshall(graph,n); return 0;
#include #include void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void heapify(int arr[], int n, int i) { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] > arr[largest]) { largest = l; } if (r < n && arr[r] > arr[largest]) { largest = r; } if (largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); heapify(arr, i, 0); } } int main() { int n; printf("Enter the number of elements: "); scanf("%d", &n); int arr[n]; printf("Generating %d random numbers...\n", n); for (int i = 0; i < n; i++) { arr[i] = rand() % 100; } printf("Unsorted array:\n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } heapSort(arr, n); printf("\nSorted array:\n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
1. **What is a tree?** - A tree is a hierarchical data structure composed of nodes connected by edges. It consists of a collection of nodes, where each node has a value and a list of references to its child nodes (if any), with one designated as the "root" node.
2. **What is a graph?** - A graph is a collection of nodes (vertices) and edges that connect pairs of nodes. Graphs can be directed (edges have a specific direction) or undirected (edges do not have a direction).
3. **What is hash?** - Hashing is the process of mapping data of arbitrary size to fixed-size values. A hash function is used to generate the hash value, which is typically a unique identifier representing the original data. Hashing is commonly used in data structures like hash tables for fast data retrieval.
4. **What is a binary tree?** - A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
5. **What is an AVL tree?** - An AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of any node is at most one. It ensures that the tree remains balanced, which helps maintain efficient search, insertion, and deletion operations.
6. **Types of AVL rotations?** - There are four types of rotations in AVL trees: - Left Rotation - Right Rotation - Left-Right Rotation (also known as Double Right Rotation) - Right-Left Rotation (also known as Double Left Rotation)
7. **Rules for red-black tree?** - Red-black trees are self-balancing binary search trees with the following rules: 1. Every node is either red or black. 2. The root is always black. 3. Red nodes cannot have red children. 4. Every path from a node to its descendant NIL nodes (leaf nodes) must have the same number of black nodes.
8. **What is a terminal node?** - A terminal node, also known as a leaf node, is a node in a tree data structure that does not have any children.
9. **What is a root node?** - The root node is the topmost node in a tree hierarchy. It is the starting point for traversing the tree and is the only node that does not have a parent.
10. **Type of binary tree?** - There are various types of binary trees, including: - Full binary tree - Complete binary tree - Perfect binary tree - Balanced binary tree
11. **BFS and DFS rules?** - Breadth-First Search (BFS) visits nodes level by level starting from the root. It uses a queue data structure for traversal. - Depth-First Search (DFS) explores as far as possible along each branch before backtracking. It can be implemented using either a stack (for iterative DFS) or recursion.
12. **Preorder, Inorder, Postorder?** - These are different methods for traversing a binary tree: - Preorder: Visit the root node first, then recursively traverse the left subtree, followed by the right subtree. - Inorder: Recursively traverse the left subtree, visit the root node, then recursively traverse the right subtree. - Postorder: Recursively traverse the left subtree, then the right subtree, and finally visit the root node.
24 Comments
This comment has been removed by the author.
ReplyDeleteVisit My page for 2019 Pattern Slip Solutions:
ReplyDeletehttps://computersciencestudyhub.blogspot.com/
For CPP programs visit https://codeforever.in/bcs-lab-book/
ReplyDeleteThanks bro! this info help me lot.
DeleteYou can get solved practical output on Code Forever CPP program
ReplyDeleteCode Forever Data Structure
nice this website has code forever online compiler where we can run our program and check output
DeleteMangesh Borate
ReplyDeletea) Implement a Binary search tree (BST) library (btree.h) with operations – create, search,
ReplyDeleteinsert, inorder, preorder and postorder. Write a menu driven program that performs the above
operations.
Warshall algorithm
ReplyDelete#include
#define MAX 100
void warshall(int graph[10][10],int n)
{
int dist[10][10],i,j,k;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
dist[i][j]=graph[i][j];
}
}
for (k=0;k<n;k++)
{
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
if (dist[i][k]+dist[k][j]<dist[i][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
}
}
}
}
printf("\nShortest distances between every pair of vertices:\n");
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
printf("%d\t",dist[i][j]);
}
printf("\n");
}
}
int main()
{
int n,i,j;
printf("Enter the number of vertices: ");
scanf("%d",&n);
int graph[10][10];
printf("Enter the adjacency cost matrix:\n");
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
scanf("%d",&graph[i][j]);
}
}
warshall(graph,n);
return 0;
Krushkal algorithm
ReplyDelete#include
#include
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
printf("***Krushkal's Algorithm***\n");
printf("Enter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost of adjacency matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
{
cost[i][j]=999;
}
}
}
printf("The edges of minimun cost spanning tree :\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%dEdge(%d,%d)=%d\n",ne++,a,b,min);
mincost+=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\nMinimum Cost=%d\n",mincost);
}
int find(int i)
{
while(parent[i])
{
i=parent[i];
}
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
#include
ReplyDelete#include
typedef struct node
{
int vertex;
struct node *next;
} NODE;
NODE *list[10];
void createmat(int m[10][10],int n)
{
int i,j;
char ans;
for(i=0;ivertex=j+1;
if(list[i]==NULL)
list[i]=temp=newnode;
else
{
temp->next=newnode;
temp=newnode;
}
}
}
}
}
void displist(int n)
{
struct node *temp;
int i;
printf("\n The adjcency list is :\n");
for(i=0;i",i+1);
temp=list[i];
while(temp)
{
printf("v%d->",temp->vertex);
temp=temp->next;
}
printf("NULL");
}
}
void main()
{
int m[10][10],n;
printf("Enter the no of vertices :");
scanf("%d",&n);
createmat(m,n);
dispmat(m,n);
createlist(m,n);
displist(n);
}
Adjacency list
DeletePrims algorithm
ReplyDelete#include
int a,b,u,v,n,i,j,e=1;
int visited[10]= {0},min,mincost=0,cost[10][10];
void main(){
printf("Enter the number of vertices:");
scanf("%d",&n);
printf("Enter the adjacency matrix:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(e<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",e++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
}
Best postorder
ReplyDelete#include
#include
#define NEWNODE (struct node *)malloc(sizeof(struct node))
struct node
{
struct node *left;
int data;
struct node *right;
};
struct node *root;
void init()
{root=NULL;
}
void insert(int item)
{
struct node *t1,*t2,*t;
t=NEWNODE;
t->data=item;
t->left=NULL;
t->right=NULL;
if(root==NULL)
{
root=t;
}
else
{
t1=root;
while(t1!=NULL)
{
t2=t1;
if(item<=t1->data)
t1=t1->left;
else
t1=t1->right;
}
if(item<=t2->data)
t2->left=t;
else
t2->right=t;
}
}
void postorder(struct node *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
printf(" %d ",t->data);
}
}
int main()
{
int n,i,item;
printf("\nHow many item u want to store =");
scanf("%d",&n);
init();
for(i=1;i<=n;i++)
{
printf("\nEnter data = ");
scanf("%d",&item);insert(item);
}
printf("\nDisplaying tree POSTORDER WISE = ");
postorder(root);
return 0;
}
DFS
ReplyDelete#include
#define MAX 10
typedef struct
{
int data[MAX];
int top;
}STACK;
void initstack(STACK * ps)
{
ps->top=-1;
}
void push(STACK *ps, int num)
{
ps->data[++ps->top]=num;
}
int pop(STACK *ps)
{
return(ps->data[ps->top--]);
}
int isempty(STACK *ps)
{
return(ps->top==-1);
}
int isfull(STACK *ps)
{
return (ps->top==MAX-1);
}
void dfs(int m[10][10], int n)
{
int i, v, w, found;
int visited[10]={0};
STACK s;
initstack(&s);
v=0;
visited[v]=1;
push(&s,v);
printf("v%d" ,v+1);
while(1)
{
found=0;
for(w=0; w<n; w++)
{
if((m[v][w]==1)&&(visited[w]==0))
{
push(&s, w);
printf("v%d", w+1);
visited[w]=1;
v = w;
found = 1;
break;
}
}
if(found == 0)// did not find an adjacent unvisited vertex
if(isempty(&s))
break;
else
v = pop(&s);
}
}
int recdfs(int m[10][10], int n, int v)
{
int w;
static int visited[10]={0};
visited[v]=1;
printf("v%d" ,v+1);
for(w=0; w<n; w++)
{
if( (m[v] [w]==1) && (visited[w]==0) )
recdfs(m,n,w);
}
}
int main()
{
int m[10][10], n, i, j, w;
printf("\nHow many vertices:");
scanf("%d", &n);
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
if(i!=j)
{
printf("Is there edge between vertex %d and %d
(1/0):", i+1, j+1);
scanf("%d", &m[i][j]);
}
}
printf("\nNon recursive depth first search is :");
dfs(m,n);
printf("\nRecursive depth first search is :");
recdfs(m,n,0);
}
Nodes at each level
ReplyDelete#include
#include
struct node
{
struct node *left;
int info;
struct node *right;
};
struct node *insert(struct node *ptr, int key )
{
if(ptr==NULL)
{
ptr = (struct node *) malloc(sizeof(struct node));
ptr->info = key;
ptr->left = NULL;
ptr->right = NULL;
}
else if(key info)
ptr->left = insert(ptr->left, key);
else if(key >ptr->info)
ptr->right = insert(ptr->right, key);
else
printf("\nDuplicate key\n");
return(ptr);
}
int NodesAtLevel(struct node *ptr, int level)
{
if(ptr==NULL)
return 0;
if(level==0)
return 1;
return NodesAtLevel(ptr->left,level-1) + NodesAtLevel(ptr->right,level-1);
}
int main()
{
struct node *root=NULL,*root1=NULL,*ptr;
int choice,k,item,level,i;
while(1)
{
printf("\n");
printf("1.Insert Tree \n");
printf("2.Number of Nodes present at any level\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter number of nodes : ");
scanf("%d",&k);
for(i=1;i<=k;i++)
{
printf(“enter data for node”,i);
scanf("%d",&item);
root = insert(root, item);
}
break;
case 2:printf("\n");
printf("Enter any level :: ");
scanf("%d",&level);
printf("\nNumber of nodes at [ %d ] Level :: %d\n",level,NodesAtLevel(root,level));
break;
case 4:exit(1);
default:
printf("\nWrong choice\n");
}
}
return 0;
}
Heap sort
ReplyDelete#include
#include
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Generating %d random numbers...\n", n);
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
printf("Unsorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
heapSort(arr, n);
printf("\nSorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
BFS search (breath first' search)
ReplyDelete#include
#define MAX 10
typedef struct
{
int data[MAX];
int front, rear;
}QUEUE;
void initq(QUEUE *pq)
{
pq->front = pq->rear = -1;
}
void addq(QUEUE *pq, int num)
{
pq->rear++;
pq->data[pq->rear] = num;
}
int removeq(QUEUE *pq)
{
int num;
pq->front++;
num=pq->data[pq->front];
return(num);
}
int isempty(QUEUE *pq)
{
return(pq->front == pq->rear);
}
int isfull(QUEUE *pq)
{
return(pq->rear==MAX-1);
}
void bfs(int m[10][10], int n)
{
int i, v, w;
int visited[10]={0};
QUEUE q;
initq(&q);
v=0;
visited[v]=1;
addq(&q,v);
while(!isempty(&q))
{
v=removeq(&q);
printf("v%d",v+1);
for(w=0; w<n; w++)
{
if((m[v][w]==1)&&(visited[w]==0))
{
addq(&q, w);
visited[w]=1;
}
}
}
}
int main()
{
int m[10][10], n, i, j, w;
printf("\nHow many vertices:");
scanf("%d", &n);
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
if(i!=j)
{
printf("Is there edge between vertex %d and %d
(1/0):", i+1, j+1);
scanf("%d", &m[i][j]);
}
}
printf("\nNon recursive breadth first search is :");
bfs(m,n);
}
Dijikatras algorithm
ReplyDelete#include
#define MAX 20
void djks(int c[10][10], int n)
{
int i, j, v, w, u, count, min;
int dist[10];
int visited[10]={0};
printf("\nEnter the source vertex:");
scanf("%d", &v);
v=v-1;
for(i=0; i%d :", i+1, j+1);
scanf("%d", &c[i][j]);
c[j][i]= c[i][j];
}
}
djks(c,n);
}
Best inorder
ReplyDelete#include
#include
#define NEWNODE (struct node *)malloc(sizeof(struct node))
struct node
{
struct node *left;
int data;
struct node *right;
};
struct node *root;
void init()
{
root=NULL;
}
void insert(int item)
{ struct node *t1,*t2,*t;
t=NEWNODE;
t->data=item;
t->left=NULL;
t->right=NULL;
if(root==NULL)
{
root=t;
}
else
{
t1=root;
while(t1!=NULL)
{
t2=t1;
if(item<=t1->data)
t1=t1->left;
else
t1=t1->right;
}
if(item<=t2->data)
t2->left=t;
else
t2->right=t;
}
}
void inorder(struct node *t)
{
if(t!=NULL)
{
inorder(t->left);
printf(" %d ",t->data);
inorder(t->right);
}
}
int main()
{
int n,i,item;
printf("\n How many item u want to store =");
scanf("%d",&n);
init();
for(i=1;i<=n;i++)
{
printf("\n Enter data = ");
scanf("%d",&item);
insert(item);
}
printf("\n Displaying tree INORDER WISE = ");
inorder(root);
return 0;
}
Best preorder
ReplyDelete#include
#include
#define NEWNODE (struct node *)malloc(sizeof(struct node))
struct node
{
struct node *left;
int data;
struct node *right;
};
struct node *root;
void init()
{
root=NULL;
}
void insert(int item)
{ struct node *t1,*t2,*t;
t=NEWNODE;
t->data=item;
t->left=NULL;
t->right=NULL;
if(root==NULL)
{
root=t;
}
else
{
t1=root;
while(t1!=NULL)
{
t2=t1;
if(item<=t1->data)
t1=t1->left;
else
t1=t1->right;
}
if(item<=t2->data)
t2->left=t;
else
t2->right=t;
}
}
void preorder(struct node *t)
{
if(t!=NULL)
{
printf(" %d ",t->data);
preorder(t->left);
preorder(t->right);
}
}
int main()
{
int n,i,item;
printf("\nHow many item u want to store =");
scanf("%d",&n);
init();
for(i=1;i<=n;i++)
{
printf("\nEnter data = ");
scanf("%d",&item);
insert(item);
}
printf("\nDisplaying tree PREORDER WISE = ");
preorder(root);
return 0;
}
Topological sort
ReplyDelete#include
int main()
{
int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;
printf("enter the number of vertices:\n");
scanf("%d",&n);
printf("enter the adjancency matrix:\n");
for(i=0; i<n; i++)
{
printf("enter row %d\n",i+1);
for(j=0;j<n; j++)
scanf("%d",&a[i][j]);
}
for(i=0;i<n;i++)
{
indeg[i]=0;
flag[i]=0;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
indeg[i]=indeg[i]+a[j][i];
printf("\n the topological order is");
while(count<n)
{
for(k=0;k<n;k++)
{
if((indeg[k]==0) && (flag[k]==0))
{
printf("%d",(k+1));
flag[k]=1;
break;
}
}
for(i=0;i<n;i++)
{
if(a[k][i]==1)
indeg[i]--;
}
count ++;
}
return 0;
}
Even numbers from bst
ReplyDelete#include
#include
struct node
{
int info;
struct node *left;
struct node *right;
};
struct node *createnode(int key)
{
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode->info = key;
newnode->left = NULL;
newnode->right = NULL;
return(newnode);
}
int sumeven(struct node *root)
{
int rightsubtree, leftsubtree, sum = 0;
if(root != NULL)
{
leftsubtree = sumeven(root->left);
rightsubtree = sumeven(root->right);
sum = (root->info) + leftsubtree + rightsubtree;
return sum;
}
}
int main()
{
// first bst
struct node *newnode = createnode(22);
newnode->left = createnode(28);
newnode->right = createnode(18);
newnode->left->left = createnode(10);
newnode->left->right = createnode(90);
newnode->right->left = createnode(12);
newnode->right->right = createnode(56);
printf("Returning sum of all even numbers from BST 1 = %d", sumeven(newnode));
printf("\n");
// creating 2nd bst//
struct node *node = createnode(14);
node->right = createnode(2);
node->right->right = createnode(2);
node->right->right->right = createnode(4);
node->right->right->right->right = createnode(6);
printf("Returning sum of all even numbers from BST 2 = %d", sumeven(node));
printf("\n");
// third bst
struct node *root = createnode(16);
printf("Returning sum of all even numbers from BST 3 = %d", sumeven(root));
printf("\n");
return 0;
}
Sure, here's a breakdown of each question:
ReplyDelete1. **What is a tree?**
- A tree is a hierarchical data structure composed of nodes connected by edges. It consists of a collection of nodes, where each node has a value and a list of references to its child nodes (if any), with one designated as the "root" node.
2. **What is a graph?**
- A graph is a collection of nodes (vertices) and edges that connect pairs of nodes. Graphs can be directed (edges have a specific direction) or undirected (edges do not have a direction).
3. **What is hash?**
- Hashing is the process of mapping data of arbitrary size to fixed-size values. A hash function is used to generate the hash value, which is typically a unique identifier representing the original data. Hashing is commonly used in data structures like hash tables for fast data retrieval.
4. **What is a binary tree?**
- A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
5. **What is an AVL tree?**
- An AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of any node is at most one. It ensures that the tree remains balanced, which helps maintain efficient search, insertion, and deletion operations.
6. **Types of AVL rotations?**
- There are four types of rotations in AVL trees:
- Left Rotation
- Right Rotation
- Left-Right Rotation (also known as Double Right Rotation)
- Right-Left Rotation (also known as Double Left Rotation)
7. **Rules for red-black tree?**
- Red-black trees are self-balancing binary search trees with the following rules:
1. Every node is either red or black.
2. The root is always black.
3. Red nodes cannot have red children.
4. Every path from a node to its descendant NIL nodes (leaf nodes) must have the same number of black nodes.
8. **What is a terminal node?**
- A terminal node, also known as a leaf node, is a node in a tree data structure that does not have any children.
9. **What is a root node?**
- The root node is the topmost node in a tree hierarchy. It is the starting point for traversing the tree and is the only node that does not have a parent.
10. **Type of binary tree?**
- There are various types of binary trees, including:
- Full binary tree
- Complete binary tree
- Perfect binary tree
- Balanced binary tree
11. **BFS and DFS rules?**
- Breadth-First Search (BFS) visits nodes level by level starting from the root. It uses a queue data structure for traversal.
- Depth-First Search (DFS) explores as far as possible along each branch before backtracking. It can be implemented using either a stack (for iterative DFS) or recursion.
12. **Preorder, Inorder, Postorder?**
- These are different methods for traversing a binary tree:
- Preorder: Visit the root node first, then recursively traverse the left subtree, followed by the right subtree.
- Inorder: Recursively traverse the left subtree, visit the root node, then recursively traverse the right subtree.
- Postorder: Recursively traverse the left subtree, then the right subtree, and finally visit the root node.