Scribd
Upload
2 views3 pages

Binary Tree and BFS Implementation

The document contains two C programs: one for implementing a binary search tree (BST) with functions to create nodes, insert values, and perform postorder traversal, and another for performing a breadth-first search (BFS) on a graph represented as an adjacency matrix. The BST program includes a menu for user interaction to insert values and display the postorder traversal, while the BFS program allows the user to input the number of vertices and edges, and then perform BFS from a specified starting vertex. Both programs utilize standard input/output and dynamic memory allocation.

Uploaded by

kgxsumitsalunke
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
2 views3 pages

Binary Tree and BFS Implementation

The document contains two C programs: one for implementing a binary search tree (BST) with functions to create nodes, insert values, and perform postorder traversal, and another for performing a breadth-first search (BFS) on a graph represented as an adjacency matrix. The BST program includes a menu for user interaction to insert values and display the postorder traversal, while the BFS program allows the user to input the number of vertices and edges, and then perform BFS from a specified starting vertex. Both programs utilize standard input/output and dynamic memory allocation.

Uploaded by

kgxsumitsalunke
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

Q1

// btree.h

#ifndef BTREE_H
#define BTREE_H

typedef struct Node {


int data;
struct Node* left;
struct Node* right;
} Node;
Node* createNode(int data);
Node* insert(Node* root, int data);
void postorder(Node* root);

#endif

// btree.c

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

Node* createNode(int data) {


Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

Node* insert(Node* root, int data) {


if (root == NULL) {
return createNode(data);
}

if (data < root->data)


root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
else
printf("Duplicate value %d not inserted.\n", data);

return root;
}
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}

// main.c
#include <stdio.h>
#include <stdlib.h>
#include "btree.h"

int main() {
Node* root = NULL;
int choice, value;

while (1) {
printf("\n--- Binary Search Tree Menu ---\n");
printf("1. Insert\n");
printf("2. Postorder Traversal\n");
printf("3. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
root = insert(root, value);
break;

case 2:
printf("Postorder Traversal: ");
postorder(root);
printf("\n");
break;

case 3:
printf("Exiting program.\n");
exit(0);

default:
printf("Invalid choice! Try again.\n");
}
}

return 0;
}

Q2

#include <stdio.h>

#define MAX 100

int graph[MAX][MAX];
int visited[MAX];
int queue[MAX];
int front = -1, rear = -1;
int n;

void enqueue(int v) {
if (rear == MAX - 1)
return;
if (front == -1) front = 0;
queue[++rear] = v;
}
int dequeue() {
if (front == -1 || front > rear)
return -1;
return queue[front++];
}
void BFS(int start) {
int i;
enqueue(start);
visited[start] = 1;

while (front <= rear) {


int vertex = dequeue();
printf("%d ", vertex);

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


if (graph[vertex][i] == 1 && !visited[i]) {
enqueue(i);
visited[i] = 1;
}
}
}
}

int main() {
int edges, src, dest, i, j, start;

printf("Enter number of vertices: ");


scanf("%d", &n);
for (i = 0; i < n; i++) {
visited[i] = 0;
for (j = 0; j < n; j++) {
graph[i][j] = 0;
}
}

printf("Enter number of edges: ");


scanf("%d", &edges);

printf("Enter edges (source destination) using 0-based indexing:\n");


for (i = 0; i < edges; i++) {
scanf("%d %d", &src, &dest);
graph[src][dest] = 1;
}

printf("Enter starting vertex for BFS: ");


scanf("%d", &start);

printf("BFS Traversal starting from vertex %d: ", start);


BFS(start);
printf("\n");

return 0;
}

You might also like