Find Nodes which are at Maximum Distance in Binary Tree
#include
#include
#include
struct btnode
{
int
value;
struct btnode *r,*l;
} *root = NULL, *temp = NULL;
void create();
void insert();
void add(struct btnode *t);
void maxdistance(struct btnode *t);
int count = 0, max = 0, v[100] = {0}, z = 0,
max2, max1[100] = {0};
void main()
{
int
ch, i;
printf("Program to find nodes at maximum distance");
printf("\n Operations ----");
printf("\n1] Insert ");
printf("\n2] Display nodes ");
printf("\n3] Exit ");
while (1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
max = 0;
count = 0;
maxdistance(root);
for (i = 1; i < z; i++)
{
max2 = max1[0];
if (max2 < max1[i])
max2 = max1[i];
}
printf("Maximum distance nodes \nNodes\t Distance ");
for (i = 0; i < z; i++)
{
if (max2 == max1[i])
printf("\n %d\t %d
",v[i],max2);
}
break;
case 3:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
void create()
{
int
data;
printf("Enter the data of node : ");
scanf("%d", &data);
temp
= (struct btnode* ) malloc(1*(sizeof(struct btnode)));
temp->value = data;
temp->l = temp->r = NULL;
}
void insert()
{
create();
if
(root == NULL)
root = temp;
else
add(root);
}
void add(struct btnode *t)
{
if
((temp->value > t->value) && (t->r!=NULL))
add(t->r);
else
if ((temp->value > t->value) && (t->r==NULL))
t->r = temp;
else
if ((temp->value < t->value) && (t->l!=NULL))
add(t->l);
else
if ((temp->value < t->value) && (t->l==NULL))
t->l = temp;
}
void maxdistance(struct btnode *t)
{
if
(t->l!=NULL)
{
count++;
maxdistance(t->l);
}
if
(max < count)
max = count;
if
(max == count)
{
max1[z] = max;
v[z] = t->value;
z++;
}
if
(t->r != NULL)
{
count++;
maxdistance(t->r);
}
count--;
}
Output
Program to find nodes at maximum distance
Operations ----
1]
Insert
2]
Display nodes
3]
Exit
Enter
your choice : 1
Enter
the data of node : 50
Enter
your choice : 1
Enter
the data of node : 30
Enter
your choice : 1
Enter
the data of node : 20
Enter
your choice : 1
Enter
the data of node : 40
Enter
your choice : 1
Enter
the data of node : 35
Enter
your choice : 1
Enter
the data of node : 100
Enter
your choice : 1
Enter
the data of node : 70
Enter
your choice : 1
Enter
the data of node : 120
Enter
your choice : 1
Enter
the data of node : 140
Enter
your choice : 2
Maximum distance nodes
Nodes Distance
35 3
140 3
50
/\
/ \
30 100
/ \ / \
20 40 70 120
/ \
35 140
Enter your choice : 3
Program to find nodes at maximum distance
OPERATIONS ----
1]
Insert
2]
Display nodes
3]
Exit
Enter
your choice : 1
Enter
the data of node : 40
Enter
your choice : 1
Enter
the data of node : 20
Enter
your choice : 1
Enter
the data of node : 60
Enter
your choice : 1
Enter
the data of node : 10
Enter
your choice : 1
Enter
the data of node : 30
Enter
your choice : 1
Enter
the data of node : 80
Enter
your choice : 1
Enter
the data of node : 90
Enter
your choice : 2
Maximum distance nodes
Nodes Distance
90 3
Enter
your choice : 3
40
/\
/ \
20 60
/ \ \
10 30 80
\
90
No comments:
Post a Comment