Scribd
Upload
3 views11 pages

Heap Sort and Tree Traversals in C

The document contains code implementations for various algorithms and data structures in C, including Heap Sort, Inorder and Preorder Traversals (both recursive and non-recursive), Hashing with Linear Probing and Chaining, Min-Max Problem using Divide and Conquer, Binary Search, Postorder Traversal, and Merge Sort. Each section provides a brief description of the algorithm followed by its implementation. The main function in each code snippet demonstrates how to execute the respective algorithms.

Uploaded by

becauseweneverknoww
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
3 views11 pages

Heap Sort and Tree Traversals in C

The document contains code implementations for various algorithms and data structures in C, including Heap Sort, Inorder and Preorder Traversals (both recursive and non-recursive), Hashing with Linear Probing and Chaining, Min-Max Problem using Divide and Conquer, Binary Search, Postorder Traversal, and Merge Sort. Each section provides a brief description of the algorithm followed by its implementation. The main function in each code snippet demonstrates how to execute the respective algorithms.

Uploaded by

becauseweneverknoww
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

1.1.

Heap Sort
---------------
#include <stdio.h>

void heapify(int arr[], int n, int i) {


int largest = i, l = 2*i + 1, 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) {
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
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--) {
int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
heapify(arr, i, 0);
}
}

int main() {
int arr[] = {4, 10, 3, 5, 1}, n = 5;
heapSort(arr, n);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}

1.2 Inorder Traversal (Recursive)


---------------------------------
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *left, *right;
};

struct Node* newNode(int data) {


struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data; node->left = node->right = NULL;
return node;
}

void inorder(struct Node* root) {


if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

int main() {
struct Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
inorder(root);
return 0;
}

2.1. Hashing using Linear Probing


----------------------------------
#include <stdio.h>
#define SIZE 10

int hashTable[SIZE];

void initHashTable() {
for (int i = 0; i < SIZE; i++)
hashTable[i] = -1; // -1 indicates empty
}

int hash(int key) {


return key % SIZE;
}

void insert(int key) {


int index = hash(key);
int i = 0;

while (hashTable[(index + i) % SIZE] != -1 && i < SIZE) {


i++;
}

if (i < SIZE) {
hashTable[(index + i) % SIZE] = key;
} else {
printf("Hash table is full\n");
}
}

void display() {
printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++)
printf("Index %d: %d\n", i, hashTable[i]);
}

int main() {
initHashTable();
int keys[] = {23, 43, 13, 27, 34};
int n = sizeof(keys) / sizeof(keys[0]);

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


insert(keys[i]);
}

display();
return 0;
}
2.2 Preorder Traversal (Recursive)
-----------------------------------

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};

struct Node* createNode(int value) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

void preorderTraversal(struct Node* root) {


if (root == NULL)
return;

printf("%d ", root->data); // Visit the root


preorderTraversal(root->left); // Traverse left subtree
preorderTraversal(root->right); // Traverse right subtree
}

int main() {
struct Node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);

printf("Preorder Traversal: ");


preorderTraversal(root);
return 0;
}

3.1. Min-Max Problem using Divide and Conquer


-----------------------------------------------
#include <stdio.h>

struct Result {
int min;
int max;
};

struct Result findMinMax(int arr[], int low, int high) {


struct Result result, leftResult, rightResult;

// If only one element


if (low == high) {
[Link] = [Link] = arr[low];
return result;
}

// If two elements
if (high == low + 1) {
if (arr[low] < arr[high]) {
[Link] = arr[low];
[Link] = arr[high];
} else {
[Link] = arr[high];
[Link] = arr[low];
}
return result;
}

// More than two elements


int mid = (low + high) / 2;
leftResult = findMinMax(arr, low, mid);
rightResult = findMinMax(arr, mid + 1, high);

// Combine results
[Link] = ([Link] < [Link]) ? [Link] :
[Link];
[Link] = ([Link] > [Link]) ? [Link] :
[Link];

return result;
}

int main() {
int arr[] = {100, 11, 445, 1, 330, 3000};
int n = sizeof(arr) / sizeof(arr[0]);

struct Result res = findMinMax(arr, 0, n - 1);


printf("Minimum: %d\n", [Link]);
printf("Maximum: %d\n", [Link]);
return 0;
}
3.2. Preorder Traversal (Non-Recursive)
------------------------------------------

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

#define STACK_SIZE 100

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

// Stack for tree nodes


struct Node* stack[STACK_SIZE];
int top = -1;

void push(struct Node* node) {


if (top < STACK_SIZE - 1)
stack[++top] = node;
}

struct Node* pop() {


if (top >= 0)
return stack[top--];
return NULL;
}
int isEmpty() {
return top == -1;
}

struct Node* createNode(int value) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

void preorderNonRecursive(struct Node* root) {


if (root == NULL)
return;

push(root);
while (!isEmpty()) {
struct Node* current = pop();
printf("%d ", current->data);

if (current->right)
push(current->right);
if (current->left)
push(current->left);
}
}

int main() {
struct Node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);

printf("Preorder Traversal (Non-Recursive): ");


preorderNonRecursive(root);
return 0;
}

4.1. Hashing with Chaining


--------------------------
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

// Node structure for chaining


struct Node {
int data;
struct Node* next;
};

// Hash table
struct Node* hashTable[SIZE];

// Hash function
int hash(int key) {
return key % SIZE;
}
// Insert into hash table with chaining
void insert(int key) {
int index = hash(key);
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = key;
newNode->next = NULL;

if (hashTable[index] == NULL) {
hashTable[index] = newNode;
} else {
// Insert at the beginning for simplicity
newNode->next = hashTable[index];
hashTable[index] = newNode;
}
}

// Display hash table


void display() {
printf("Hash Table with Chaining:\n");
for (int i = 0; i < SIZE; i++) {
printf("Index %d: ", i);
struct Node* temp = hashTable[i];
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
}

int main() {
// Initialize table
for (int i = 0; i < SIZE; i++)
hashTable[i] = NULL;

// Example keys
int keys[] = {15, 25, 35, 20, 30, 10, 40};
int n = sizeof(keys) / sizeof(keys[0]);

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


insert(keys[i]);

display();
return 0;
}
4.2. Preorder Traversal (Recursive Procedure)
----------------------------------------------
#include <stdio.h>
#include <stdlib.h>

// Tree node structure


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

// Create new node


struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

// Recursive Preorder Traversal


void preorderTraversal(struct Node* root) {
if (root == NULL)
return;

printf("%d ", root->data); // Visit root


preorderTraversal(root->left); // Traverse left
preorderTraversal(root->right); // Traverse right
}

int main() {
struct Node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);

printf("Preorder Traversal (Recursive): ");


preorderTraversal(root);
return 0;
}

5.1. Binary Search using Divide and Conquer


-----------------------------------------------
#include <stdio.h>

// Binary Search using Divide and Conquer


int binarySearch(int arr[], int low, int high, int key) {
if (low > high)
return -1;

int mid = (low + high) / 2;

if (arr[mid] == key)
return mid;
else if (key < arr[mid])
return binarySearch(arr, low, mid - 1, key);
else
return binarySearch(arr, mid + 1, high, key);
}

int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 50;

int index = binarySearch(arr, 0, n - 1, key);

if (index != -1)
printf("Element %d found at index %d\n", key, index);
else
printf("Element %d not found\n", key);
return 0;
}
5.2. Postorder Traversal (Non-Recursive Procedure)
----------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

#define STACK_SIZE 100

// Binary Tree Node


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

// Stack structure for Nodes


struct Node* stack1[STACK_SIZE];
struct Node* stack2[STACK_SIZE];
int top1 = -1, top2 = -1;

void push1(struct Node* node) {


stack1[++top1] = node;
}

void push2(struct Node* node) {


stack2[++top2] = node;
}

struct Node* pop1() {


return stack1[top1--];
}

struct Node* pop2() {


return stack2[top2--];
}

int isEmpty1() {
return top1 == -1;
}

// Create a new tree node


struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

// Postorder Traversal (Non-Recursive using 2 stacks)


void postorderNonRecursive(struct Node* root) {
if (root == NULL)
return;

push1(root);

while (!isEmpty1()) {
struct Node* curr = pop1();
push2(curr);

if (curr->left)
push1(curr->left);
if (curr->right)
push1(curr->right);
}

while (top2 != -1) {


struct Node* node = pop2();
printf("%d ", node->data);
}
}

int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Postorder Traversal (Non-Recursive): ");


postorderNonRecursive(root);
return 0;
}

[Link] Sort using Divide and Conquer


----------------------------------------
#include <stdio.h>

// Merge two sorted halves


void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

int L[n1], R[n2]; // Temporary arrays

for (i = 0; i < n1; i++)


L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

i = j = 0;
k = left;

// Merge the arrays


while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];

while (i < n1)


arr[k++] = L[i++];

while (j < n2)


arr[k++] = R[j++];
}

// Recursive Merge Sort


void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;

mergeSort(arr, left, mid); // Left half


mergeSort(arr, mid + 1, right); // Right half

merge(arr, left, mid, right); // Merge them


}
}

int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, n - 1);

printf("Sorted array using Merge Sort:\n");


for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
6.2. Inorder Traversal (Non-Recursive)
--------------------------------------
#include <stdio.h>
#include <stdlib.h>

#define STACK_SIZE 100

// Tree node structure


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

// Stack for nodes


struct Node* stack[STACK_SIZE];
int top = -1;

void push(struct Node* node) {


if (top < STACK_SIZE - 1)
stack[++top] = node;
}

struct Node* pop() {


if (top >= 0)
return stack[top--];
return NULL;
}

int isEmpty() {
return top == -1;
}

// Create new node


struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

// Inorder traversal without recursion


void inorderNonRecursive(struct Node* root) {
struct Node* current = root;

while (current != NULL || !isEmpty()) {


while (current != NULL) {
push(current);
current = current->left;
}

current = pop();
printf("%d ", current->data);
current = current->right;
}
}

int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Inorder Traversal (Non-Recursive): ");


inorderNonRecursive(root);
return 0;
}

You might also like