C Program to Convert Binary Tree to Circular Doubly Linked List

This C Program takes an ordered binary tree & rearranges the internal pointers to make a circular doubly linked list.

Here is a source code of the C program to transform an ordered binary tree & rearranges the internal pointers to make a circular doubly linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program that takes an Ordered Binary tree & Rearranges the 
  3.  * Internal Pointers to make a Circular Doubly Linked List out 
  4.  * of the Tree Nodes 
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. struct node
  10. {
  11.     int num;
  12.     struct node *left;
  13.     struct node *right;
  14.     int used;
  15. };
  16.  
  17. void create(struct node **);
  18. void release(struct node **);
  19. void display(struct node *, int);
  20. struct node * transformdet(struct node *);
  21. struct node * transform(struct node *);
  22.  
  23. int main()
  24. {
  25.     struct node *root = NULL, *head;
  26.  
  27.     printf("Creating binary tree:\n");
  28.     create (&root);
  29.     printf("Displaying binary tree:\n");
  30.     display(root, 0);
  31.     head = transform(root);
  32.     printf("\nDisplaying circular linked list:\n");
  33.     display(head, 1);
  34.     root->left->right = NULL;
  35.     release(&root);
  36.  
  37.     return 0;
  38. }
  39.  
  40. struct node * transformdet(struct node *root)
  41. {
  42.     struct node *left, *right;
  43.  
  44.     if (root == NULL)
  45.     {
  46.         return root;
  47.     }
  48.     if (root->left != NULL)
  49.     {
  50.         left = transformdet(root->left);
  51.         while (left->right != NULL)
  52.         {
  53.             left = left->right;
  54.         }
  55.         left->right = root;
  56.         root->left = left;
  57.     }
  58.     if (root->right != NULL)
  59.     {
  60.         right = transformdet(root->right);
  61.         while (right->left != NULL)
  62.         {
  63.             right = right->left;
  64.         }
  65.         right->left = root;
  66.         root->right = right;
  67.     }
  68.  
  69.     return root;
  70. }
  71.  
  72. struct node * transform(struct node *root)
  73. {
  74.     struct node *rear;
  75.     if (root == NULL)
  76.     {
  77.         return root;
  78.     }
  79.     root = transformdet(root);
  80.     rear = root;
  81.     while (root->left != NULL)
  82.     {
  83.         root = root->left;
  84.     }
  85.     while (rear->right != NULL)
  86.     {
  87.         rear = rear->right;
  88.     }
  89.     root->left = rear;
  90.     rear->right = root;
  91.  
  92.     return (root);
  93. }
  94.  
  95. void create(struct node **root)
  96. {
  97.     struct node *temp, *p, *q;
  98.     int a, ch;
  99.  
  100.     do
  101.     {
  102.         p = *root;
  103.         printf("Enter a number in the tree: ");
  104.         scanf("%d", &a);
  105.         temp = (struct node *)malloc(sizeof(struct node));
  106.         temp->num = a;
  107.         temp->used = 0;
  108.         temp->left = temp->right = NULL;
  109.         if (*root == NULL)
  110.         {
  111.             *root = temp;
  112.         }
  113.         else
  114.         {
  115.             while (p != NULL)
  116.             {
  117.                 q = p;
  118.                 if (p->num >= temp->num)
  119.                 {
  120.                     p = p->right;
  121.                 }
  122.                 else
  123.                 {
  124.                     p = p->left;
  125.                 }
  126.             }
  127.             if (q->num >= temp->num)
  128.             {
  129.                 q->right = temp;
  130.             }
  131.             else
  132.             {
  133.                 q->left = temp;
  134.             }
  135.         }
  136.         printf("Do you want to add more numbers? [1/0]\n");
  137.         scanf("%d", &ch);
  138.     } while (ch != 0);
  139. }
  140.  
  141. void display(struct node *root, int n)
  142. {
  143.     struct node *temp;
  144.  
  145.     if (root != NULL && !n)
  146.     {
  147.         display(root->left, 0);
  148.         printf("%d   ", root->num);
  149.         display(root->right, 0);
  150.     }
  151.     else if (root != NULL && n)
  152.     {
  153.         temp = root;
  154.         printf("%d   ", temp->num);
  155.         temp = temp->right;
  156.         while (temp != root)
  157.         {
  158.             printf("%d   ", temp->num);
  159.             temp = temp->right;
  160.         }
  161.         printf("\n");
  162.     }
  163. }
  164.  
  165. void release(struct node **root)
  166. {
  167.     if (*root != NULL)
  168.     {
  169.         release(&(*root)->right);
  170.         free(*root);
  171.     }
  172. }

$ gcc treetocircular.c 
$ ./a.out
Creating binary tree:
Enter a number in the tree: 5
Do you want to add more numbers? [1/0]
1
Enter a number in the tree: 3
Do you want to add more numbers? [1/0]
1
Enter a number in the tree: 4
Do you want to add more numbers? [1/0]
1
Enter a number in the tree: 2
Do you want to add more numbers? [1/0]
1
Enter a number in the tree: 7
Do you want to add more numbers? [1/0]
1
Enter a number in the tree: 6
Do you want to add more numbers? [1/0]
1
Enter a number in the tree: 8
Do you want to add more numbers? [1/0]
0
Displaying binary tree:
8   7   6   5   4   3   2  
Displaying circular linked list:
8   7   6   5   4   3   2

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.