C Program to Implement Threaded Binary Tree

«
»
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.

  1. # include <stdio.h>
  2. # include <malloc.h>
  3. #define infinity 9999
  4.  
  5. typedef enum {
  6.     thread, link
  7. } boolean;
  8. struct node *in_succ(struct node *p);
  9. struct node *in_pred(struct node *p);
  10.  
  11. struct node {
  12.     struct node *left_ptr;
  13.     boolean left;
  14.     int info;
  15.     boolean right;
  16.     struct node *right_ptr;
  17. }*head = NULL;
  18.  
  19. int main() {
  20.     int choice, num;
  21.     insert_head();
  22.     while (1) {
  23.         printf("\n");
  24.         printf("1.Insert\n");
  25.         printf("2.Inorder Traversal\n");
  26.         printf("3.Quit\n");
  27.         printf("Enter your choice : ");
  28.         scanf("%d", &choice);
  29.  
  30.         switch (choice) {
  31.         case 1:
  32.             printf("Enter the number to be inserted : ");
  33.             scanf("%d", &num);
  34.             insert(num);
  35.             break;
  36.         case 2:
  37.             inorder();
  38.             break;
  39.         case 3:
  40.             exit(0);
  41.         default:
  42.             printf("Wrong choice\n");
  43.         }/*End of switch */
  44.     }/*End of while */
  45. }/*End of main()*/
  46.  
  47. int insert_head() {
  48.     struct node *tmp;
  49.     head = (struct node *) malloc(sizeof(struct node));
  50.     head->info = infinity;
  51.     head->left = thread;
  52.     head->left_ptr = head;
  53.     head->right = link;
  54.     head->right_ptr = head;
  55. }/*End of insert_head()*/
  56.  
  57. int find(int item, struct node **par, struct node **loc) {
  58.     struct node *ptr, *ptrsave;
  59.     if (head->left_ptr == head) /* If tree is empty*/
  60.     {
  61.         *loc = NULL;
  62.         *par = head;
  63.         return;
  64.     }
  65.     if (item == head->left_ptr->info) /* item is at head->left_ptr */
  66.     {
  67.         *loc = head->left_ptr;
  68.         *par = head;
  69.         return;
  70.     }
  71.     ptr = head->left_ptr;
  72.     while (ptr != head) {
  73.         ptrsave = ptr;
  74.         if (item < ptr->info) {
  75.             if (ptr->left == link)
  76.                 ptr = ptr->left_ptr;
  77.             else
  78.                 break;
  79.         } else if (item > ptr->info) {
  80.             if (ptr->right == link)
  81.                 ptr = ptr->right_ptr;
  82.             else
  83.                 break;
  84.         }
  85.         if (item == ptr->info) {
  86.             *loc = ptr;
  87.             *par = ptrsave;
  88.             return;
  89.         }
  90.     }/*End of while*/
  91.     *loc = NULL; /*item not found*/
  92.     *par = ptrsave;
  93. }/*End of find()*/
  94.  
  95. /* Creating threaded binary search tree */
  96.  
  97. int insert(int item) {
  98.     struct node *tmp, *parent, *location;
  99.     find(item, &parent, &location);
  100.  
  101.     if (location != NULL) {
  102.         printf("Item already present");
  103.         return;
  104.     }
  105.  
  106.     tmp = (struct node *) malloc(sizeof(struct node));
  107.     tmp->info = item;
  108.     tmp->left = thread;
  109.     tmp->right = thread;
  110.  
  111.     if (parent == head) /*tree is empty*/
  112.     {
  113.         head->left = link;
  114.         head->left_ptr = tmp;
  115.         tmp->left_ptr = head;
  116.         tmp->right_ptr = head;
  117.     } else if (item < parent->info) {
  118.         tmp->left_ptr = parent->left_ptr;
  119.         tmp->right_ptr = parent;
  120.         parent->left = link;
  121.         parent->left_ptr = tmp;
  122.     } else {
  123.         tmp->left_ptr = parent;
  124.         tmp->right_ptr = parent->right_ptr;
  125.         parent->right = link;
  126.         parent->right_ptr = tmp;
  127.     }
  128. }/*End of insert()*/
  129.  
  130. /* Finding succeeder */
  131.  
  132. struct node *in_succ(struct node *ptr) {
  133.     struct node *succ;
  134.     if (ptr->right == thread)
  135.         succ = ptr->right_ptr;
  136.     else {
  137.         ptr = ptr->right_ptr;
  138.         while (ptr->left == link)
  139.             ptr = ptr->left_ptr;
  140.         succ = ptr;
  141.     }
  142.     return succ;
  143. }/*End of in_succ()*/
  144.  
  145. /* Finding predecessor */
  146.  
  147. struct node *in_pred(struct node *ptr) {
  148.     struct node *pred;
  149.     if (ptr->left == thread)
  150.         pred = ptr->left_ptr;
  151.     else {
  152.         ptr = ptr->left_ptr;
  153.         while (ptr->right == link)
  154.             ptr = ptr->right_ptr;
  155.         pred = ptr;
  156.     }
  157.     return pred;
  158. }/*End of in_pred()*/
  159.  
  160. /* Displaying all nodes */
  161.  
  162. inorder() {
  163.     struct node *ptr;
  164.     if (head->left_ptr == head) {
  165.         printf("Tree is empty");
  166.         return;
  167.     }
  168.  
  169.     ptr = head->left_ptr;
  170.  
  171.     /*Find the leftmost node and traverse it */
  172.  
  173.     while (ptr->left == link)
  174.         ptr = ptr->left_ptr;
  175.     printf("%d ", ptr->info);
  176.  
  177.     while (1) {
  178.         ptr = in_succ(ptr);
  179.         if (ptr == head) /*If last node reached */
  180.             break;
  181.         printf("%d  ", ptr->info);
  182.     } /*End of while*/
  183. }/*End of inorder()*/

Output:

advertisement
$ 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.

advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.