MIT-Curricular/DS/C/Lab/Shortcodes/BST.c

93 lines
1.7 KiB
C

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
int d;
struct TreeNode *l, *r;
} T;
T *c(int d) {
T *n = malloc(sizeof(T));
n->d = d;
n->l = n->r = NULL;
return n;
}
T *i(T *r, int d) {
if (!r) return c(d);
if (d < r->d) r->l = i(r->l, d);
else if (d > r->d) r->r = i(r->r, d);
return r;
}
T *f(T *r) {
while (r->l) r = r->l;
return r;
}
T *d(T *r, int k) {
if (!r) return NULL;
if (k < r->d) r->l = d(r->l, k);
else if (k > r->d) r->r = d(r->r, k);
else {
if (!r->l) {
T *t = r->r;
free(r);
return t;
} else if (!r->r) {
T *t = r->l;
free(r);
return t;
}
T *t = f(r->r);
r->d = t->d;
r->r = d(r->r, t->d);
}
return r;
}
void t(T *r) {
if (r) {
t(r->l);
printf("%d ", r->d);
t(r->r);
}
}
int s(T *r, int k, int *p) {
if (!r) return 0;
int l = s(r->l, k, p);
if (l) return l;
if (++*p == k) return *p;
return s(r->r, k, p);
}
int main() {
T *r = NULL;
int c, v;
while (1) {
printf("\n1. Insert\n2. Delete\n3. Search\n4. Display\n5. Exit\n");
scanf("%d", &c);
if (c == 1) {
scanf("%d", &v);
r = i(r, v);
} else if (c == 2) {
scanf("%d", &v);
r = d(r, v);
} else if (c == 3) {
scanf("%d", &v);
int p = 0, f = s(r, v, &p);
printf(f ? "Found at %d\n" : "Not found\n", f);
} else if (c == 4) {
t(r);
printf("\n");
} else if (c == 5) {
break;
} else {
printf("Invalid\n");
}
}
free(r);
return 0;
}