C Program to Convert Binary Tree to Singly Linked List

This C Program converts a binary tree into a singly linked list by Breadth first search algorithm. We use this algorithm for traversing level by level

Here is a source code of the C program that converts a binary tree into a singly 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 to Convert a Binary Tree into a Singly Linked List by Traversing Level by Level 
  3.  */
  4. <pre>
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7.  
  8. /*structure type to create a tree*/
  9. struct node
  10. {
  11.     int num;
  12.     struct node *left;
  13.     struct node *right;
  14. };
  15. /*
  16.  * structure type to point to the nodes of a tree
  17.  * and also create self-referential list used for
  18.  * queueing.
  19.  */
  20. struct queue
  21. {
  22.     struct node *nodeptr;
  23.     struct queue *next;
  24. };
  25. /* resulting singly linked list */
  26. struct list
  27. {
  28.     int num;
  29.     struct list *next;
  30. };
  31.  
  32. void createTree(struct node **);
  33. void createlistbfs(struct node *, struct list **);
  34. void delete(struct node **);
  35. void display(struct list *);
  36. void deleteList(struct list **);
  37.  
  38. int main()
  39. {
  40.     struct node *root = NULL;
  41.     struct list *head = NULL;
  42.  
  43.     createTree(&root);
  44.     createlistbfs(root, &head);
  45.     printf("Displaying the list generated at node by node level of the tree: ");
  46.     display(head);
  47.     deleteList(&head);
  48.     delete(&root);
  49.  
  50.     return 0;
  51. }
  52.  
  53. void createTree(struct node **root)
  54. {
  55.     struct node *temp, *p, *q;
  56.     int a, ch;
  57.  
  58.     do
  59.     {
  60.         printf("Enter a number for a node: ");
  61.         scanf("%d", &a);
  62.         temp = (struct node *)malloc(sizeof(struct node));
  63.         temp->num = a;
  64.         temp->left = NULL;
  65.         temp->right = NULL;
  66.         p = q = *root;
  67.         if (*root == NULL)
  68.         {
  69.             *root = temp;
  70.         }
  71.         else
  72.         {
  73.             while (1)
  74.             {
  75.                 q = p;
  76.                 if (p->num >= temp->num)
  77.                 {
  78.                     p = p->left;
  79.                 }
  80.                 else
  81.                 {
  82.                     p = p->right;
  83.                 }
  84.                 if (p == NULL)
  85.                 {
  86.                     break;
  87.                 }
  88.             }
  89.             if (q->num >= temp->num)
  90.                 q->left = temp;
  91.             else
  92.                  q->right = temp;
  93.         }
  94.         printf("Do you want to continue? [1/0]: ");
  95.         scanf("%d", &ch);
  96.     } while (ch != 0);
  97. }
  98.  
  99. void createlistbfs(struct node *root, struct list **head)
  100. {
  101.     struct queue *qhead, *qrear, *qtemp, *qrelease;
  102.     struct list *temp, *rear;
  103.  
  104.     if (root == NULL)
  105.     {
  106.         return;
  107.     }
  108.     qhead = (struct queue *)malloc(sizeof(struct queue));
  109.     qhead->nodeptr = root;
  110.     qhead->next = NULL;
  111.     qrear = qhead;
  112.     while (qhead != NULL)
  113.     {
  114.  
  115.         temp = (struct list *)malloc(sizeof(struct list));
  116.         temp->num = qhead->nodeptr->num;
  117.         temp->next = NULL;
  118.         if (*head == NULL)
  119.         {
  120.             *head = temp;
  121.         }
  122.         else
  123.         {
  124.             rear->next = temp;
  125.         }
  126.         rear = temp;
  127.         if (qhead->nodeptr->left != NULL)
  128.         {
  129.             qtemp = (struct queue *)malloc(sizeof(struct queue));
  130.             qtemp->nodeptr = qhead->nodeptr->left;
  131.             qtemp->next = NULL;
  132.             qrear->next = qtemp;
  133.             qrear = qtemp;
  134.         }
  135.         if (qhead->nodeptr->right != NULL)
  136.         {
  137.             qtemp = (struct queue *)malloc(sizeof(struct queue));
  138.             qtemp->nodeptr = qhead->nodeptr->right;
  139.             qtemp->next = NULL;
  140.             qrear->next = qtemp;
  141.             qrear = qtemp;
  142.         }
  143.         qrelease = qhead;
  144.         qhead = qhead->next;
  145.         free(qrelease);
  146.     }
  147. }
  148.  
  149. void delete(struct node **root)
  150. {
  151.     if (*root == NULL)
  152.     {
  153.         return;
  154.     }
  155.     else
  156.     {
  157.         if ((*root)->left != NULL)
  158.         {
  159.             delete(&((*root)->left));
  160.         }
  161.         if ((*root)->right != NULL)
  162.         {
  163.             delete(&((*root)->right));
  164.         }
  165.     }
  166. }
  167.  
  168. void display(struct list *head)
  169. {
  170.     while (head != NULL)
  171.     {
  172.         printf("%d  ", head->num);
  173.         head = head->next;
  174.     }
  175. }
  176.  
  177. void deleteList(struct list **head)
  178. {
  179.     struct list *temp;
  180.  
  181.     temp = *head;
  182.     while (temp != NULL)
  183.     {
  184.         *head = (*head)->next;
  185.         free(temp);
  186.         temp = *head;
  187.     }
  188. }

$ gcc treetolistbfs.c 
$ ./a.out
Enter a number for a node: 4
Do you want to continue? [1/0]: 1
Enter a number for a node: 2
Do you want to continue? [1/0]: 1
Enter a number for a node: 3
Do you want to continue? [1/0]: 1
Enter a number for a node: 1
Do you want to continue? [1/0]: 1
Enter a number for a node: 6
Do you want to continue? [1/0]: 1
Enter a number for a node: 5
Do you want to continue? [1/0]: 1
Enter a number for a node: 8
Do you want to continue? [1/0]: 1
Enter a number for a node: 7
Do you want to continue? [1/0]: 1
Enter a number for a node: 9
Do you want to continue? [1/0]: 0
Displaying the list generated at node by node level of the tree: 4  2  6  1  3  5  8  7  9

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.