#include #include typedef struct _Node { int key; int value; struct _Node* L; struct _Node* R; } Node; typedef struct { int count; Node *root; } Tree; Node* Add(Tree* T, int K) { Node** N = &(T->root); while (*N != NULL) { if ((*N)->key == K) return *N; if ((*N)->key < K) N = &((*N)->L); else N = &((*N)->R); } if ( (*N = malloc(sizeof(Node))) == NULL) return NULL; (*N)->key = K; (*N)->value = 0; (*N)->L = (*N)->R = NULL; T->count++; return *N; } Node** FindD(Tree* T, int K) { Node** FindDNode(Node** N, int K) { if (*N == NULL) return NULL; if ((*N)->key == K) return N; if ((*N)->key < K) return FindDNode(&((*N)->L), K); return FindDNode(&((*N)->R), K); } if (T == NULL) return NULL; return FindDNode(&(T->root), K); } Node* Find(Tree* T, int K) { Node* FindNode(Node* N, int K) { if (N == NULL) return NULL; if (N->key == K) return N; if (N->key < K) return FindNode(N->L, K); return FindNode(N->R, K); } if (T == NULL) return NULL; return FindNode(T->root, K); } Node* Insert(Tree* T, int K, int V) { Node* N = Find(T, K); if (N == NULL) return NULL; N->value = V; return N; } void Remove(Tree* T, int K) { Node** N = FindD(T, K); if (N == NULL) return; if (((**N).L == NULL) && ((**N).R == NULL)) { free(*N); *N = NULL; T->count--; return; } if (((**N).L != NULL) && ((**N).R == NULL)) { Node* Temp = *N; *N = (**N).L; free(Temp); T->count--; return; } if (((**N).L == NULL) && ((**N).R != NULL)) { Node* Temp = *N; *N = (**N).R; free(Temp); T->count--; return; } Node** GetSuccessor(Node** P) { if ((**P).L == NULL) return P; return GetSuccessor(&((**P).L)); } Node** S = GetSuccessor(&((**N).R)); (**S).L = (**N).L; (**S).R = (**N).R; free(*N); *N = malloc( sizeof(Node) ); (*N)->key = (**S).key; (*N)->value = (**S).value; (*N)->L = (**S).L, (*N)->R = (**S).R; free(*S); *S = NULL; T->count--; return; } void Uproot(Tree* T) { void FreeNode(Node* N) { if (N == NULL) return; FreeNode(N->L); FreeNode(N->R); free(N); } if (T == NULL) return; FreeNode(T->root); free(T); } Tree* plant() { Tree* T; if ((T = malloc(sizeof(Tree))) == NULL) return NULL; T->count = 0; T->root = NULL; return T; } int main() { Tree* T = plant(); Add(T, 4); Add(T, 2); Add(T, 7); Add(T, 6); Add(T, 8); Insert(T, 8, 3); Insert(T, 6, 2); Remove(T, 7); printf("The tree has %d elements and ", T->count); if (Find(T, 6) == NULL) printf("didn't"); else printf("did"); printf(" find 6, and the value of 8 is %d.", Find(T,8)->value); Uproot(T); return 0; }