#include
struct node
{ int data1, data2, level;
struct node * right, * left;
}* root, * temp;
void inorder(struct node * p)
{ if (p != NULL)
{ inorder(p – > left);
printf(“\t%d:%d “, p – > data1, p – > data2);
inorder(p – > right);
}
}
void postorder(struct node * p)
{ if (p != NULL)
{ postorder(p – > left);
postorder(p – > right);
printf(“\t%d:%d “, p – > data1, p – > data2);
}
}
void insert(int d1, int d2)
{ int for;
struct node * temp, * prev, * z;
z = (struct node * ) malloc(sizeof(struct node));
z – > right = NULL;
z – > left = NULL;
z – > level = 0;
z – > data1 = d1;
z – > data2 = d2;
if (root == NULL)
{ root = z;
return;
} temp = root;
while (temp != NULL)
{ prev = temp;
f = 0;
if (temp – > level == 0)
{ if (temp – > data1 > z – > data1)
{ temp = temp – > left; f = 1;
} else temp = temp – > right;
} else
{ if (temp – > data2 > z – > data2)
{ temp = temp – > left; f = 1;
} else temp = temp – > right;
}
}
z – > level = (1 – prev – > level);
if (f) prev – > left = z;
else prev – > right = z;
}
void search(struct node * treePtr, int s1, int s2, int flip)
{ if (treePtr != NULL)
{ int x1, y1;
x1 = treePtr – > data1;
y1 = treePtr – > data2;
if (x1 == s1 && y1 == s2)
{ printf(“\nElement %d:%d is found “, s1, s2);
} else
{ if (flip == 0)
{ if (s1 < x1) { search((treePtr - > left), s1, s2, 0);
} else
{ search((treePtr – > right), s1, s2, 0);
}
} if (flip == 1)
{ if (s2 < y1) { search((treePtr - > left), s1, s2, 1);
} else
{ search((treePtr – > right), s1, s2, 1);
}
}
}
} if (treePtr == NULL)
printf(“\nnot found %d::%d \n”, s1, s2);
}
struct node * min(struct node * treePtr, int dim, int cd)
{ struct node * a, * b;
int c1, c2;
if (treePtr == NULL)
return NULL;
if (treePtr != NULL && cd == dim)
{ if (treePtr – > left == NULL)
return treePtr – > data1;
else
return min(treePtr – > left, dim, (cd + 1) % 2);
} else
{ a = min(treePtr – > left, dim, (cd + 1) % 2);
b = min(treePtr – > right, dim, (cd + 1) % 2);
c1 = treePtr – > data1;
if (a != NULL)
{ if (b != NULL)
{ if (a – > data1 < b - > data1 && a – > data1 < c1) return a; } else if (a - > data1 < c1) return a; } if (b != NULL) { if (a != NULL) { if (b - > data1 < a - > data1 && b – > data1 < c1) return b; } else if (b - > data1 < c1) return b; } return treePtr; } } struct node * delete(struct node * z, int d3, int d4, int cd) { struct node * x = NULL, * y = NULL, * prev = NULL; int lg = 0, next_cd = (cd + 1) % 2, flag = 0; if ((z - > data1 == d3) && (z – > data2 == d4))
{ if ((z == root) && (z – > left == NULL) && (z – > right == NULL))
{ root = NULL;
printf(“\nKDTREE is empty\n”);
return;
}
if (z – > right != NULL)
{ y = min(z – > right, cd, next_cd);
z – > data1 = y – > data1;
z – > data2 = y – > data2;
if (z – > right != NULL)
z – > right = delete(z – > right, z – > right – > data1, z – > right – > data2, next_cd);
} else if (z – > left != NULL)
{ x = min(z – > left, cd, next_cd);
z – > data1 = x – > data1;
z – > data2 = x – > data2;
if (z – > right != NULL)
z – > right = delete(z – > right, z – > left – > data1, z – > left – > data2, next_cd);
z – > left = NULL;
} else z = NULL;
} else
{ while (z != NULL)
{ if (d3 == z – > data1 && d4 == z – > data2)
{ if (z == prev – > left)
prev – > left = delete(z, d3, d4, next_cd);
else if (z == prev – > right)
prev – > right = delete(z, d3, d4, next_cd);
break;
} else if (z – > level == 0)
{ if (d3 < z - > data1)
{ prev = z; z = z – > left;
} else if (d3 > z – > data1)
{ prev = z; z = z – > right;
}
} else if (z – > level == 1)
{ if (d4 < z - > data2)
{ prev = z; z = z – > left;
} else if (d4 > z – > data2)
{ prev = z; z = z – > right;
}
}
}
} return z;
}
int main(int argc, char * argv[])
{
int fl = 0, n, d1, d2, d3, d4, s1, s2, flip, val, flip1;
struct node * minvalue;
printf(“KDTree Management”);
while (1)
{ printf(“\nEnter ur option \t1.Insert\t2.Delete\t3.Search\t4.Traversal\t5.Exit\n”);
scanf(“%d”, & val);
switch (val)
{ case 1: printf(“Enter the elements:”);
scanf(“%d”, & d1);
scanf(“%d”, & d2);
insert(d1, d2); break;
case 2: printf(“\nEnter the node you want to delete : “);
scanf(“%d”, & d3);
scanf(“%d”, & d4);
printf(“Enter the splitting axis of the node x-axis:-0 y-axis:-1 : “);
scanf(“%d”, & flip1);
delete(root, d3, d4, flip1);
printf(“\nDeleted element is %d:%d”, d3, d4); break;
case 3: printf(“\nEnter the node you want to search : “);
scanf(“%d”, & s1);
scanf(“%d”, & s2);
printf(“Enter the splitting axis of the node x-axis:-0 y-axis:-1 : “);
scanf(“%d”, & flip);
search(root, s1, s2, flip); break;
case 4: printf(“Root is %d::%d”, root – > data1, root – > data2);
printf(“\nInorder traversal \n”);
inorder(root);
printf(“\nPostorder traversal \n”);
postorder(root);
break;
case 5: fl = 1; break;
default: break;
}
if (fl == 1)
{ break; }
}
}
Sample Output
Sample Output
