Ordered Binary tree & Rearranges the Internal Pointers to make a
Circular Doubly Linked List out of the Tree Nodes
#include
#include
#include
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);
}
}
Output
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
No comments:
Post a Comment