C Program that takes an Ordered Binary tree & Rearranges the Internal Pointers to make a Circular Doubly Linked List out of the Tree Nodes

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

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

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

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

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn