Friday 18 October 2024

Traversal -Create Node,Preorder,PostOrder,Inorder


  • #include <stdio.h>  

  • #include <stdlib.h>  

  •   

  • struct node {  

  •     int element;  

  •     struct node* left;  

  •     struct node* right;  

  • };  

  •   

  • /*To create a new node*/  

  • struct node* createNode(int val)  

  • {  

  •     struct node* Node = (struct node*)malloc(sizeof(struct node));  

  •     Node->element = val;  

  •     Node->left = NULL;  

  •     Node->right = NULL;  

  •   

  •     return (Node);  

  • }  

  •   

  • /*function to traverse the nodes of binary tree in preorder*/  

  • void traversePreorder(struct node* root)  

  • {  

  •     if (root == NULL)  

  •         return;  

  •     printf(" %d ", root->element);  

  •     traversePreorder(root->left);  

  •     traversePreorder(root->right);  

  • }  

  •   

  •   

  • /*function to traverse the nodes of binary tree in Inorder*/  

  • void traverseInorder(struct node* root)  

  • {  

  •     if (root == NULL)  

  •         return;  

  •     traverseInorder(root->left);  

  •     printf(" %d ", root->element);  

  •     traverseInorder(root->right);  

  • }  

  •   

  • /*function to traverse the nodes of binary tree in postorder*/  

  • void traversePostorder(struct node* root)  

  • {  

  •     if (root == NULL)  

  •         return;  

  •     traversePostorder(root->left);  

  •     traversePostorder(root->right);  

  •     printf(" %d ", root->element);  

  • }  

  •   

  •   

  • int main()  

  • {  

  •     struct node* root = createNode(36);  

  •     root->left = createNode(26);  

  •     root->right = createNode(46);  

  •     root->left->left = createNode(21);  

  •     root->left->right = createNode(31);  

  •      

  •     printf("\n The Preorder traversal of given binary tree is -\n");  

  •     traversePreorder(root);  

  •       

  •     printf("\n The Inorder traversal of given binary tree is -\n");  

  •     traverseInorder(root);  

  •       

  •     printf("\n The Postorder traversal of given binary tree is -\n");  

  •     traversePostorder(root);  

  •   

  •     return 0;  

  • }    


Without structure

#include <stdio.h>

#include <stdlib.h>


#define MAX_NODES 100  // Maximum number of nodes in the tree


// Global arrays to represent tree elements and relationships

int element[MAX_NODES];   // Stores node values

int left[MAX_NODES];      // Stores index of the left child (-1 if no child)

int right[MAX_NODES];     // Stores index of the right child (-1 if no child)


// Function to create a new node at the given index

void createNode(int index, int val, int leftChild, int rightChild) {

    element[index] = val;           // Store the element at the given index

    left[index] = leftChild;         // Store the left child index (-1 if no child)

    right[index] = rightChild;       // Store the right child index (-1 if no child)

}


// Preorder traversal (Root -> Left -> Right)

void traversePreorder(int index) {

    if (index == -1) return;  // Base case: no node to traverse


    printf(" %d ", element[index]);  // Visit root

    traversePreorder(left[index]);   // Visit left subtree

    traversePreorder(right[index]);  // Visit right subtree

}


// Inorder traversal (Left -> Root -> Right)

void traverseInorder(int index) {

    if (index == -1) return;  // Base case: no node to traverse


    traverseInorder(left[index]);    // Visit left subtree

    printf(" %d ", element[index]);  // Visit root

    traverseInorder(right[index]);   // Visit right subtree

}


// Postorder traversal (Left -> Right -> Root)

void traversePostorder(int index) {

    if (index == -1) return;  // Base case: no node to traverse


    traversePostorder(left[index]);   // Visit left subtree

    traversePostorder(right[index]);  // Visit right subtree

    printf(" %d ", element[index]);   // Visit root

}


int main() {

    // Create nodes using arrays instead of structures

   // Create binary tree nodes

    createNode(0, 36, 1, 2);  // Root node with value 36

    createNode(1, 26, 3, 4);  // Node 26 with left child 21 and right child 31

    createNode(2, 46, -1, -1);  // Node 46 with no children

    createNode(3, 21, -1, -1);  // Node 21 with no children

    createNode(4, 31, -1, -1);  // Node 31 with no children

  


    printf("\nThe Preorder traversal of the binary tree is:\n");

    traversePreorder(0);  // Start from the root (index 0)


    printf("\n\nThe Inorder traversal of the binary tree is:\n");

    traverseInorder(0);  // Start from the root (index 0)


    printf("\n\nThe Postorder traversal of the binary tree is:\n");

    traversePostorder(0);  // Start from the root (index 0)


    return 0;

}



Binary search

 Binary search is an efficient algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the target value is equal to the middle element, the search is complete. If the target is smaller, the search continues in the lower half, and if the target is larger, it continues in the upper half.


mid=low +(High-low)/2


Compare the target value with the element at mid:

  • If arr[mid] == target, return mid.

  • If arr[mid] < target, search the right half by setting low = mid + 1.

  • If arr[mid] > target, search the left half by setting high = mid - 1.



Binary Search 

#include <stdio.h>

#define SIZE 8  // Define the size of the array


// Binary search function

int binarySearch(int arr[], int target) {

    int low = 0, high = SIZE - 1;  // Use SIZE to determine the range


    while (low <= high) {

        int mid = low + (high - low) / 2;  

        if (arr[mid] == target)

            return mid;  // Target found

        else if (arr[mid] < target)

            low = mid + 1;  // Search in the right half

        else

            high = mid - 1;  // Search in the left half

    }

    return -1;  // Target not found

}


int main() {

    int arr[SIZE] = {1, 3, 5, 7, 9, 11, 13, 15};  // Array


    int target;  // Variable to store the target value


    // Take input from user

    printf("Enter the target value: ");

    scanf("%d", &target);


    // Perform binary search without passing the size

    int result = binarySearch(arr, target);


    // Display the result

    if (result != -1)

        printf("Element found at index %d\n", result);

    else

        printf("Element not found\n");


    return 0;

}



Linear Search

 

What is Linear Search?

Linear search is a simple search algorithm that looks for a specific value in a list or array by checking each element one-by-one. It continues until it finds the value or reaches the end of the list.


How Linear Search Works

  1. Start at the first element of the list.

  2. Compare each element with the target value.

  3. If a match is found, return the position of the element.

  4. If no match is found by the end, return “not found.”


 Linear Search

#include <stdio.h>   


int linearSearch(int arr[], int target)

 {  

    int i;  

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

        if (arr[i] == target) {  

            return i;  // Element found at index i  

        }  

    }  

    return -1;  // Element not found  

}  

  

int main() {  

    int arr[5] = {10, 2, 8, 5, 17};  

  

    int target;  // Declare target variable  


        printf("Enter the value to search: ");

    scanf("%d", &target);  // Take input from user


    int result = linearSearch(arr, target);  

    if (result == -1) {  

        printf("Element not found in the array.\n");  

    } else {  

        printf("Element found", result);  

    }  

    return 0;  

}  



Dynamic linear serach

#include <stdio.h>


#define SIZE 5  // Size of the array


// Linear search function

int linearSearch(int arr[], int target) {

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

        if (arr[i] == target) {

            return i;  // Element found at index i

        }

    }

    return -1;  // Element not found

}


int main() {

    int arr[SIZE];  // Declare array


    // Take input for the array from the user

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

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

        printf("Element %d: ", i + 1);

        scanf("%d", &arr[i]);  // Input each element

    }


    int target;  // Declare target variable


    // Take target element input from user

    printf("Enter the value to search: ");

    scanf("%d", &target);  // Input the target value


   

    printf("You entered target: %d\n", target);


    // Perform linear search

    int result = linearSearch(arr, target);


    // Display the result

    if (result == -1) {

        printf("Element not found in the array.\n");

    } else {

        printf("Element found at index %d.\n", result);

    }


    return 0;

}