This blog is under construction

Friday 3 May 2013

C Program To Perform Insertion, Deletion & Traversal In Threaded Binary Search Tree

  • The left and right child pointers in binary search tree are NULL.
  • But in threaded binary search tree, left child pointer will point to the predecessor and the right child will point to the successor of the current node.
  • For traversal in Binary search tree, we need to keep track of list of the nodes present above the current node.  It leads to additional usage of space and time.  But, this could be avoided by using Threaded Binary Search Tree.

Example for Threaded Binary Search Tree:




 See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs


 Example Program For Insertion, Deletion & Traversal In Threaded BST(in C):


  #include <stdio.h>
  #include <stdlib.h>

   enum marker {
        CHILD,
        THREAD
  };

   struct tbstNode {
        int data;
        struct tbstNode *link[2];
        int marker[2];
  };

   struct tbstNode *root = NULL;

   struct tbstNode * createNode (int data) {
        struct tbstNode *newNode;
        newNode = (struct tbstNode *)malloc(sizeof (struct tbstNode));
        newNode->data = data;
        newNode->link[0] = newNode->link[1] = NULL;
        newNode->marker[0] = newNode->marker[1] = THREAD;
        return newNode;
  }

  void insertion(int data) {
        struct tbstNode *parent, *newNode, *temp;
        int path;

        if (!root) {
                root = createNode(data);
                return;
        }

        parent = root;
        /* find the location to insert the new node */
        while (1) {
                if (data == parent->data) {
                        printf("Duplicates Not Allowed\n");
                        return;
                }
                path = (data > parent->data) ? 1 : 0;
                if (parent->marker[path] == THREAD)
                        break;
                else
                        parent = parent->link[path];
        }
        /*
         * newnode's left points to predecessor and
         * right to successor
         */
        newNode = createNode(data);
        newNode->link[path] = parent->link[path];
        parent->marker[path] = CHILD;
        newNode->link[!path] = parent;
        parent->link[path] = newNode;
        return;
  }

  void delete(int data) {
        struct tbstNode *current, *parent, *temp;
        int path;

        parent = root;
        current = root;

        /* search the node to delete */
        while (1) {
                if (data == current->data)
                        break;

                path = (data > current->data) ? 1 : 0;

                if (current->marker[path] == THREAD) {
                        printf("Given data is not available!!\n");
                        return;
                }

                parent = current;
                current = current->link[path];
        }

        if (current->marker[1] == THREAD) {
                if (current->marker[0] == CHILD) {
                        /* node with single child */
                        temp = current->link[0];
                        while (temp->marker[1] == CHILD) {
                                temp = temp->link[1];
                        }
                        temp->link[1] = current->link[1];
                        if (current == root) {
                                root = current->link[0];
                        } else {
                                parent->link[path] = current->link[0];
                        }
                } else {
                        /* deleting leaf node */
                        if (current == root) {
                                root = NULL;
                        } else {
                                parent->link[path] = current->link[path];
                                parent->marker[path] = THREAD;
                        }
                }
        } else {
                temp = current->link[1];
                /*
                 * node with two child - whose right child has
                 * no left child 
                 */
                if (temp->marker[0] == THREAD) {
                        temp->link[0] = current->link[0];
                        temp->marker[0] = current->marker[0];
                        if (temp->marker[0] == CHILD) {
                                struct tbstNode *x = temp->link[0];
                                while (x->marker[1] == CHILD) {
                                        x = x->link[1];
                                }
                                x->link[1] = temp;
                        }

                        if (current == root) {
                                root = temp;
                        } else {
                                printf("path: %d data:%d\n", path, parent->data);
                                parent->link[path] = temp;
                        }

                } else {
                        /* node with two child */
                        struct tbstNode *child;
                        while (1) {
                                child  = temp->link[0];
                                if (child->marker[0] == THREAD)
                                        break;
                                temp = child;
                        }

                        if (child->marker[1] == CHILD)
                                temp->link[0] = child->link[1];
                        else {
                                temp->link[0] = child;
                                temp->marker[0] = THREAD;
                        }

                        child->link[0] = current->link[0];
                        /* update the links */
                        if (current->marker[0] == CHILD) {
                                struct tbstNode *x = current->link[0];
                                while(x->marker[1] == CHILD)
                                        x = x->link[1];
                                x->link[1] = child;
                                child->marker[0] = CHILD;
                        }
                        child->link[1] = current->link[1];
                        child->marker[1] = CHILD;

                        if (current == root)
                                root = child;
                        else
                                parent->link[path] = child;
                }
        }
        /* deallocation */
        free(current);
        return;
  }

  void traversal() {
        struct tbstNode *myNode;
        if (!root) {
                printf("Threaded Binary Tree Not Exists!!\n");
                return;
        }

        myNode = root;
        while (1) {
                while(myNode->marker[0] == CHILD) {
                        myNode = myNode->link[0];
                }
                printf("%d ", myNode->data);
                myNode = myNode->link[1];
                if (myNode) {
                        printf("%d ", myNode->data);
                        myNode = myNode->link[1];
                }
                if (!myNode)
                        break;
        }
        printf("\n");
        return;
  }

  void search(int data) {
        struct tbstNode *myNode;
        int path;

        if (!root) {
                printf("Tree Not Available!!\n");
                return;
        }

        myNode = root;
        while (1) {
                if (myNode->data == data) {
                        printf("Given data present in TBST!!\n");
                        return;
                }

                path = (data > myNode->data) ? 1 : 0;
                if (myNode->marker[path] == THREAD)
                        break;
                else
                        myNode = myNode->link[path];
        }
        printf("Given data is not present in TBST!!\n");
        return;
  }

  int main () {
        int data, ch;
        while (1) {
                printf("1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Traversal\n");
                printf("5. Exit\nEnter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter your input data:");
                                scanf("%d", &data);
                                insertion(data);
                                break;
                        case 2:
                                printf("Enter your input data:");
                                scanf("%d", &data);
                                delete(data);
                                break;
                        case 3:
                                printf("Enter your input data:");
                                scanf("%d", &data);
                                search(data);
                                break;
                        case 4:
                                traversal();
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("You have entered wrong option!!\n");
                                break;
                }
                printf("\n");
        }
  }



  Output(Insertion, Deletion & Traversal In Threaded BST Tree):
  jp@jp-VirtualBox:$ ./a.out
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input data:50

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input data:40

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input data:60

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input data:30

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input data:45

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input data:55

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input data:70

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:4
  30 40 45 50 55 60 70 

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:2
  Enter your input data:50

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:4
  30 40 45 55 60 70 

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:3
  Enter your input data:70
  Given data present in TBST!!

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:5
  


Posted by at 17:58

2 comments:

  1. ThatOneGuy5 October 2015 at 21:26

    what does the while(1) mean in the deletion method

    ReplyDelete
    Replies
    1. Hi Bad7 May 2018 at 10:03

      It means repeat while loop until 1 turns to 0

      Delete

Subscribe to: Post Comments (Atom)