Threaded Binary Tree in C

This is a C Program to implement threaded binary search tree. A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists) , and all left child pointers that would normally be null point to the inorder predecessor of the node.

Here is source code of the C Program to Implement Threaded Binary Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
# include <stdio.h>
```
```
# include <malloc.h>
```
```
#define infinity 9999
```
```
 
```
```
typedef enum {
```
```
    thread, link
```
```
} boolean;
```
```
struct node *in_succ(struct node *p);
```
```
struct node *in_pred(struct node *p);
```
```
 
```
```
struct node {
```
```
    struct node *left_ptr;
```
```
    boolean left;
```
```
    int info;
```
```
    boolean right;
```
```
    struct node *right_ptr;
```
```
}*head = NULL;
```
```
 
```
```
int main() {
```
```
    int choice, num;
```
```
    insert_head();
```
```
    while (1) {
```
```
        printf("\n");
```
```
        printf("1.Insert\n");
```

        printf("2.Inorder Traversal\n");

```
        printf("3.Quit\n");
```
```
        printf("Enter your choice : ");
```
```
        scanf("%d", &choice);
```
```
 
```
```
        switch (choice) {
```
```
        case 1:
```

            printf("Enter the number to be inserted : ");

```
            scanf("%d", &num);
```
```
            insert(num);
```
```
            break;
```
```
        case 2:
```
```
            inorder();
```
```
            break;
```
```
        case 3:
```
```
            exit(0);
```
```
        default:
```
```
            printf("Wrong choice\n");
```
```
        }/*End of switch */
```
```
    }/*End of while */
```
```
}/*End of main()*/
```
```
 
```
```
int insert_head() {
```
```
    struct node *tmp;
```

    head = (struct node *) malloc(sizeof(struct node));

```
    head->info = infinity;
```
```
    head->left = thread;
```
```
    head->left_ptr = head;
```
```
    head->right = link;
```
```
    head->right_ptr = head;
```
```
}/*End of insert_head()*/
```
```
 
```

int find(int item, struct node **par, struct node **loc) {

```
    struct node *ptr, *ptrsave;
```

    if (head->left_ptr == head) /* If tree is empty*/

```
    {
```
```
        *loc = NULL;
```
```
        *par = head;
```
```
        return;
```
```
    }
```

    if (item == head->left_ptr->info) /* item is at head->left_ptr */

```
    {
```
```
        *loc = head->left_ptr;
```
```
        *par = head;
```
```
        return;
```
```
    }
```
```
    ptr = head->left_ptr;
```
```
    while (ptr != head) {
```
```
        ptrsave = ptr;
```
```
        if (item < ptr->info) {
```
```
            if (ptr->left == link)
```
```
                ptr = ptr->left_ptr;
```
```
            else
```
```
                break;
```
```
        } else if (item > ptr->info) {
```
```
            if (ptr->right == link)
```
```
                ptr = ptr->right_ptr;
```
```
            else
```
```
                break;
```
```
        }
```
```
        if (item == ptr->info) {
```
```
            *loc = ptr;
```
```
            *par = ptrsave;
```
```
            return;
```
```
        }
```
```
    }/*End of while*/
```
```
    *loc = NULL; /*item not found*/
```
```
    *par = ptrsave;
```
```
}/*End of find()*/
```
```
 
```

/* Creating threaded binary search tree */

```
 
```
```
int insert(int item) {
```

    struct node *tmp, *parent, *location;

```
    find(item, &parent, &location);
```
```
 
```
```
    if (location != NULL) {
```
```
        printf("Item already present");
```
```
        return;
```
```
    }
```
```
 
```

    tmp = (struct node *) malloc(sizeof(struct node));

```
    tmp->info = item;
```
```
    tmp->left = thread;
```
```
    tmp->right = thread;
```
```
 
```

    if (parent == head) /*tree is empty*/

```
    {
```
```
        head->left = link;
```
```
        head->left_ptr = tmp;
```
```
        tmp->left_ptr = head;
```
```
        tmp->right_ptr = head;
```
```
    } else if (item < parent->info) {
```

        tmp->left_ptr = parent->left_ptr;

```
        tmp->right_ptr = parent;
```
```
        parent->left = link;
```
```
        parent->left_ptr = tmp;
```
```
    } else {
```
```
        tmp->left_ptr = parent;
```

        tmp->right_ptr = parent->right_ptr;

```
        parent->right = link;
```
```
        parent->right_ptr = tmp;
```
```
    }
```
```
}/*End of insert()*/
```
```
 
```
```
/* Finding succeeder */
```
```
 
```

struct node *in_succ(struct node *ptr) {

```
    struct node *succ;
```
```
    if (ptr->right == thread)
```
```
        succ = ptr->right_ptr;
```
```
    else {
```
```
        ptr = ptr->right_ptr;
```
```
        while (ptr->left == link)
```
```
            ptr = ptr->left_ptr;
```
```
        succ = ptr;
```
```
    }
```
```
    return succ;
```
```
}/*End of in_succ()*/
```
```
 
```
```
/* Finding predecessor */
```
```
 
```

struct node *in_pred(struct node *ptr) {

```
    struct node *pred;
```
```
    if (ptr->left == thread)
```
```
        pred = ptr->left_ptr;
```
```
    else {
```
```
        ptr = ptr->left_ptr;
```
```
        while (ptr->right == link)
```
```
            ptr = ptr->right_ptr;
```
```
        pred = ptr;
```
```
    }
```
```
    return pred;
```
```
}/*End of in_pred()*/
```
```
 
```
```
/* Displaying all nodes */
```
```
 
```
```
inorder() {
```
```
    struct node *ptr;
```
```
    if (head->left_ptr == head) {
```
```
        printf("Tree is empty");
```
```
        return;
```
```
    }
```
```
 
```
```
    ptr = head->left_ptr;
```
```
 
```

    /*Find the leftmost node and traverse it */

```
 
```
```
    while (ptr->left == link)
```
```
        ptr = ptr->left_ptr;
```
```
    printf("%d ", ptr->info);
```
```
 
```
```
    while (1) {
```
```
        ptr = in_succ(ptr);
```

        if (ptr == head) /*If last node reached */

```
            break;
```
```
        printf("%d  ", ptr->info);
```
```
    } /*End of while*/
```
```
}/*End of inorder()*/
```

Output:

$ gcc ThreadedBST.c
$ ./a.out
 
1.Insert
2.Inorder Traversal
3.Quit
Enter your choice : 1
Enter the number to be inserted: 12
 
1.Insert
2.Inorder Traversal
3.Quit
Enter your choice : 1
Enter the number to be inserted: 5
 
1.Insert
2.Inorder Traversal
3.Quit
Enter your choice : 1
Enter the number to be inserted: 88
 
1.Insert
2.Inorder Traversal
3.Quit
Enter your choice : 2
5 12 88
 
1.Insert
2.Inorder Traversal
3.Quit
Enter your choice : 3

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Find the Height of Tree using Recursion

» Next - C Program to Check if Binary Tree is Subtree of Another Tree

Next Steps: