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

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]**

**Related Posts:**

- Check Programming Books
- Apply for Computer Science Internship
- Practice Programming MCQs
- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books