Threaded Binary Tree - 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 Threaded Binary Tree

    Threaded Binary Tree

    Share This

    In the case of the linked representation of a binary tree we find that half of the entries in the pointers fields LEFT and RIGHT will contain null entries. This space may be efficiently used by replacing the null entries with special pointers called Threads which point to the nodes higher in trees. Such trees are called Threaded trees.


    Threads in a binary tree must be distinguished from normal pointers. There are many ways to thread a binary tree.


    1. The right NULL pointer of each node can be replaced by a thread to the successor of that node under in-order traversal called a right thread and the tree is called a right-threaded tree.


    2. The left NULL pointer of each node can be replaced by a thread to the predecessor of that node under in order traversal called a left thread and the tree will call a left threaded tree.


    3. Both left and right NULL pointers can be used to point to the predecessor and successor of that node respectively under in-order traversal. Such a tree is called a fully threaded tree.


    Insertion In Threaded Binary Tree

    First of all, we have to find the location of the new node for insertion. The new node will be inserted as a leaf node so its left and right pointers both will be threads.


    Case 1:When the tree is empty:-When the tree is empty the left pointer of the head node is a thread pointing to itself. We will insert the new node as the left child of the header node so now the left pointer of the head will be a link pointing to the newnode. We know that the left pointer of the first node in in-order traversal and the right pointer of the last node in in-order traversals are threads pointing to the header node. Here we have only one node which is the first and the last node so its left-right pointers will be threads pointing to the header node.


    Case 2:When a new node is inserted as the left child of its parent:- The threads of the new node will point to its in-order predecessor and successor. The node which was the in-order predecessor of the parent is now the in-order predecessor of this node. The in-order successor of this node is its parent.


    Case 3:When a new node is inserted as the right child of its parent:- The node which was the in-order successor of the parent is now the in-order successor of this node. The in-order predecessor of this node is its parent. so the left and right threads of the new node will be: tmp->leftptr=parent;tmp->rightptr=parent->child


    The parent of the new node had a thread in its right pointer pointing to its successor but after insertion, its right pointer will be a link pointing to the new node. parent->right=link;parent->rchild=tmp;


    Let's see the following Figure. where the insertion procedure is clearly described.

    thread_ins1

    Deletion In Threaded Binary Tree

    Case 1:Node to be deleted is the leaf node:-  If the node to be deleted is the root node then the tree will become empty after its deletion so the left pointer of the head will be a thread pointing to itself.


    If the node to be deleted is a left leaf node then the left pointer of the parent will become a thread pointing to its in-order predecessor. Initially, its in-order predecessor was its left child but now its in-order predecessor will be that node which was the predecessor of its left child.


    If the node to be deleted is a right leaf node then the right pointer of the parent will become a thread pointing to its in-order successor. Initially, its in-order successor was its right child but now its in-order successor will be that node which was the successor of its right child.


    Case 2: The node to be deleted has one child:- Delete the node as in the binary search tree. Find the in-order successor and in-order predecessor of the node to be deleted.


    If the node has a right subtree then put the predecessor of the node in the left pointer of its successor.


    If the node has left subtree then put the successor of the node in the right pointer of its predecessor.


    Case 3: The node to be deleted has two children:-First we delete the in-order successor of the node and then replace the deleted node with the in-order successor. For deleting in-order successor we will call either case 1 or case 2.


    Let's see the following Fig 2. where the deletion procedure is clearly described.


    thread_del1

    Fig 2. deletion 10 is replaced by inorder successor 12 in threaded binary tree.


    Insertion And Deletion In Threaded Binary Tree
    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
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    #include <stdio.h>
    #include <stdlib.h>
    enum boolean
    {
    false = 0,
    true = 1
    } ;
    struct thtree
    {
    enum boolean isleft ;
    struct thtree *left ;
    int data ;
    struct thtree *right ;
    enum boolean isright ;
    } ;
    void insert ( struct thtree **, int ) ;
    void delete ( struct thtree **, int ) ;
    void search ( struct thtree **, int, struct thtree **,
    struct thtree **, int * ) ;
    void inorder ( struct thtree * ) ;
    void deltree ( struct thtree ** ) ;
    /* inserts a node in a threaded binary tree */
    void insert ( struct thtree **s, int num )
    {
    struct thtree *p, *z, *head = *s ;
    /* allocating a new node */
    z = malloc ( sizeof ( struct thtree ) ) ;
    z -> isleft = true ; /* indicates a thread */
    z -> data = num ; /* assign new data */
    z -> isright = true ; /* indicates a thread */
    /* if tree is empty */
    if ( *s == NULL )
    {
    head = malloc ( sizeof ( struct thtree ) ) ;
    /* the entire tree is treated as a left sub-tree of the head node */
    head -> isleft = false ;
    head -> left = z ; /* z becomes leftchild of the head node */
    head -> data = -9999 ; /* no data */
    head -> right = head ; /* right link will always be pointing
    to itself */
    head -> isright = false ;
    *s = head ;
    z -> left = head ; /* left thread to head */
    z -> right = head ; /* right thread to head */
    }
    else/* if tree is non-empty */
    {
    p = head -> left ;
    /* traverse till the thread is found attached to the head */
    while ( p != head )
    {
    if ( p -> data > num )
    {
    if ( p -> isleft != true ) /* checking for a thread */
    p = p -> left ;
    else
    {
    z -> left = p -> left ;
    p -> left = z ;
    p -> isleft = false ; /* indicates a link */
    z -> isright = true ;
    z -> right = p ;
    return ;
    }
    }
    else
    {
    if ( p -> data < num )
    {
    if ( p -> isright != true )
    p = p -> right ;
    else
    {
    z -> right = p -> right ;
    p -> right = z ;
    p -> isright = false ; /* indicates a link */
    z -> isleft = true ;
    z -> left = p ;
    return ;
    }
    }
    }
    }
    }
    }
    /* deletes a node from the binary search tree */
    void delete ( struct thtree **root, int num )
    {
    int found ;
    struct thtree *parent, *x, *xsucc ;
    /* if tree is empty */
    if ( *root == NULL )
    {
    printf ( "\nTree is empty" ) ;
    return ;
    }
    parent = x = NULL ;
    /* call to search function to find the node to be deleted */
    search ( root, num, &parent, &x, &found ) ;
    /* if the node to deleted is not found */
    if ( found == false )
    {
    printf ( "\nData to be deleted, not found" ) ;
    return ;
    }
    /* if the node to be deleted has two children */
    if ( x -> isleft == false && x -> isright == false )
    {
    parent = x ;
    xsucc = x -> right ;
    while ( xsucc -> isleft == false )
    {
    parent = xsucc ;
    xsucc = xsucc -> left ;
    }
    x -> data = xsucc -> data ;
    x = xsucc ;
    }
    /* if the node to be deleted has no child */
    if ( x -> isleft == true && x -> isright == true )
    {
    /* if node to be deleted is a root node */
    if ( parent == NULL )
    {
    ( *root ) -> left = *root ;
    ( *root ) -> isleft = true ;
    free ( x ) ;
    return ;
    }
    if ( parent -> right == x )
    {
    parent -> isright = true ;
    parent -> right = x -> right ;
    }
    else
    {
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

    Happy Exploring!

    Tags
    Share This
    bunksAllowed

    About BunksAllowed

    Newer Article B Tree Older Article AVL Tree and Balancing
    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