Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Pes2ug20cs282 - Rohit V Shastry - Sec E - Week 8

    Uploaded by

    ROHIT V SHASTRY
    This document contains code for implementing binary search tree operations like insertion, deletion and traversal. It includes functions for inserting a node, deleting a node, finding the minimum value node and traversing the tree using inorder. The main function tests these operations by building a sample tree with 7 nodes and performing various deletion operations and traversals.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Pes2ug20cs282 - Rohit V Shastry - Sec E - Week 8

    Uploaded by

    ROHIT V SHASTRY
    28 views12 pages
    This document contains code for implementing binary search tree operations like insertion, deletion and traversal. It includes functions for inserting a node, deleting a node, finding the minimum value node and traversing the tree using inorder. The main function tests these operations by building a sample tree with 7 nodes and performing various deletion operations and traversals.

    Original Title

    Pes2ug20cs282_rohit v Shastry_sec E_week 8

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains code for implementing binary search tree operations like insertion, deletion and traversal. It includes functions for inserting a node, deleting a node, finding the minimum value node and traversing the tree using inorder. The main function tests these operations by building a sample tree with 7 nodes and performing various deletion operations and traversals.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    28 views12 pages

    Pes2ug20cs282 - Rohit V Shastry - Sec E - Week 8

    Uploaded by

    ROHIT V SHASTRY
    This document contains code for implementing binary search tree operations like insertion, deletion and traversal. It includes functions for inserting a node, deleting a node, finding the minimum value node and traversing the tree using inorder. The main function tests these operations by building a sample tree with 7 nodes and performing various deletion operations and traversals.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 12

    DSA LAB WEEK 8

    NAME: ROHIT V SHASTRY SRN: PES2UG20CS282


    SECTION: E SECTION WEEK 8

    code
    #include <stdio.h>
    #include <stdlib.h>
    struct node {
    int key;
    struct node *left, *right;
    };
    struct node* newNode(int item)
    {
    struct node* temp
    = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
    }
    void inorder(struct node* root)
    {
    if (root != NULL) {
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
    }
    }
    struct node* insert(struct node* node, int key)
    {
    if (node == NULL)
    return newNode(key);
    if (key < node->key)
    node->left = insert(node->left, key);
    else
    node->right = insert(node->right, key);
    return node;
    }
    struct node* minValueNode(struct node* node)
    {
    struct node* current = node;

    while (current && current->left != NULL)


    current = current->left;
    return current;
    }
    struct node* deleteNode(struct node* root, int key)
    {
    if (root == NULL)
    return root;
    if (key < root->key)
    root->left = deleteNode(root->left, key);
    else if (key > root->key)
    root->right = deleteNode(root->right, key);
    else {
    // node with only one child or no child
    if (root->left == NULL) {
    struct node* temp = root->right;
    free(root);
    return temp;
    }
    else if (root->right == NULL) {
    struct node* temp = root->left;
    free(root);
    return temp;
    }

    struct node* temp = minValueNode(root->right);

    root->key = temp->key;

    root->right = deleteNode(root->right, temp->key);


    }
    return root;
    }
    int main()
    {
    int a,b,c,d,e,f,g,x,y,z;
    struct node* root = NULL;
    printf("Enter the root node\n");
    scanf("%d",&a);
    printf("Enter the node\n");
    scanf("%d",&b);
    printf("Enter the node\n");
    scanf("%d",&c);
    printf("Enter the node\n");
    scanf("%d",&d);
    printf("Enter the node\n");
    scanf("%d",&e);
    printf("Enter the node\n");
    scanf("%d",&f);
    printf("Enter the node\n");
    scanf("%d",&g);
    root = insert(root, a);
    root = insert(root, b);
    root = insert(root, c);
    root = insert(root, d);
    root = insert(root, e);
    root = insert(root, f);
    root = insert(root, g);
    printf("Inorder traversal of the given tree \n");
    inorder(root);
    printf("\nEnter to delete root node \n");
    scanf("%d",&x);
    root = deleteNode(root, x);
    printf("after deleting \n");
    inorder(root);
    printf("\nEnter to delete subtree node \n");
    scanf("%d",&y);
    root = deleteNode(root, y);
    printf("after deleting\n");
    inorder(root);
    printf("\nEnter to delete leaf node \n");
    scanf("%d",&z);
    root = deleteNode(root, z);
    printf("after deleting \n");
    inorder(root);
    return 0;
    }

    OUTPUT:

    Program 2a
    #include<stdio.h>
    #include<conio.h>
    #include<string.h>
    #include<malloc.h>
    struct node {
    struct node *right,*left,*prev;
    char data;
    }*cur,*par,*root=NULL;
    void preorder(struct node *);
    void postorder(struct node *);
    void inorder(struct node *);
    int eval(struct node* root)
    {

    if (!root)
    return 0;
    int l_val = eval(root
    ->left);

    int r_val = eval(root


    ->right);

    if ((root
    ->data)=='+')
    return l_val+r_val;

    if (root
    ->data=='
    -')
    return l_val
    -r_val;

    if (root
    ->data=='*')
    return l_val*r_val;
    return l_val/r_val;
    }
    int main()
    {
    char a[100];
    int len,i;
    struct node *new_node;
    printf("Enter Postfix Expression\n");
    gets(a);
    len=strlen(a);
    for(i=len-1 ; i>=0 ; i--)
    {
    new_node=(struct node *)malloc(sizeof(struct node));
    new_node->data=a[i];
    new_node->left=new_node->right=new_node->prev=NULL;
    if(root==NULL)
    {
    root=new_node;
    cur=par=root;
    }
    else
    {
    if(a[i]=='+' ||a[i]=='-' ||a[i]=='*'||a[i]=='/')
    {
    if(par->right==NULL)
    {
    cur=new_node;
    par->right=cur;
    cur->prev=par;
    par=cur;
    }
    else if(par->left==NULL)
    {
    cur=new_node;
    par->left=cur;
    cur->prev=par;
    par=cur;
    }
    else

    {
    while(par
    ->left!=NULL)

    {
    par=par
    ->prev;

    }
    cur=new_node;
    par
    ->left=cur;
    cur
    ->prev=par;
    par=cur;

    }
    }
    else

    {
    if(par
    ->right==NULL)

    {
    cur=new_node;
    par
    ->right=cur;
    cur
    ->prev=par;

    }
    else if(par
    ->left==NULL)

    {
    cur=new_node;
    par
    ->left=cur;
    cur
    ->prev=par;

    }
    else

    {
    while(par
    ->left!=NULL)

    {
    par=par
    ->prev;

    }
    cur=new_node;
    par
    ->left=cur;
    cur
    ->prev=par;

    }}
    printf("
    \nInorder Traversal:
    \n");
    inorder(root);
    printf("
    \
    n
    \nPreorder Traversal:
    \n");
    preorder(root);
    printf("
    \
    n
    \nPostorder Traversal:
    \n");
    postorder(root);
    printf("
    \n value is :
    -10");
    eval(root);
    return 0;
    getch(); }
    void inorder(struct node *root) {
    if(root!=NULL) {
    inorder(root
    ->left);
    printf("%c
    \t",root
    ->data);
    inorder(root
    ->right);
    }}
    void preorder(struct node *root) {
    if(root!=NULL) {
    printf("%c
    \t",root
    ->data);
    preorder(root
    ->left);
    preorder(root
    ->right);
    }}
    void postorder(struct node *root) {
    if(root!=NULL) {
    postorder(root->left);
    postorder(root->right);
    printf("%c\t",root->data);
    }
    }

    Output:

    You might also like