threaded_binary_trees.c

/**
 * @file
 * \brief This file is a simple implementation of a Threaded Binary Tree
 *
 * Threaded Binary Tree is a binary tree variant in which all left child
 * pointers that are NULL (in Linked list representation) point to its
 * in-order predecessor, and all right child pointers that are NULL
 * (in Linked list representation) point to its in-order successor.
 * It has the following functionalities:
 * - Insertion
 * - Search
 * - Deletion
 * - Listing of node keys inorder,preorder,postorder
 *
 * -see binary_search_tree.c
 *
 * \author [Amitha Nayak](https://github.com/amitnayakblr)
 */

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

/**
 * Node, the basic data structure of the tree
 */
typedef struct Node
{
    int data;           /**< stores the number */
    struct Node *llink; /**< link to left child */
    struct Node *rlink; /**< link to right child */
} node;

/**
 * creates a new node
 * param[in] data value to be inserted
 * \returns a pointer to the new node
 */
node *create_node(int data)
{
    node *ptr = (node *)malloc(sizeof(node));
    ptr->rlink = ptr->llink = NULL;
    ptr->data = data;
    return ptr;
}

/**
 * inserts a node into the tree
 * param[in,out] root pointer to node pointer to the topmost node of the tree
 * param[in] data value to be inserted into the tree
 */
void insert_bt(node **root, int data)
{
    node *new_node = create_node(data);
    node *temp;  // to be deleted
    node *prev;  // keeps track of the parent of the element deleted
    if (*root == NULL)
    {
        *root = new_node;
    }
    else
    {
        temp = *root;
        prev = NULL;
        while (temp != NULL)
        {
            if (new_node->data > temp->data)
            {
                prev = temp;
                temp = temp->rlink;
            }
            else if (new_node->data < temp->data)
            {
                prev = temp;
                temp = temp->llink;
            }
            else
            {
                return;
            }
        }

        if (new_node->data > prev->data)
        {
            prev->rlink = new_node;
        }
        else
        {
            prev->llink = new_node;
        }
    }
}

/**
 * searches for the element
 * \param[in] root node pointer to the topmost node of the tree
 * \param[in] ele value searched for
 */
void search(node *root, int ele)
{
    node *temp = root;
    while (temp != NULL)
    {
        if (temp->data == ele)
        {
            break;
        }
        else if (ele > temp->data)
        {
            temp = temp->rlink;
        }
        else
        {
            temp = temp->llink;
        }
    }

    if (temp == NULL)
    {
        printf("%s\n", "Element not found.");
    }
    else
        printf("%s\n", "Element found.");
}

/**
 * performs inorder traversal
 * param[in] curr node pointer to the topmost node of the tree
 */
void inorder_display(node *curr)
{
    if (curr != NULL)
    {
        inorder_display(curr->llink);
        printf("%d\t", curr->data);
        inorder_display(curr->rlink);
    }
}

/**
 * performs postorder traversal
 * param[in] curr node pointer to the topmost node of the tree
 */
void postorder_display(node *curr)
{
    if (curr != NULL)
    {
        postorder_display(curr->llink);
        postorder_display(curr->rlink);
        printf("%d\t", curr->data);
    }
}

/**
 * performs preorder traversal
 * param[in] curr node pointer to the topmost node of the tree
 */
void preorder_display(node *curr)
{
    if (curr != NULL)
    {
        printf("%d\t", curr->data);
        preorder_display(curr->llink);
        preorder_display(curr->rlink);
    }
}

/**
 * deletion of a node from the tree
 * if the node isn't present in the tree, it takes no action.
 * param[in,out] root pointer to node pointer to the topmost node of the tree
 * param[in] ele value to be deleted from the tree
 */
void delete_bt(node **root, int ele)
{
    node *temp;
    node *prev;
    if (*root == NULL)
        return;
    else
    {
        temp = *root;
        prev = NULL;
        // search
        while (temp != NULL)
        {
            if (temp->data == ele)
            {
                break;
            }
            else if (ele > temp->data)
            {
                prev = temp;
                temp = temp->rlink;
            }
            else
            {
                prev = temp;
                temp = temp->llink;
            }
        }
    }

    if (temp == NULL)
        return;
    else
    {
        node *replacement;  // deleted node's replacement
        node *t;
        if (temp->llink == NULL && temp->rlink == NULL)
        {
            replacement = NULL;
        }
        else if (temp->llink == NULL && temp->rlink != NULL)
        {
            replacement = temp->rlink;
        }
        else if (temp->llink != NULL && temp->rlink == NULL)
        {
            replacement = temp->llink;
        }
        else
        {
            replacement = temp->rlink;  // replaced with inorder successor
            t = replacement;
            while (t->llink != NULL)
            {
                t = t->llink;
            }
            t->llink =
                temp->llink;  // leftmost node of the replacement is linked to
                              // the left child of the deleted node
        }

        if (temp == *root)
        {
            free(*root);
            *root = replacement;
        }
        else if (prev->llink == temp)
        {
            free(prev->llink);
            prev->llink = replacement;
        }
        else if (prev->rlink == temp)
        {
            free(prev->rlink);
            prev->rlink = replacement;
        }
    }
}

/**
 * main function
 */
int main()
{
    printf("BINARY THREADED TREE: \n");
    node *root = NULL;
    int choice, n;
    do
    {
        printf("%s\n", "1. Insert into BT");
        printf("%s\n", "2. Print BT - inorder");
        printf("%s\n", "3. Print BT - preorder");
        printf("%s\n", "4. print BT - postorder");
        printf("%s\n", "5. delete from BT");
        printf("%s\n", "6. search in BT");
        printf("%s\n", "Type 0 to exit");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            printf("%s\n", "Enter a no:");
            scanf("%d", &n);
            insert_bt(&root, n);
            break;
        case 2:
            inorder_display(root);
            printf("\n");
            break;
        case 3:
            preorder_display(root);
            printf("\n");
            break;
        case 4:
            postorder_display(root);
            printf("\n");
            break;
        case 5:
            printf("%s\n", "Enter a no:");
            scanf("%d", &n);
            delete_bt(&root, n);
            break;
        case 6:
            printf("%s\n", "Enter a no:");
            scanf("%d", &n);
            search(root, n);
            break;
        }
    } while (choice != 0);
    return 0;
}