Assignment 2: Binary Search Tree Operations and Applications
Set A
a) Write a C program which uses Binary search tree library and display the following
i. Node value at each level
ii. Count of node at each level
iii. Total levels in the tree.
//Create a Binary Search Tree & Display Nodes level wise
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
struct Btree
{
struct Btree *lchild;
int data;
struct Btree *rchild;
};
typedef struct Btree BNODE;
struct Queue
{
struct Btree *Q[MAX];
int front,rear;
};
typedef struct Queue QUEUE;
void Addq(QUEUE *q,BNODE *t)
{
q->Q[++q->rear]=t;
}
BNODE * Delq(QUEUE *q)
{
return(q->Q[++q->front]);
}
int isempty(QUEUE *q)
{
if(q->front==q->rear)
return 1;
else
return 0;
}
void LevelDisp(BNODE *h)
{
QUEUE q;
BNODE *temp;
int total=0,cnt=0,level=0;
q.front=q.rear=-1;
temp=h;
Addq(&q,temp);
Addq(&q,NULL);
while(!isempty(&q))
{
temp=Delq(&q);
if(temp==NULL)
{
if(!isempty(&q))
{
printf(" = %d Level-%d\n",cnt,level);
cnt=0;
level++;
Addq(&q,NULL);
}
}
else
{
total++;
cnt++;
printf("%d ",temp->data);
if(temp->lchild!=NULL)
Addq(&q,temp->lchild);
if(temp->rchild!=NULL)
Addq(&q,temp->rchild);
}
}
printf("=%d Level-%d\n",cnt,level);
printf("\nTotal Nodes:%d",total);
printf("\nTotal Levels:%d\n",level+1);
}
BNODE* newNode(int data)
{
BNODE* node = (BNODE*)malloc(sizeof(BNODE));
node->data = data;
node->lchild = NULL;
node->rchild = NULL;
return(node);
}
void main()
{
BNODE *header = newNode(100);
header->lchild = newNode(50);
header->rchild = newNode(200);
header->rchild->lchild=newNode(150);
header->lchild->lchild = newNode(20);
header->lchild->rchild = newNode(80);
header->lchild->rchild->lchild = newNode(70);
LevelDisp(header);
}
b) Write a C program to find the minimum and maximum values in a Binary Search Tree
#include <stdio.h>
#include <stdlib.h>
// Structure for BST Node
struct Node {
int data;
struct Node *left, *right;
};
// Helper function to create a new node
struct Node* newNode(int data) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Helper function to insert nodes for testing
struct Node* insert(struct Node* node, int data) {
if (node == NULL) return newNode(data);
if (data < node->data) node->left = insert(node->left, data);
else if (data > node->data) node->right = insert(node->right, data);
return node;
}
// Function to find MINIMUM value (Iterative)
int findMin(struct Node* root) {
if (root == NULL) return -1; // Handle empty tree
struct Node* current = root;
while (current->left != NULL) {
current = current->left; // Traverse to the leftmost node
}
return current->data;
}
// Function to find MAXIMUM value (Recursive)
int findMax(struct Node* root) {
if (root == NULL) return -1;
if (root->right == NULL) return root->data; // Base case: rightmost node found
return findMax(root->right); // Recurse to the right
}
int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
if (root != NULL) {
printf("Minimum value in BST: %d\n", findMin(root));
printf("Maximum value in BST: %d\n", findMax(root));
} else {
printf("Tree is empty.\n");
}
return 0;
}
Set B
a) Write a program to sort n randomly generated elements using Heapsort method.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to swap elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Heapify function to maintain max heap property
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// Check if left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not the root
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest); // Recursively heapify the affected subtree
}
}
// Function to perform Heap Sort
void heapSort(int arr[], int n) {
// Step 1: Build Max Heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Step 2: Extract elements one by one
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]); // Move current root to end
heapify(arr, i, 0); // Heapify the reduced heap
}
}
// Function to print array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function
int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
// Random number generation
srand(time(0));
printf("Randomly generated array: ");
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100; // Generates numbers between 0-99
printf("%d ", arr[i]);
}
printf("\n");
// Sorting the array using Heap Sort
heapSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
b) Write a C program to maintain a phonebook using Binary Search Tree by name where each node contain contact name and phone number.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Structure for a Phonebook Node
typedef struct ContactNode {
char name[50];
char phone[15];
struct ContactNode *left, *right;
} Contact;
// Function to create a new contact
Contact* createContact(char* name, char* phone) {
Contact* newNode = (Contact*)malloc(sizeof(Contact));
strcpy(newNode->name, name);
strcpy(newNode->phone, phone);
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert contact into BST (ordered by name)
Contact* insert(Contact* root, char* name, char* phone) {
if (root == NULL) return createContact(name, phone);
// Alphabetical comparison using strcmp
if (strcmp(name, root->name) < 0)
root->left = insert(root->left, name, phone);
else if (strcmp(name, root->name) > 0)
root->right = insert(root->right, name, phone);
else
printf("\nContact with name '%s' already exists!", name);
return root;
}
// Search for a contact by name
Contact* search(Contact* root, char* name) {
if (root == NULL || strcmp(root->name, name) == 0)
return root;
if (strcmp(name, root->name) < 0)
return search(root->left, name);
return search(root->right, name);
}
// Display phonebook in alphabetical order (Inorder Traversal)
void display(Contact* root) {
if (root != NULL) {
display(root->left);
printf("Name: %-20s | Phone: %s\n", root->name, root->phone);
display(root->right);
}
}
int main() {
Contact* phonebook = NULL;
int choice;
char name[50], phone[15];
while (1) {
printf("\n--- Phonebook BST ---\n1. Add Contact\n2. Search\n3. Display All\n4. Exit\nChoice: ");
scanf("%d", &choice);
getchar(); // Clear newline
switch (choice) {
case 1:
printf("Enter Name: "); gets(name);
printf("Enter Phone: "); gets(phone);
phonebook = insert(phonebook, name, phone);
break;
case 2:
printf("Enter Name to Search: "); gets(name);
Contact* res = search(phonebook, name);
if (res) printf("Found: %s -> %s\n", res->name, res->phone);
else printf("Contact not found.\n");
break;
case 3:
printf("\n--- Contact List (Alphabetical) ---\n");
display(phonebook);
break;
case 4:
exit(0);
}
}
return 0;
}
c) Write a C program to find the height of the tree and check whether given tree is balanced or not.
#include <stdio.h>
#include <stdlib.h>
// Structure for a Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
// Utility function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// Function to calculate height and check balance simultaneously
// Returns height if balanced, otherwise returns -1
int checkBalance(struct Node* root) {
if (root == NULL) return 0;
// Check left subtree
int leftHeight = checkBalance(root->left);
if (leftHeight == -1) return -1; // Left is already unbalanced
// Check right subtree
int rightHeight = checkBalance(root->right);
if (rightHeight == -1) return -1; // Right is already unbalanced
// Check current node balance: absolute difference must be <= 1
int diff = abs(leftHeight - rightHeight);
if (diff > 1) return -1;
// Return actual height of this node
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// Helper function to get tree height independently
int getHeight(struct Node* root) {
if (root == NULL) return 0;
int lh = getHeight(root->left);
int rh = getHeight(root->right);
return (lh > rh ? lh : rh) + 1;
}
int main() {
// Creating a sample balanced tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Height of the tree: %d\n", getHeight(root));
int result = checkBalance(root);
if (result != -1)
printf("The tree is balanced.\n");
else
printf("The tree is NOT balanced.\n");
return 0;
}
No comments:
Post a Comment