#11. Program for Binary Tree Travarsal BinTreeTrav.

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

struct node {
int item;
struct node* left;
struct node* right;
};

struct node* initTree(int data) {

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

void freeTree(struct node* root) {

struct node* temp = root;
if (!temp)
return;
freeTree(temp->left);
freeTree(temp->right);
if (!temp->left && !temp->right) {
free(temp);
return;
}
}

// Inorder traversal
void inorderTraversal(struct node* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ->", root->item);
inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root) {
if (root == NULL) return;
printf("%d ->", root->item);
preorderTraversal(root->left);
 preorderTraversal(root->right);
}
// Postorder traversal
void postorderTraversal(struct node* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->item);
}
// Create a new Node
struct node* createNode(value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}
// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
root->left = createNode(value);
return root->left;
}
// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
root->right = createNode(value);
return root->right;
}

int main() {
struct node* root = initTree(1);

insertLeft(root, 2);
insertRight(root, 3);
insertLeft(root->left, 4);
insertRight(root->left,6);
insertLeft(root->right, 8);
insertRight(root->right,10);

printf("Inorder traversal \n");

inorderTraversal(root);
 printf("\nPreorder traversal \n");
preorderTraversal(root);

printf("\nPostorder traversal \n");

postorderTraversal(root);

freeTree(root);
}

#12. Program to implement Balanced Binary Tree B-Tree BTree.C

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

#define MAX 4
#define MIN 2

struct btreeNode {
int val[MAX + 1], count;
struct btreeNode *link[MAX + 1];
};
struct btreeNode *root;
/* creating new node */
struct btreeNode * createNode(int val, struct btreeNode *child) {
struct btreeNode *newNode;
newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
newNode->val[1] = val;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
}
/* Places the value in appropriate position */
void addValToNode(int val, int pos, struct btreeNode *node, struct btreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
node->link[j + 1] = node->link[j];
j--;
}
node->val[j + 1] = val;
node->link[j + 1] = child;
node->count++;
}
/* split the node */
void splitNode (int val, int *pval, int pos, struct btreeNode *node, struct btreeNode *child, struct btreeNode
**newNode) {
int median, j;

if (pos > MIN)

median = MIN + 1;
else
median = MIN;

*newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));

j = median + 1;
while (j <= MAX) {
(*newNode)->val[j - median] = node->val[j];
(*newNode)->link[j - median] = node->link[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;
if (pos <= MIN) {
addValToNode(val, pos, node, child);
} else {
addValToNode(val, pos - median, *newNode, child);
}
*pval = node->val[node->count];
(*newNode)->link[0] = node->link[node->count];
node->count--;
}
/* sets the value val in the node */
int setValueInNode(int val, int *pval, struct btreeNode *node, struct btreeNode **child) {
int pos;
if (!node) {
*pval = val;
*child = NULL;
return 1;
}
if (val < node->val[1]) {
pos = 0;
} else {
for (pos = node->count;(val < node->val[pos] && pos > 1); pos--);
if (val == node->val[pos]) {
 printf("Duplicates not allowed\n");
return 0;
}
}
if (setValueInNode(val, pval, node->link[pos], child)) {
if (node->count < MAX) {
addValToNode(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}
/* insert val in B-Tree */
void insertion(int val) {
int flag, i;
struct btreeNode *child;

flag = setValueInNode(val, &i, root, &child);

if (flag)
root = createNode(i, child);
}
/* search val in B-Tree */
void searching(int val, int *pos, struct btreeNode *myNode) {
if (!myNode) {
return;
}

if (val < myNode->val[1]) {

*pos = 0;
} else {
for (*pos = myNode->count; (val < myNode->val[*pos] && *pos > 1); (*pos)--);
if (val == myNode->val[*pos]) {
printf("Given data %d is present in B-Tree", val);
return;
}
}
searching(val, pos, myNode->link[*pos]);
return;
}
/* B-Tree Traversal */
void traversal(struct btreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->link[i]);
printf("%d ", myNode->val[i + 1]);
}
traversal(myNode->link[i]);
}
}

int main() {
int val, ch;

while (1) {
printf("\n1. Insertion");
printf("\n2. Searching\n3. Traversal\n");
printf("4. Exit\nEnter your choice: ");
scanf("%d", &ch);
printf("\n");
switch (ch) {
case 1:
printf("\nEnter your input: ");
scanf("%d", &val);
insertion(val);
break;
case 2:
printf("\nEnter the element to search: ");
scanf("%d", &val);
searching(val, &ch, root);
break;
case 3:
printf("\n");
traversal(root);
break;
case 4:
exit(0);
default:
printf("\nU have entered wrong option!!\n");
break;
}
printf("\n");
 }
}

#13. Program for implementing AVL Search Tree AVL-3.C

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int key;
struct node *left;
struct node *right;
int height;
}Node;
/*for creating new node */
Node * newNode(int key){
Node *temp = (Node *)malloc(sizeof(Node));
temp->key = key;
temp->left = NULL;
temp->right = NULL;
temp->height = 0;
return temp;
}
/*deciding max of i and j */
int max(int i, int j){
return i>j?i:j;
}

int height(Node *p){

return p==NULL?-1:(p->height);
}

Node *leftLeftRotn(Node *p){

Node *q = (Node *)malloc(sizeof(Node));
q = p->left;
p->left = q->right;
q->right = p;
p->height = max(height(p->left), height(p->right)) + 1;
q->height = max(height(q->left), p->height) + 1;
return q;
}

Node *rightRightRotn(Node *p){

Node *q = (Node *)malloc(sizeof(Node));
 q = p->right;
p->right = q->left;
q->left = p;
p->height = max(height(p->left), height(p->right)) + 1;
q->height = max(height(q->right), p->height) + 1;
return q;
}
/*double rotation is performed as LR */
Node *leftRightRotn(Node *p){
p->left = rightRightRotn(p->left);
p = leftLeftRotn(p);
return p;
}
/*double rotation is performed as RL */
Node *rightLeftRotn(Node *p){
p->right = leftLeftRotn(p->right);
p = rightRightRotn(p);
return p;
}

Node *balance(Node *p){

int bFactor, hL, hR; /* hL & hR: height of left subtree and right subtree*/
Node *pLeft, *pRight; /*pLeft & pRight: left and right subtree of root p */

if(!p->left){
hL = 0;
} else{
hL = p->left->height + 1;
}
if(!p->right){
hR = 0;
} else{
hR = p->right->height + 1;
}
bFactor = hL - hR;

if(bFactor < 2 && bFactor > -2){

return p;

} else if(bFactor == 2){

pLeft = p->left;
 if( height(pLeft->left) > height(pLeft->right) )
return leftLeftRotn(p);
else
return leftRightRotn(p);
} else {
pRight = p->right;

if( height(pRight->right) > height(pRight->left) )

return rightRightRotn(p);
else
return rightLeftRotn(p);
}
}
/*for inserting the key, newNode is the node needed to be inserted */
Node * insert(Node *p, Node *nwNode){
if(!p){
printf("Key %d\tinserted\n", nwNode->key);
return nwNode;
}
if(nwNode->key > p->key){
p->right = insert(p->right, nwNode);
if(!(p->right))
p->right = nwNode;
}
else{
p->left = insert(p->left, nwNode);
if(!(p->left))
p->left = nwNode;
}
p->height = max(height(p->left), height(p->right)) + 1;
p = balance(p); //balance checking and performing
return p;
}

int main(void){
Node *root = NULL;

printf("RL Rotation - \n");

root = insert(root, newNode(50));
root = insert(root, newNode(40));
root = insert(root, newNode(45)); //RL Rotation required
printf("after Rotation root of tree - %d\n", root->key); // after Rotation root should be 45
 printf("RR Rotation - \n");
root = insert(root, newNode(30));
root = insert(root, newNode(20)); //RR Rotation required
printf("right of left child of root - %d\n", root->left->right->key); // right of left child of root should be 40

printf("LL Rotation - \n");

root = insert(root, newNode(60));
root = insert(root, newNode(80)); //LL Rotation required
printf("left of right child of root - %d\n", root->right->left->key); // left of right child of root should be 50
printf("RL Rotation - \n");
root = insert(root, newNode(70));
root = insert(root, newNode(90));
root = insert(root, newNode(65)); //RL Rotation required
printf("right child of root - %d\n", root->right->key); //right child of root should be 70
return 0;
}

#14. Program for Threaded Binary Tree THBTree.C

#include <stdio.h>
#include <conio.h>

struct tree
{
int val;
struct tree *right;
struct tree *left;
int thread;
};
struct tree *root = NULL;

struct tree* insert_node(struct tree *root, struct tree *ptr, struct tree *rt)
{
if(root == NULL)
{
root = ptr;
if(rt != NULL)
{
root->right = rt;
root->thread = 1;
}
}
 else if(ptr->val < root->val)
root->left = insert_node(root->left, ptr, root);
else
if(root->thread == 1)
{
root->right = insert_node(NULL, ptr, rt);
root->thread=0;
}
else
root->right = insert_node(root->right, ptr, rt);
return root;
}

struct tree* create_threaded_tree()

{
struct tree *ptr;
int num;

printf("\n Enter the elements, press –1 to terminate ");

scanf("%d", &num);
while(num != -1)
{
ptr = (struct tree*)malloc(sizeof(struct tree));
ptr->val = num;
ptr->left = ptr->right = NULL;
ptr->thread = 0;
root = insert_node(root, ptr, NULL);
printf(" \n Enter the next element ");
fflush(stdin);
scanf("%d", &num);
}
return root;
}

void inorder(struct tree *root)

{
struct tree *ptr = root, *prev;
do
{
while(ptr != NULL)
{
prev = ptr;
 ptr = ptr->left;
}
if(prev != NULL)
{
printf(" %d", prev->val);
ptr = prev->right;
while(prev != NULL && prev->thread)
{
printf(" %d", ptr->val);
prev = ptr;
ptr = ptr->right;
}
}
}while(ptr != NULL);
}

void main()
{
//struct tree *root=NULL;
create_threaded_tree();
printf(" \n The in–order traversal of the tree can be given as : ");
inorder(root);
getch();
}

#15. Program to implement Heap Heap_3.C

# include <stdio.h>
int arr[100],n;

void display()
{
int i;
if(n==0)
{
printf("Heap is empty\n");
return;
}
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
}
void insert(int num,int loc)
{
int par;
while(loc>0)
{
par=(loc-1)/2;
if(num<=arr[par])
{
arr[loc]=num;
return;
}
arr[loc]=arr[par];
loc=par;
}
arr[0]=num; /*assign num to the root node */
}

void del(int num)

{
int left,right,i,temp,par;

for(i=0;i<n;i++)
{
if(num==arr[i])
break;
}
if( num!=arr[i] )
{
printf("%d not found in heap\n",num);
return;
}
arr[i]=arr[n-1];
n=n-1;
par=(i-1)/2; /*find parent of node i */
if(arr[i] > arr[par])
{
insert( arr[i],i);
return;
}
left=2*i+1; /*left child of i*/
right=2*i+2; /* right child of i*/
while(right < n)
 {
if( arr[i]>=arr[left] && arr[i]>=arr[right] )
return;
if( arr[right]<=arr[left] )
{
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
i=left;
}
else
{
temp=arr[i];
arr[i]=arr[right];
arr[right]=temp;
i=right;
}
left=2*i+1;
right=2*i+2;
}
if( left==n-1 && arr[i]<arr[left] ) /* right==n */
{ temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
}
}

main()
{
int choice,num;
n=0;/*Represents number of nodes in the heap*/
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
 printf("Enter the number to be inserted : ");
scanf("%d",&num);
insert(num,n);
n=n+1;
break;
case 2:
printf("Enter the number to be deleted : ");
scanf("%d",&num);
del(num);
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Wrong choice\n");
}
}
}

#16. Program for Binary Search BinSearch.C

#include <stdio.h>
int main()
{
int i, first, last, middle, n, search, array[100];

printf("Enter number of elements: ");

scanf("%d", &n);
printf("\nEnter %d integers: ", n);
for (i = 0; i < n; i++)
scanf("%d", &array[i]);

printf("\nEnter value to find: ");

scanf("%d", &search);

first = 0;
last = n - 1;
middle = (first+last)/2;

while (first <= last) {

if (array[middle] < search)
 first = middle + 1;
else if (array[middle] == search) {
printf("\n%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("\nNot found! %d isn't present in the list.\n", search);

return 0;
}

#17. Program for Selection Sort Selection Sort.C

#include <stdio.h>
int main()
{
int l[100], n, i, j, temp,pos;
printf("\nPlease Enter Number of Elements in the List: ");
scanf("%d", &n);
printf("\nPlease Enter List Elements: ");
for(i=0; i<n; i++)
scanf("%d", &l[i]);

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

pos=i;
for(j=pos+1; j<n; j++) {
if(l[pos] > l[j])
pos = j;
}
temp = l[i];
l[i] = l[pos];
l[pos] = temp;
}

printf("\nSorted List: ");

for(i=0; i<n; i++)
printf(" %d", l[i]);
return 0;
}
#18. Program for Bubble Sort Bubble Sort.C
#include <stdio.h>

void bubbleSort(int arr[], int n)

{
int i, j, temp;

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

{
for(j=0; j<n-i-1; j++)
{
if( arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

int main()
{
int arr[100], i, n;

printf("\nEnter the number of elements to be sorted: ");

scanf("%d",&n);
printf("\nEnter %d elements: ",n);
for(i=0; i<n; i++)
scanf(" %d", &arr[i]);
bubbleSort(arr, n);

printf("\nSorted Elements: ");

for(i=0; i<n; i++)
printf(" %d", arr[i]);

return 0;
}

#19. Program for Merge Sort Merge Sort.C

#include <stdio.h>
 /* Function to merge the subarrays of a[] */
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;

int LeftArray[n1], RightArray[n2]; //temporary arrays

/* copy data to temp arrays */

for (i=0; i<n1; i++)
LeftArray[i] = a[beg + i];
for (j=0; j<n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0; /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j<n2)
{
a[k] = RightArray[j];
j++;
 k++;
}
}

void mergeSort(int a[], int beg, int end)

{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}

/* Function to print the array */

void printArray(int a[], int n)
{
int i;

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

printf("%d ", a[i]);
printf("\n");
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);

printf("Before sorting array elements are - \n");

printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}

#20. Program for Quick Sort QuickSort.C

#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
 if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(number[i]<=number[pivot] && i<last)
i++;

while(number[j]>number[pivot])
j--;

if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}

temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}

int main(){
int i, count, number[25];

printf("How many elements are u going to enter?: ");

scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);

return 0;
}

#21. Program for Radix Sort Radix Sort.C

#include <stdio.h>
#include <conio.h>

#define size 10

int largest(int arr[], int n);

void radix_sort(int arr[], int n);

void main()
{
int arr[size], i, n;

printf("\n Enter the number of elements in the array: ");

scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
scanf("%d", &arr[i]);
radix_sort(arr, n);
printf("\n The sorted array is: \n");
for(i=0;i<n;i++)
printf(" %d\t", arr[i]);
getch();
}

int largest(int arr[], int n)

{
int large=arr[0], i;
for(i=1;i<n;i++)
if(arr[i]>large)
large = arr[i];
return large;
}

void radix_sort(int arr[], int n)

{
int bucket[size][size], bucket_count[size];
int i, j, k, remainder, NOP=0, divisor=1, large, pass;
large = largest(arr, n);
while(large>0)
 {
NOP++;
large/=size;
}
for(pass=0;pass<NOP;pass++) // Initialize the buckets
{
for(i=0;i<size;i++)
bucket_count[i]=0;
for(i=0;i<n;i++)
{
// sort the numbers according to the digit at passth place
remainder = (arr[i]/divisor)%size;
bucket[remainder][bucket_count[remainder]] = arr[i];
bucket_count[remainder] += 1;
}
// collect the numbers after PASS pass
i=0;
for(k=0;k<size;k++)
{
for(j=0;j<bucket_count[k];j++)
{
arr[i] = bucket[k][j];
i++;
}
}
divisor *= size;
}
}

#22. Program for Heap Sort Heap Sort.C

#include <stdio.h>
// function to heapify a subtree. Here 'i' is the index of
// root node in array a[], and 'n' is the size of heap.
void heapify(int a[], 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

if (left < n && a[left] > a[largest])

largest = left; // If left child is larger than root
if (right < n && a[right] > a[largest])
 largest = right; // If right child is larger than root
if (largest != i) { // If root is not largest
int temp = a[i];
a[i] = a[largest]; // swap a[i] with a[largest]
a[largest] = temp;
heapify(a, n, largest);
}
}
/*Function to implement the heap sort*/
void heapSort(int a[], int n)
{
int i;
for (i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
for (i = n - 1; i >= 0; i--) {
int temp = a[0]; // One by one extract an element from heap
a[0] = a[i]; // Move current root element to end
a[i] = temp; // swap a[0] with a[i]
heapify(a, i, 0);
}
}
/* function to print the array elements */
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
printf("%d ", arr[i]);
}

int main()
{
int a[] = {48, 10, 23, 43, 28, 26, 1};
int n = sizeof(a) / sizeof(a[0]);

printf("Before sorting array elements are - \n");

printArr(a, n);
heapSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}