Binary Tree Implementation and Operations in C

C program to implement binary tree and its three operations:

 1. Preorder traversal
 2. Inorder traversal
 3. Postorder traversal

Source Code

binarytree.c

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

// Defines a tree node as a structure
struct node { 
     struct node * left;
     char data; 
     struct node * right;
 };

// Function declaration
struct node * buildTree ( int ); 
void preorder(struct node *); 
void inorder(struct node *); 
void postorder( struct node *root ); 

// Tree node data
char array[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' }; 

// Indices of left children
int leftcount[ ] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 }; 

// Indices of right children
int rightcount[ ] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 }; 


int main() { 
      struct node *root; 
      int ch;
      root = buildTree ( 0 );
   
      do{
           printf("\n1: Preorder Traversal\n");
           printf("2: Inorder Traversal\n");
           printf("3: Postorder Traversal\n");
           printf("\tEnter your choice: ");
           scanf("%d",&ch);

           switch(ch) {
                case 1:
                     printf("\nPre-order Traversal: \n");
                     preorder(root);
                     break;
                case 2:
                     printf("\nIn-order Traversal: \n");
                     inorder(root);
                     break;
                case 3:
                     printf("\nPost-order Traversal: \n");
                     postorder(root); 
                     break;
                default:
                     printf("\nExiting.....\n");
           }
      }while(ch>0 && ch<4);
 } 

// Function to build tree using above data
struct node * buildTree ( int index ) { 
      struct node *temp = NULL;
      if (index != -1) {
           temp = (struct node *) malloc( sizeof ( struct node ) );
           temp->left = buildTree ( leftcount[index] );
           temp->data = array[index];
           temp->right = buildTree ( rightcount[index] );
      }
      return temp;
}

// Function to print tree data using inoder traversal 
void inorder( struct node *root ) {
      if (root != NULL) {
           inorder(root->left);
           printf("%c\t", root->data);
           inorder(root->right);
      }
}

// Function to print tree data using preorder traversal 
 void preorder( struct node *root ) {
      if (root != NULL) {
           printf("%c\t", root->data);
           preorder(root->left);
           preorder(root->right);
      }
}

// Function to print tree data using postorder traversal 
void postorder( struct node *root ) {
      if (root != NULL) {
           postorder(root->left);
           postorder(root->right);
           printf("%c\t", root->data);
      }
}

Multiplication of two matrices / Matrix multiplication

Let us see how to multiply two matrices. Here is the rule applicable for the multiplication of two matrices. Multiplication of two matrices is possible only if the number of columns of the first matrix is equal to the number of rows of the second matrix.

For example it is possible to multiply two matrices with size  2 x 2 and 2 x 3. Here number of columns of first matrix ie. 2 is equal to the number of rows of the second matrix that is again  2.

Example:

C program for matrix multiplication

matmult.c

#include <stdio.h>
int main() {
int m, n, p, q, i, j, k, sum = 0;
int a[10][10], b[10][10], c[10][10];

clrscr();
   
        // Input order or size of first matrix
printf("Enter the number of rows and columns of first matrix:");
scanf("%d%d", &m, &n);

        // Input first matrix
for (i=0;i<m;i++)
for (j=0;j<n;j++) {
printf("Enter the element %d, %d of matrix a:", i,j);
scanf("%d", &a[i][j]);
}

         // Input order or size of second matrix
printf("\nEnter the number of rows and columns of second matrix:");
scanf("%d%d", &p, &q);

         // Check whether the matrices are compatible for multiplication
if (n!=p)
printf("\nMatrices with entered orders can't be multiplied with each other.");
else {
                // Input second matrix
for (i=0;i<p;i++)
for (j=0;j<q;j++) {
printf("Enter the %d, %d element of  matrix b:", i, j);
scanf("%d", &b[i][j]);
}
             
               // Logic for multiplication
for (i=0;i<m;i++) { // Loops row times of first matrix
for (j=0;j<q;j++) { // Loops column times of second  matrix
for (k=0;k<p;k++) { // Loops row times of  second matrix
sum=sum+a[i][k]*b[k][j];
}

c[i][j] = sum;
sum = 0;
}
}

                // Displays first matrix
printf("Matrix A:\n");

for (i=0;i<m;i++) {
for (j=0;j<n;j++)
printf("%d\t", a[i][j]);
printf("\n");
}

                // Displays second matrix
printf("Matrix B:\n");

for (i=0;i<p;i++) {
for (j=0;j<q;j++)
printf("%d\t", b[i][j]);
printf("\n");
}

                // Displays third matrix
printf("Product of entered matrices:\n");

for (i=0;i<m;i++) {
for (j=0;j<q;j++)
printf("%d\t", c[i][j]);
printf("\n");
}
}

return 0;
}

Recursive Function in C Language

Recursion is a method used to solve some problems where the solution depends on solutions to smaller instances of the same problem. The approach can be applied to types of problems for which solution can be represented recursively.

C Program to check Leap Year

A leap year is a year containing one additional day in order to keep the calendar year synchronized with the astronomical or seasonal year.

For example, in the Gregorian calendar, each leap year lasts 366 days instead of the usual 365, by extending February to 29 days rather than the common 28 days.

For example:

1991 is not  a leap year.
2000  is a leap year.
1900  is not a leap year.
2004 is  a leap year.

C Program for generating Fibonacci Series

Fibonacci series is a series of integer numbers where the first two numbers in the series are 1 and 1, or 0 and 1, depending on the chosen starting point of the series, and each subsequent number is the sum of the previous two numbers  ie. Fn = Fn-1  +  Fn-2.


For example:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ….

Or

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ….

C program to check if a given matrix is a sparse matrix or not

A sparse matrix is a matrix in which most of the elements are zero.

For example let us consider two matrices  A and B

Matrix A
1 0 0
1 1 0
0 1 0

Matrix B
1 1 1
0 1 0
1 0 1

C Program to implement a Queue using array

Queue 

 A queue is a a linear collection of objects, where objects are inserted and removed according to the first-in first-out (FIFO) principle. An example of a queue is a line of people in a ticket counter. New additions to the line is made to the back of the queue, while removal (or serving) happens in the front. In a queue only two operations are allowed enqueue/insert and dequeue/delete. Enqueue means to insert an item into the back of the queue, dequeue means deleting the front item. 

C Program to implement stack using array

A stack is a data structure which is a  logical representation of  a real physical stack or pile of objects, where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of the data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it. In a stack last added item is deleted first and so it is called a LIFO (Last In First Out) data structure.

C Program to check a number is prime or composite

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime because 1 and 5 are its only positive integer factors, whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6.

Examples of prime numbers are:  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,.....

Let us see a function to check whether a number is prime or not.

// Function to check prime returns 0 or 1
int isprime(int value) {
    int i;
    for (i=2;i<=value/2;i++)
        if (value%i==0)
            return (0);
    return 1;
}

Here value is the number to be checked given as parameter to the function. This function returns 1 if the value prime and returns 0 if it is not.

C Program to check whether an array is sorted or not

To sort an array there are different methods. And you may be familiar with them. However, what to do if you want to simply check whether an array is sorted or not.

Method 1
Start from the beginning of the array and compare whether the 0th element is less than 1st element and so on up to the end of the array (for Ascending order). If you can move up to the end of the array without any failure in the condition, then you can assure that the array is sorted.

Method 2
You can apply the reverse logic of method 1. Initially check whether the 0th element is greater than 1st element. If this condition is true, then you can say it is not sorted without checking further.

Let us see a function using the second method to check whether an array is sorted or not.

int issorted(int array[], int len){
    int i;
    for(i=0;i<len-1;i++)
        if (a[i]>a[i+1])
            return (0); //Unsorted

    return (1); //Sorted

}

Here array[] is the actual array and len is the length of the array. This function returns 1 if the array is sorted and returns 0 if it is not sorted.

C Program to Insert an element in an array

How to insert an element in a given position in an array. It is very simple, if you want insert an element at nth position, you want to move or shift the elements right to the nth location by one place and make the nth location free. Then you can just assign the new value to the nth location.

Let us see a function implemented in C Language for inserting an element in an array.

void insert(int array[],int value,int position,int len)
{
    int i;
    for (i=len + 1 ; i>=position;i--)
        a[i]=a[i-1];
    a[position-1]=value;
    return;
}

Here array[] is the actual array where insertion is to be made. value is the new value that has to be inserted and position is the location where the value is to be inserted. len is the existing length of the array.

C Program to check Amicable Numbers

Amicable numbers are two different numbers so related that the sum of the proper divisors of first number is equal to the other number and vice-versa. (A proper divisor of a number is a positive factor of that number other than the number itself. For example, the proper divisors of 6 are 1, 2, and 3.).

For example, the smallest pair of amicable numbers is (220, 284); for the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71 and 142, of which the sum is 220.

The first few amicable pairs are: (220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368).

Following is a C language program to check the given two numbers are amicable or not.

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

int  main() {
    int i, sf1=0, sf2=0,  m, n;

    clrscr();
    printf("Enter the first number :");
    scanf("%d", &m);
    printf("Enter the second number :");
    scanf("%d",&n);

    if (m==n) {
       printf("Given numbers are not amicable");
       getch();
       return 0;
    }

   / * Finds sum of proper divisors of the first number (m) */
    for (i=1;i<=m/2;i++){
        if (m%i==0)
            sf1=sf1+i;
        }

 / * Finds sum of proper divisors of the second number (n) only if sum of proper divisors of first number is equal to the second number */

    if (sf1==n)
        for (i=1; i<=n/2;i++){
            if (n%i==0)
                sf2=sf2+i;
        }

     if (sf2==m)
        printf ("Given numbers are amicable");
     else
        printf("Given numbers are not amicable");

     
     getch();
     return 0;
}

C Function to compare two strings

This is a C function to compare two strings. The function takes two strings as arguments, loops while the characters in both the string are equal and the end of either string is not reached.  After finishing the loop, it returns the difference of ASCII values (string1[i] - string2[i]) of the characters where the loop is stopped. 

So the final value may be:
          -ve, if string 1 is less than string 2
          +ve, if string 1 is greater than string 2
           0 , if both the strings are same


Source Code


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

/* Function definition */
int cmpstr (char str1 [], char str2[] ) {
    int i, diff;

    for (i=0;str1[i]==str2[i] && str1[i]!=0 && str2[i]!=0;i++);
    diff = str1[i]-str2[i];

    return diff;
}


int main() {
    char str1[30], str2[30];
    int diff;

    clrscr();

    printf("Enter a string:");
    scanf("%s", str1);
    printf("Enter another string:");
    scanf("%s", str2);


    diff=cmpstr(str1, str2); // Function Call

    if (diff<0)
        printf("\n\nstring 1 (%s) is less than string 2 (%s)", str1, str2);
    else if (diff==0)
        printf("\n\nstring 1 (%s) and  string 2 (%s) are same", str1, str2);
    else
        printf("\n\nstring 1 (%s) is greater than string 2 (%s)", str1, str2);



    getch();
    return 0;
}


Output

String1 is less than String2

String1 is greater than String2

String1 and  String2 are same

C Function to find out the length of a string

This is a function written in C language to find out the length of a string given by the user.


Source Code

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

/* Function definition */
int lenstr (char str [] ) {
    int len=0;
    while (str[len++]!=0);
    len--;
    return len;
}



int main() {
    char str[30];
    int len=0;

    clrscr();

    printf("Enter a string:");
    scanf("%s", str);
    len=lenstr(str); // Function Call
    printf("\n\nLength of the string: %d", len);

    getch();
    return 0;
}



Output

C Program to merge two sorted arrays

 This program merges two sorted arrays and creates a third array with the values from the two arrays. The final array also is in sorted form. Here first element of list1 and list2 are compared, the lesser value will be assigned to list3. Index of the array, from where the value is taken, ie. i if the array is list1 and j if the array is list2 will be incremented. Index of the third array ie. k will be incremented in both cases. This process will be repeated up to the end of either list1 or list2.

Finally, if list1 or list2  contains any remaining values, it will be copied to list3.


Source Code

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

int main() {
    int list1[6]={ 1, 3, 5, 7, 9, 11 };
    int list2[8]={ 2, 4, 6, 8, 10, 12, 13, 14 };
    int list3[14], i, j, k;

    clrscr();


    for (i=0, j=0, k=0; i<6 && j<8 ; k++) {
        /* 
             if ith element of list1 is less than jth element of list2, takes value from list1
             otherwise takes value from list2 and assigns to list3.
      */
        if (list1[i] < list2[j]) {
            list3[k] = list1[i];
            i++;
        }
        else {
            list3[k] = list2[j];
            j++;
        }

    }

  /* If list1 has remaining values assigns them to list3*/
    for (; i<6 ;i++, k++) {
        list3[k] = list1[i];
    }

  /* If list2 has remaining values assigns them to list3 */
     for (; j<8 ;j++, k++) {
        list3[k] = list2[j];
    }

    printf("\n\nList 1\n\n");
    for (i=0; i<6 ; i++) {
        printf ("%d ", list1[i]);
    }

    printf("\n\nList 2\n\n");
    for (i=0; i<8 ; i++) {
        printf ("%d ", list2[i]);
    }

    printf("\n\nList 3\n\n");
    for (i=0; i<14 ; i++) {
        printf ("%d ", list3[i]);
    }

    printf("\n\nPress any key to continue...");
    getch();

    return 0;
}


Output

C Program for Binary Searching

This program performs searching in a sorted array using Binary Search algorithm. It takes the Number of values (max) in the list, the actual values in the list, and the value to be searched for as inputs. The program then searches for the value in the list using Binary Search method and  prints the location of the value, if it is found. Otherwise it displays an error message.

Pre-condition
The array used as input for the program should be sorted in ascending order. So the user has to enter the values in sorted order. This program does not sort the array. You can find program for sorting this site itself in the following sections.

C Program for Quick Sorting
C Program for Insertion Sorting
C Program for Bubble Sorting

Source code for Binary Search


/*
    Binary Search
    -------------
    Input:
        1. No. of values in the List
        2. Actual values in the list (in ascending order)
        3. The value to be searched for
    Output:
        1. If the "search value" is there in the list, location of the value
        2. If the value is there in the list, an error message.
*/


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

int main() {
    int i, first, last, middle, max, findme, list[100];

    clrscr();

    printf("Enter number of elements:");
    scanf("%d",&max);

    printf("Enter %d values:\n", max);

    for ( i = 0 ; i < max ; i++ )
        scanf("%d",&list[i]);

    printf("Enter value to be searched for:");
    scanf("%d",&findme);

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

    while( first <= last )
    {
        if ( list[middle] < findme )
            first = middle + 1;
        else if ( list[middle] == findme )
        {
            printf("%d found at location %d.\n", findme, middle + 1);
            break;
        }
        else
            last = middle - 1;

        middle = (first + last)/2;
    }

    if ( first > last )
        printf("Not found! %d is not present in the list.\n", findme);

    getch();

    return 0;
}


Output

C Program for Quick Sorting

 C Source code for implementing Quick Sort using recursive function . This program accepts No. of values to be sorted and the actual values to be sorted from user. By using Quick Sort algorithm it sorts the values and prints the output.

Source Code

/*
    Quick Sorting
    --------------
    Input :
        1. No. of values to be sorted i.e. n.
        2. Values to be sorted. i.e. n values.
    Output:
        List of sorted values.
*/


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

void quicksort(int [100], int, int);

int main() {
    int array[100], size, i;

    clrscr();
    printf("Enter size of the array: ");
    scanf("%d", &size);

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

    // Call the function by passing array, starting index and ending index
    quicksort(array, 0, size-1);

    printf("\n\nArray after sorting:\n");
    for(i=0;i<size;i++)
        printf("%d ", array[i]);

    getch();
    return 0;
}

/*  Function for Quick Sorting */

void quicksort(int array[100], int start_index, int end_index) {
    int pivot,j,temp,i;

    if(start_index<end_index){
        pivot=start_index;
        i=start_index;
        j=end_index;

        while(i < j){
            while(array[i] <= array[pivot] && i < end_index)
                i++;
            while(array[j] > array[pivot])
                j--;

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

        temp = array[pivot];
        array[pivot] = array[j];
        array[j] = temp;
        quicksort(array,start_index,j - 1);
        quicksort(array,j + 1,end_index);

    }
}


Output
 

C Program for Insertion Sorting

 C Source code for implementing Insertion Sort. This program accepts No. of values to be sorted and the actual values to be sorted from user. By using Insertion Sort algorithm it sorts the values and prints the output.

Source Code
 
/*
    Insertion sorting
    --------------
    Input :
        1. No. of values to be sorted i.e. n.
        2. Values to be sorted. i.e. n values.
    Output:
        List of sorted values.
*/

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


#include <stdio.h>

int main() {
    int n, list[100], i, j, temp;

    clrscr();
    printf("Enter number of elements (maximum: 100):");
    scanf("%d", &n);

    printf("Enter %d values for sorting:\n", n);

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

    for (i = 1 ; i <= n - 1; i++) {
        j = i;

        while ( j > 0 && list[j] < list[j-1]) {
            temp = list[j];
            list[j] = list[j-1];
            list[j-1] = temp;

            j--;
        }
    }


    printf("\n\nSorted list:\n");

    for (i = 0; i <= n - 1; i++) {
        printf("%d\n", list[i]);
    }

    printf("\nPress any key to continue...");
    getch();
    return 0;
}


Output

C Program for Bubble Sorting

 C Source code for implementing Bubble Sorting. This program accepts No. of values to be sorted and the actual values to be sorted from user. By using bubble sort algorithm it sorts the values and prints the output.


Source code

/*
    Bubble sorting
    --------------
    Input :
        1. No. of values to be sorted i.e. n.
        2. Values to be sorted. i.e. n values.
    Output:
        List of sorted values.
*/

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

int main() {
    int list[100], n, i, j, temp;

    clrscr();
    printf("Enter number of values to be sorted (Maximum: 100):");
    scanf("%d", &n);

    printf("Enter %d values:\n", n);

    for (i = 0; i < n; i++)
        scanf("%d", &list[i]);


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

    printf("Sorted list:\n");
    for ( i = 0 ; i < n ; i++ )
        printf("%d\n", list[i]);

    getch();

    return 0;
}


Output

C Program to reverse a number

C Program to reverse a number 

This is a C program to reverse a number. In this example, it takes the a number as input to the program, reverses the number and stores in another variable and prints the result.

See the source code of the program

/*

            Program to reverse a number

            input  : a number

            output : reverse of the number

*/

#include <stdio.h>

#include <conio.h>

int main() {

int n, reverse = 0;

                printf("Enter a number to reverse:");

                scanf("%d",&n);

                while (n != 0) {

                                reverse = reverse * 10;

                                reverse = reverse + n%10;

                                n = n/10;

                }

                printf("Reverse of entered number is = %d\n", reverse);

                getch();

                return 0;

}

Output