Data Structure Assignment No.

Q1. SOLUTION:

CODE:

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>
#include <bitset>

using namespace std;

// Node structure for Huffman Tree

struct Node {
char data;
int freq;
Node* left;
Node* right;

Node(char c, int f) : data(c), freq(f), left(nullptr), right(nullptr) {}

};

// Compare function for priority queue to build Huffman tree

struct compare {
bool operator()(Node* left, Node* right) {
return left->freq > right->freq;
}
};

// Function to build the Huffman Tree

Node* buildHuffmanTree(const unordered_map<char, int>& freq) {
priority_queue<Node*, vector<Node*>, compare> minHeap;
 for (auto& entry : freq) {
minHeap.push(new Node(entry.first, entry.second));
}

while (minHeap.size() > 1) {

Node* left = minHeap.top();
minHeap.pop();
Node* right = minHeap.top();
minHeap.pop();

Node* internalNode = new Node('$', left->freq + right->freq);

internalNode->left = left;
internalNode->right = right;
minHeap.push(internalNode);
}

return minHeap.top();
}

// Helper function to generate Huffman codes for each character

void generateCodes(Node* root, const string& str,
unordered_map<char, string>& huffmanCodes) {
if (!root) {
return;
}

if (root->data != '$') { // '$' is an internal node, so we ignore it.

huffmanCodes[root->data] = str;
}

generateCodes(root->left, str + "0", huffmanCodes);

generateCodes(root->right, str + "1", huffmanCodes);
}

// Function to calculate the efficiency of Huffman encoding

double calculateEfficiency(int totalOriginalBits, int totalCompressedBits)
{
return ((double)(totalOriginalBits - totalCompressedBits) /
totalOriginalBits) * 100;
}

// Function to count the frequency of characters in the message

unordered_map<char, int> countFrequency(const string& message) {
unordered_map<char, int> freq;
for (char c : message) {
if (c != '"' && c != '\n') { // Remove double quotes and newline
characters
freq[c]++;
}
}
return freq;
}

int main() {

string message = "Department of Electrical and Computer Engineering,

International Islamic University, Islamanbad";

unordered_map<char, int> freq = countFrequency(message);

// Build Huffman Tree

Node* root = buildHuffmanTree(freq);

// Generate Huffman codes

unordered_map<char, string> huffmanCodes;
generateCodes(root, "", huffmanCodes);

// Create the table with Letter, Frequency, Original Bits, and Encoded
Bits
int totalOriginalBits = 0;
int totalCompressedBits = 0;
cout << "Letter | Frequency | Original Bits | Encoded Bits" << endl;
for (auto& entry : freq) {
char letter = entry.first;
int frequency = entry.second;
int originalBits = 8; // ASCII uses 8 bits for each character
string encodedBits = huffmanCodes[letter];
int encodedBitsLength = encodedBits.length();

totalOriginalBits += frequency * originalBits;

 totalCompressedBits += frequency * encodedBitsLength;

cout << letter << " | " << frequency << " | " << originalBits <<
" | " << encodedBitsLength << endl;
}

// Calculate the efficiency of Huffman encoding

double efficiency = calculateEfficiency(totalOriginalBits,
totalCompressedBits);
cout << "\nTotal Original Bits: " << totalOriginalBits << endl;
cout << "Total Compressed Bits: " << totalCompressedBits << endl;
cout << "Efficiency of Huffman Encoding: " << efficiency << "%" <<
endl;

// Clean up the memory by deleting the Huffman tree

delete root;

return 0;
}
Output:
Q2:You are required to construct AVL tree from the following

data:

15 ,18 ,12,8, 54, 50,14,13, 9, 61, 20,17, 20

a. You need to insert these data items one by one starting

from the data item 15 in the same order in

which they have written above.

b. Show and perform necessary rotations where needed.

c. In Solution show only the final AVL tree and only those

steps in which rotation is applied.

Code:

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
int data;
Node* left;
Node* right;
int height;

Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}

};

// Utility function to get the height of a node

int getHeight(Node* node) {
 return node ? node->height : 0;
}

// Utility function to get the balance factor of a node

int getBalanceFactor(Node* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// Right rotation
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

// Return the new root

return x;
}

// Left rotation
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

// Return the new root

return y;
}

// Left-Right rotation
Node* leftRightRotate(Node* node) {
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right-Left rotation
Node* rightLeftRotate(Node* node) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

// Function to insert a node

Node* insert(Node* node, int key) {
// Perform the normal BST insert
if (node == nullptr) {
return new Node(key);
}

if (key < node->data) {

node->left = insert(node->left, key);
} else if (key > node->data) {
node->right = insert(node->right, key);
} else {
return node; // Duplicates are not allowed
}

// Update the height of the current node

node->height = max(getHeight(node->left), getHeight(node->right)) +
1;

// Get the balance factor

int balance = getBalanceFactor(node);

// Perform rotations if the node is unbalanced

if (balance > 1 && key < node->left->data) {
return rightRotate(node); // Left-Left case
}
 if (balance < -1 && key > node->right->data) {
return leftRotate(node); // Right-Right case
}

if (balance > 1 && key > node->left->data) {

return leftRightRotate(node); // Left-Right case
}

if (balance < -1 && key < node->right->data) {

return rightLeftRotate(node); // Right-Left case
}

return node;
}

// Utility function to do inorder traversal of the tree

void inorder(Node* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}

// Function to delete the AVL tree

void deleteTree(Node* node) {
if (node == nullptr) return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}

int main() {
Node* root = nullptr;

int values[] = {15, 18, 12, 8, 54, 50, 14, 13, 9, 61, 20, 17, 20};
int n = sizeof(values) / sizeof(values[0]);

// Insert the values one by one and print the AVL tree after each
insertion
 for (int i = 0; i < n; i++) {
root = insert(root, values[i]);
cout << "After inserting " << values[i] << ": ";
inorder(root);
cout << endl;
}

deleteTree(root); // Free memory

return 0;
}

Output:
Q3:You are required to construct a minimum heap from the

following data:

44, 31, 11, 5, 7, 90, 4, 6

a. You need to insert these data items one by one starting

from the data item 15 in the same order in

which they have written above.

b. Show and perform necessary swap operations where

needed.

c. In Solution show only the final minimum heap tree and only

those steps in which swap is applied.

CODE:

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

using namespace std;

// Function to heapify the tree at a given index

void heapifyUp(vector<int>& heap, int index) {
int parent = (index - 1) / 2;

// Check if the heap property is violated

if (index > 0 && heap[parent] > heap[index]) {
// Swap parent and child
 swap(heap[parent], heap[index]);
// Recursively heapify the parent
heapifyUp(heap, parent);
}
}

// Function to insert an element into the heap

void insert(vector<int>& heap, int value) {
// Insert the new element at the end of the heap
heap.push_back(value);

// Heapify up to restore the heap property

heapifyUp(heap, heap.size() - 1);
}

// Function to print the heap

void printHeap(const vector<int>& heap) {
for (int val : heap) {
cout << val << " ";
}
cout << endl;
}

int main() {
vector<int> heap;

// Array of elements to insert

int data[] = {44, 31, 11, 5, 7, 90, 4, 6};
int n = sizeof(data) / sizeof(data[0]);

// Insert elements one by one and maintain the Min-Heap property

for (int i = 0; i < n; i++) {
insert(heap, data[i]);
cout << "After inserting " << data[i] << ": ";
printHeap(heap);
}

return 0;
}
OUTPUT:

Q4: Perform BFS starting at node A. Show the results of the

queue and graph at every step.

Code:

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <set>
using namespace std;

// Function to perform BFS

void bfs(unordered_map<char, vector<char>> &graph, char start) {
queue<char> q; // Queue for BFS
set<char> visited; // Set to keep track of visited nodes

q.push(start); // Start from the initial node

visited.insert(start); // Mark it as visited

cout << "BFS Traversal: ";

while (!q.empty()) {
char current = q.front(); // Get the front of the queue
 q.pop(); // Remove it from the queue

cout << current << " "; // Print the current node

// Traverse all neighbors of the current node

for (char neighbor : graph[current]) {
if (visited.find(neighbor) == visited.end()) { // If neighbor is not
visited
q.push(neighbor); // Add to the queue
visited.insert(neighbor); // Mark as visited
}
}
}
cout << endl;
}

int main() {
// Define the graph as an adjacency list
unordered_map<char, vector<char>> graph = {
{'A', {'B', 'C', 'D'}},
{'B', {'A', 'C', 'F'}},
{'C', {'A', 'B', 'F'}},
{'D', {'A', 'G'}},
{'E', {'F', 'H'}},
{'F', {'B', 'C', 'E', 'G', 'I'}},
{'G', {'D', 'F'}},
{'H', {'E', 'I', 'J'}},
{'I', {'F', 'H', 'J'}},
{'J', {'H', 'I'}}
};

// Perform BFS starting from node A

bfs(graph, 'A');

return 0;
}
OUTPUT:

Q5: Perform DFS starting at node F. Show the result of graph

at every step

Code:

#include <iostream>
#include <unordered_map>
#include <vector>
#include <set>
#include <stack>
using namespace std;

// Function to perform DFS

void dfs(unordered_map<char, vector<char>> &graph, char start) {
stack<char> s; // Stack for DFS
set<char> visited; // Set to keep track of visited nodes

s.push(start); // Start from the initial node

cout << "Step-by-Step DFS Traversal:\n";

while (!s.empty()) {
char current = s.top(); // Get the top of the stack
s.pop(); // Remove it from the stack

// If the current node is not visited

if (visited.find(current) == visited.end()) {
visited.insert(current); // Mark it as visited
cout << "Visited: " << current << "\n";
 cout << "Stack: ";
stack<char> temp = s; // Print the current stack
while (!temp.empty()) {
cout << temp.top() << " ";
temp.pop();
}
cout << "\n";

// Add neighbors in reverse order to maintain correct order in DFS

for (auto it = graph[current].rbegin(); it != graph[current].rend(); +
+it) {
if (visited.find(*it) == visited.end()) {
s.push(*it);
}
}

cout << "Stack after pushing neighbors of " << current << ": ";
temp = s;
while (!temp.empty()) {
cout << temp.top() << " ";
temp.pop();
}
cout << "\n\n";
}
}
}

int main() {
// Define the graph as an adjacency list
unordered_map<char, vector<char>> graph = {
{'A', {'B', 'C', 'D'}},
{'B', {'A', 'C', 'F'}},
{'C', {'A', 'B', 'F'}},
{'D', {'A', 'G'}},
{'E', {'F', 'H'}},
{'F', {'B', 'C', 'E', 'G', 'I'}},
{'G', {'D', 'F'}},
{'H', {'E', 'I', 'J'}},
{'I', {'F', 'H', 'J'}},
{'J', {'H', 'I'}}
 };

// Perform DFS starting from node F

dfs(graph, 'F');

return 0;
}
Output: