Data Structures Module_V

 

Module – V

 1. Binary Tree Traversals using Linked List

Inorder:

#include <stdio.h>

#include <stdlib.h> 

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

}; 

// Function to perform inorder traversal

void inorderTraversal(struct Node* root) 

{ 

    // Empty Tree

    if (root == NULL)

        return; 

    // Recur on the left subtree

    inorderTraversal(root->left); 

    // Visit the current node

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

    // Recur on the right subtree

    inorderTraversal(root->right);

} 

// Function to create a new node

struct Node* newNode(int data) 

{ 

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

    node->data = data;

    node->left = NULL;

    node->right = NULL; 

    return node;

} 

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);

    printf("Inorder traversal: ");

    inorderTraversal(root);

    printf("\n");

    return 0;

} 

Output:

Inorder traversal: 4 2 5 1 3

 

Preorder:

#include <stdio.h>

#include <stdlib.h> 

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

}; 

// Function to perform preorder traversal

void preorderTraversal(struct Node* root) 

{ 

    // Base case

    if (root == NULL)

        return; 

    // Visit the current node

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

    // Recur on the left subtree

    preorderTraversal(root->left); 

    // Recur on the right subtree

    preorderTraversal(root->right);

} 

struct Node* newNode(int data) 

{

    struct Node* node =

      (struct Node*)malloc(sizeof(struct Node));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return node;

} 

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);

    preorderTraversal(root);

    return 0;

}

Output:

1 2 4 5 3

 

Postorder:

#include <stdio.h>

#include <stdlib.h> 

struct Node 

{

    int data;

    struct Node* left;

    struct Node* right;

}; 

// Function to perform postorder traversal

void postorderTraversal(struct Node* node) 

{ 

    // Base case

    if (node == NULL)

        return; 

    // Recur on the left subtree

    postorderTraversal(node->left); 

    // Recur on the right subtree

    postorderTraversal(node->right); 

    // Visit the current node

    printf("%d ", node->data);

} 

struct Node* newNode(int data) 

{

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

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return node;

} 

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);

    postorderTraversal(root);

    return 0;

}

Output:

4 5 2 3 1

 

2. Write program to create binary search tree for given list of integers. perform inorder traversal of the tree. implement insertion and deletion operations

#include <stdio.h> 

#include <stdlib.h> 

#include <stdbool.h>   

//Represent a node of binary tree 

struct node

{ 

    int data; 

    struct node *left; 

    struct node *right; 

};   

//Represent the root of binary tree 

struct node *root= NULL;   

//createNode() will create a new node 

struct node* createNode(int data)

{ 

    //Create a new node 

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

    //Assign data to newNode, set left and right children to NULL 

    newNode->data= data; 

    newNode->left = NULL; 

    newNode->right = NULL;      

    return newNode; 

}   

//insert() will add new node to the binary search tree 

void insert(int data) 

{ 

    //Create a new node 

    struct node *newNode = createNode(data);      

    //Check whether tree is empty 

    if(root == NULL){ 

        root = newNode; 

        return; 

      } 

    else 

{ 

        //current node point to root of the tree 

        struct node *current = root, *parent = NULL;          

        while(true) 

        { 

            //parent keep track of the parent node of current node. 

            parent = current;   

            //If data is less than current's data, node will be inserted to the left of tree 

            if(data < current->data) 

        { 

                current = current->left; 

                if(current == NULL) 

                { 

                    parent->left = newNode; 

                    return; 

                } 

            } 

            //If data is greater than current's data, node will be inserted to the right of tree 

            else { 

                current = current->right; 

                if(current == NULL) 

                { 

                    parent->right = newNode; 

                    return; 

                } 

            } 

        } 

    } 

}   

//minNode() will find out the minimum node 

struct node* minNode(struct node *root) 

{ 

    if (root->left != NULL) 

        return minNode(root->left); 

    else  

        return root; 

}    

//deleteNode() will delete the given node from the binary search tree 

struct node* deleteNode(struct node *node, int value) 

{ 

    if(node == NULL){ 

          return NULL; 

     } 

    else 

        { 

        //value is less than node's data then, search the value in left subtree 

        if(value < node->data) 

            node->left = deleteNode(node->left, value);          

        //value is greater than node's data then, search the value in right subtree 

        else if(value > node->data) 

            node->right = deleteNode(node->right, value);          

        //If value is equal to node's data that is, we have found the node to be deleted 

        else 

        { 

            //If node to be deleted has no child then, set the node to NULL 

            if(node->left == NULL && node->right == NULL) 

                node = NULL;              

            //If node to be deleted has only one right child 

            else if(node->left == NULL) 

            { 

                node = node->right; 

            } 

             //If node to be deleted has only one left child 

            else if(node->right == NULL) 

            { 

                node = node->left; 

            }              

            //If node to be deleted has two children node 

            else 

            { 

                //then find the minimum node from right subtree 

                struct node *temp = minNode(node->right); 

                //Exchange the data between node and temp 

                node->data = temp->data; 

                //Delete the node duplicate node from right subtree 

                node->right = deleteNode(node->right, temp->data); 

            } 

        } 

        return node; 

    } 

}   

//inorder() will perform inorder traversal on binary search tree 

void inorderTraversal(struct node *node) 

{        

    //Check whether tree is empty 

    if(root == NULL)

   { 

        printf("Tree is empty\n"); 

          return; 

     } 

    else 

  {            

        if(node->left!= NULL) 

            inorderTraversal(node->left); 

        printf("%d ", node->data); 

        if(node->right!= NULL) 

          inorderTraversal(node->right);            

    }       

}        

int main() 

{ 

    //Add nodes to the binary tree 

    insert(50); 

    insert(30); 

    insert(70); 

    insert(60); 

    insert(10); 

    insert(90);      

    printf("Binary search tree after insertion: \n"); 

    //Displays the binary tree 

    inorderTraversal(root);      

    struct node *deletedNode = NULL; 

    //Deletes node 90 which has no child 

    deletedNode = deleteNode(root, 90); 

    printf("\nBinary search tree after deleting node 90: \n"); 

    inorderTraversal(root);      

    //Deletes node 30 which has one child 

    deletedNode = deleteNode(root, 30); 

    printf("\nBinary search tree after deleting node 30: \n"); 

    inorderTraversal(root);      

    //Deletes node 50 which has two children 

    deletedNode = deleteNode(root, 50); 

    printf("\nBinary search tree after deleting node 50: \n"); 

    inorderTraversal(root);   

    return 0; 

} 

 

Output:

Binary search tree after insertion:

10 30 50 60 70 90

Binary search tree after deleting node 90:

10 30 50 60 70

Binary search tree after deleting node 30:

10 50 60 70

Binary search tree after deleting node 50:

10 60 70

 

Comments

Post a Comment

Popular posts from this blog

Data Structures Module-IV

  Module-IV 1) Implementation of Queue Operations using                      i) Arrays    ii) Linked List 2) Implementation of Circular Queue Operations using                      i) Arrays    ii) Linked List 3) Implement Dequeue using Linked List.   1) a) Implementation of Queue Operations using Arrays. #include<stdio.h> #include<stdlib.h> #define SIZE 5 void enqueue(); void dequeue(); void display(); int queue[SIZE],front=-1,rear=-1,ele; int main() {     int ch;     while(1)     {     printf("\n menu");     printf("\n 1.enqueue\n 2.dequeue\n 3.display");     printf("\n enter ur choice");     scanf("...
Read more

DS - Module - II - DLL

  Implementation of Doubly Linked List #include<stdio.h> #include<stdlib.h> void create(); void display(); void insert_at_begin(); void insert_at_end(); void insert_at_pos(); void delete_at_begin(); void delete_at_end(); void delete_at_pos(); void reverse(); struct node {     int data;     struct node *prev,*next; }*new,*head,*temp,*d; int i,value,p; char ch; void main() {     int n;     printf("\n 1.create\n 2.display\n 3.insert_at_begin\n 4.insert_at_end\n 5.insert_at_pos\n 6.delete_at_begin\n 7.delete_at_end\n 8.delete_at_pos\n 9.reverse");   while(1) {     printf("enter your choice:");     scanf("%d",&n);     switch(n)     {           case 1:create();               ...
Read more