Binary Search Tree using C Programming - BunksAllowed

BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

  • Home
    • demo-image
    Home Data Structures Technology Binary Search Tree using C Programming

    Binary Search Tree using C Programming

    Share This

    An important application of binary tree is their use in searching. Let us assume that each node in the tree is assigned a key value. In our examples, we will assume for simplicity that these are integers, although arbitrarily complex keys are allowed. We will also assume that all the keys are distinct, and deal with duplicates later.


    The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the keys in the left subtree are smaller than the key value in X, and the values of all the keys in the right subtree are larger than the key value in X.


    Notice that this implies that all the elements in the tree can be ordered in some consistent manner.


    Insertion can be done in Binary Search Tree as follows:

    Step 1:Strat from the root node.
    Step 2:If the data to be inserted is x, compare it with the root value.
    Step 2.1:If they are equal then just stop.
    Step 2.2:If the data to be inserted is less than the root value then choose the left sub-tree.
    Step 2.3If the data to be inserted is greater than the root value then choose the right sub-tree.
    Step 3:Repeat step 2 until the value is properly positioned.

    The above mechanism is clearly shown in the following Fig 1.


    bst_insert1
    bst_insert2
    when we delete a node from Binary Search Tree then the deleted node may fall in either of the three cases.
    Case 1:Deleted node has no child.
    Case 2:Deleted node has exactly one child.
    Case 3:Deleted node has Two children.

    In case 1 we simply delete the node but in case 2 we replace the node with its child. In case 3 the deleted node is replaced by the in-order successor of the node. All three cases has been shown in the following Figure.

    bst_deletion
    Source code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct Node
    {
    int key;
    struct Node *left;
    struct Node *right;
    } node;
    node *newNode(int item)
    {
    node *temp = (node *)malloc(sizeof(node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
    }
    void inorder(node *root)
    {
    if (root != NULL)
    {
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
    }
    }
    void preorder(node *root)
    {
    if (root != NULL)
    {
    printf("%d ", root->key);
    preorder(root->left);
    preorder(root->right);
    }
    }
    void postorder(node *root)
    {
    if (root != NULL)
    {
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->key);
    }
    }
    node* insert(node* nd, int key)
    {
    if (nd == NULL)
    return newNode(key);
    if (key < nd->key)
    nd->left = insert(nd->left, key);
    else
    nd->right = insert(nd->right, key);
    return nd;
    }
    node * minValueNode(node* nd)
    {
    node* current = nd;
    while (current->left != NULL)
    current = current->left;
    return current;
    }
    node* delete(node* root, int key)
    {
    if (root == NULL)
    {
    printf("The tree is empty!");
    return root;
    }
    if (key < root->key)
    root->left = delete(root->left, key);
    else if (key > root->key)
    root->right = delete(root->right, key);
    else
    {
    if (root->left == NULL)
    {
    node *temp = root->right;
    free(root);
    return temp;
    }
    else if (root->right == NULL)
    {
    node *temp = root->left;
    free(root);
    return temp;
    }
    node* temp = minValueNode(root->right);
    root->key = temp->key;
    root->right = delete(root->right, temp->key);
    }
    return root;
    }
    int main()
    {
    node *root=NULL;
    int ch, value;
    while(1)
    {
    printf("\nChoices are as follows:");
    printf("\n1:Insert a node");
    printf("\n2:Traversal");
    printf("\n3:Delete a node");
    printf("\n4:Exit");
    printf("\nEnter your choice:");
    scanf("%d",&ch);
    switch(ch)
    {
    case 1: printf("\nEnter a value to insertion:");
    scanf("%d",&value);
    root = insert(root,value);
    break;
    case 2: inorder(root);
    printf("\n");
    preorder(root);
    printf("\n");
    postorder(root);
    printf("\n");
    break;
    case 3: printf("\nEnter a value for deletion:");
    scanf("%d",&value);
    root = delete(root,value);
    break;
    case 4: return 0;
    }
    }
    return 0;
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

    Happy Exploring!

    Tags
    Share This
    bunksAllowed

    About BunksAllowed

    By on
    Labels: ,
    Subscribe to: Post Comments (Atom)
    Comment Using!!

    No comments:

    Post a Comment

    Note: Only a member of this blog may post a comment.

    About BunksAllowed