93 lines
1.7 KiB
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;
|
||
|
|
}
|