Find center of a tree
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
int height;
}*root=NULL;
void insert(struct node **root,int num){
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->left=NULL;
temp->right=NULL;
temp->height=0;
temp->data=num;
if((*root)==NULL){
(*root)=temp;
return ;
}
if(num>(*root)->data)
insert(&((*root)->right),num);
else
insert(&((*root)->left),num);
}
int max(int a,int b){
return a>b?a:b;
}
int height(struct node *root){
if(root==NULL)
return 0;
root->height=max(height(root->left),height(root->right));
return 1+root->height;
}
int min(int a,int b)
{
return a<b?a:b;
}
int findcenter(struct node *root)
{
if(root==NULL)
return 0;
static int center=0;
int lh=0,rh=0;
if(root->left)
lh=root->left->height;
if(root->right)
rh=root->right->height;
int larger=max(lh,rh);
int smaller=min(lh,rh);
center=1+max(center,smaller);
if(abs(center-1-larger)<=1)
return root->data;
else if(larger==rh)
return findcenter(root->right);
else
return findcenter(root->left);
}
void display(struct node *root)
{
if(!root)
return;
display(root->left);
printf(" %d %d\n",root->data,root->height);
display(root->right);
}
int main()
{
insert(&root,6);
insert(&root,5);
insert(&root,3);
insert(&root,1);
insert(&root,9);
insert(&root,7);
insert(&root,8);
height(root);
display(root);
printf("Congrats ,so you got the center %d\n",findcenter(root));
return 0;
}
Hey! What do I change and how in the code to be able to solve the problem: http://www.quora.com/How-do-I-find-the-node-that-has-the-least-maximum-distance-to-all-the-other-nodes-in-a-graph
ReplyDelete