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.

```
/*
```

 * C Program that takes an Ordered Binary tree & Rearranges the

 * Internal Pointers to make a Circular Doubly Linked List out

```
 * of the Tree Nodes 
```
```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int num;
```
```
    struct node *left;
```
```
    struct node *right;
```
```
    int used;
```
```
};
```
```
 
```
```
void create(struct node **);
```
```
void release(struct node **);
```
```
void display(struct node *, int);
```

struct node * transformdet(struct node *);

```
struct node * transform(struct node *);
```
```
 
```
```
int main()
```
```
{
```
```
    struct node *root = NULL, *head;
```
```
 
```
```
    printf("Creating binary tree:\n");
```
```
    create (&root);
```

    printf("Displaying binary tree:\n");

```
    display(root, 0);
```
```
    head = transform(root);
```

    printf("\nDisplaying circular linked list:\n");

```
    display(head, 1);
```
```
    root->left->right = NULL;
```
```
    release(&root);
```
```
 
```
```
    return 0;
```
```
}
```
```
 
```

struct node * transformdet(struct node *root)

```
{
```
```
    struct node *left, *right;
```
```
 
```
```
    if (root == NULL)
```
```
    {
```
```
        return root;
```
```
    }
```
```
    if (root->left != NULL)
```
```
    {
```

        left = transformdet(root->left);

```
        while (left->right != NULL)
```
```
        {
```
```
            left = left->right;
```
```
        }
```
```
        left->right = root;
```
```
        root->left = left;
```
```
    }
```
```
    if (root->right != NULL)
```
```
    {
```

        right = transformdet(root->right);

```
        while (right->left != NULL)
```
```
        {
```
```
            right = right->left;
```
```
        }
```
```
        right->left = root;
```
```
        root->right = right;
```
```
    }
```
```
 
```
```
    return root;
```
```
}
```
```
 
```

struct node * transform(struct node *root)

```
{
```
```
    struct node *rear;
```
```
    if (root == NULL)
```
```
    {
```
```
        return root;
```
```
    }
```
```
    root = transformdet(root);
```
```
    rear = root;
```
```
    while (root->left != NULL)
```
```
    {
```
```
        root = root->left;
```
```
    }
```
```
    while (rear->right != NULL)
```
```
    {
```
```
        rear = rear->right;
```
```
    }
```
```
    root->left = rear;
```
```
    rear->right = root;
```
```
 
```
```
    return (root);
```
```
}
```
```
 
```
```
void create(struct node **root)
```
```
{
```
```
    struct node *temp, *p, *q;
```
```
    int a, ch;
```
```
 
```
```
    do
```
```
    {
```
```
        p = *root;
```

        printf("Enter a number in the tree: ");

```
        scanf("%d", &a);
```

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

```
        temp->num = a;
```
```
        temp->used = 0;
```

        temp->left = temp->right = NULL;

```
        if (*root == NULL)
```
```
        {
```
```
            *root = temp;
```
```
        }
```
```
        else
```
```
        {
```
```
            while (p != NULL)
```
```
            {
```
```
                q = p;
```

                if (p->num >= temp->num)

```
                {
```
```
                    p = p->right;
```
```
                }
```
```
                else
```
```
                {
```
```
                    p = p->left;
```
```
                }
```
```
            }
```
```
            if (q->num >= temp->num)
```
```
            {
```
```
                q->right = temp;
```
```
            }
```
```
            else
```
```
            {
```
```
                q->left = temp;
```
```
            }
```
```
        }
```

        printf("Do you want to add more numbers? [1/0]\n");

```
        scanf("%d", &ch);
```
```
    } while (ch != 0);
```
```
}
```
```
 
```
```
void display(struct node *root, int n)
```
```
{
```
```
    struct node *temp;
```
```
 
```
```
    if (root != NULL && !n)
```
```
    {
```
```
        display(root->left, 0);
```
```
        printf("%d   ", root->num);
```
```
        display(root->right, 0);
```
```
    }
```
```
    else if (root != NULL && n)
```
```
    {
```
```
        temp = root;
```
```
        printf("%d   ", temp->num);
```
```
        temp = temp->right;
```
```
        while (temp != root)
```
```
        {
```
```
            printf("%d   ", temp->num);
```
```
            temp = temp->right;
```
```
        }
```
```
        printf("\n");
```
```
    }
```
```
}
```
```
 
```
```
void release(struct node **root)
```
```
{
```
```
    if (*root != NULL)
```
```
    {
```
```
        release(&(*root)->right);
```
```
        free(*root);
```
```
    }
```
```
}
```

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

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.

« Prev - C Program to Search a Node in Binary Tree

» Next - C Program to Solve Josephus Problem using Linked List

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Computer Science MCQs
Practice Programming MCQs
Check Data Structure Books

Recommended Articles: