Construct a Balanced Binary Search Tree which has same data members
as the given Doubly Linked List
#include
#include
#include
struct node
{
int num;
struct node *left;
struct node *right;
};
void create(struct node **);
void treemaker(struct node **, int);
void display(struct node *);
void displayTree(struct node *);
void delete(struct node **);
int main()
{
struct node *headList = NULL, *rootTree, *p;
int count = 1, flag = 0;
create(&headList);
printf("Displaying the doubly linked list:\n");
display(headList);
rootTree = p = headList;
while (p->right != NULL)
{
p = p->right;
count = count + 1;
if (flag)
{
rootTree = rootTree->right;
}
flag = !flag;
}
treemaker(&rootTree, count / 2);
printf("Displaying the tree: (Inorder)\n");
displayTree(rootTree);
printf("\n");
return 0;
}
void create(struct node **head)
{
struct node *rear, *temp;
int a, ch;
do
{
printf("Enter a number: ");
scanf("%d", &a);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = a;
temp->right = NULL;
temp->left = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->right = temp;
temp->left = rear;
}
rear = temp;
printf("Do you wish to continue [1/0] ?: ");
scanf("%d", &ch);
} while (ch != 0);
}
void treemaker(struct node **root, int count)
{
struct node *quarter, *thirdquarter;
int n = count, i = 0;
if ((*root)->left != NULL)
{
quarter = (*root)->left;
for (i = 1; (i < count / 2) && (quarter->left != NULL); i++)
{
quarter = quarter->left;
}
(*root)->left->right = NULL;
(*root)->left = quarter;
printf("%d's left child is now %d\n", (*root)->num, quarter->num);
if (quarter != NULL)
{
treemaker(&quarter, count / 2);
}
}
if ((*root)->right != NULL)
{
thirdquarter = (*root)->right;
for (i = 1; (i < count / 2) && (thirdquarter->right != NULL); i++)
{
thirdquarter = thirdquarter->right;
}
(*root)->right->left = NULL;
(*root)->right = thirdquarter;
printf("%d's right child is now %d\n", (*root)->num, thirdquarter->num);
if (thirdquarter != NULL)
{
treemaker(&thirdquarter, count / 2);
}
}
}
void display(struct node *head)
{
while (head != NULL)
{
printf("%d ", head->num);
head = head->right;
}
printf("\n");
}
void displayTree(struct node *root)
{
if (root != NULL)
{
displayTree(root->left);
printf("%d ", root->num);
displayTree(root->right);
}
}
void delete(struct node **root)
{
if (*root != NULL)
{
displayTree((*root)->left);
displayTree((*root)->right);
free(*root);
}
}
Output
Enter a number: 1
Do you wish to continue [1/0] ?: 1
Enter a number: 2
Do you wish to continue [1/0] ?: 1
Enter a number: 3
Do you wish to continue [1/0] ?: 1
Enter a number: 4
Do you wish to continue [1/0] ?: 1
Enter a number: 5
Do you wish to continue [1/0] ?: 1
Enter a number: 6
Do you wish to continue [1/0] ?: 0
Displaying the doubly linked list:
1 2 3 4 5 6
Displaying the tree: (Inorder)
1 2 3 4 5 6
No comments:
Post a Comment