159 lines
3.7 KiB
C
159 lines
3.7 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <assert.h>
|
|
|
|
typedef struct s_node {
|
|
int element;
|
|
struct s_node* left;
|
|
struct s_node* right;
|
|
} *Nodeptr, Node;
|
|
|
|
typedef Nodeptr* Tree;
|
|
|
|
Tree tree_create() {
|
|
Tree t = malloc(sizeof( Nodeptr ));
|
|
*t = NULL;
|
|
return t;
|
|
}
|
|
|
|
void tree_add(Tree t, int element) {
|
|
Nodeptr n = malloc(sizeof(Node));
|
|
n->element = element;
|
|
n->left = NULL;
|
|
n->right = NULL;
|
|
|
|
if(*t == NULL) {
|
|
*t = n;
|
|
} else {
|
|
Nodeptr iter = *t;
|
|
while(1) {
|
|
if(iter->element > element) {
|
|
if(iter->left == NULL) {
|
|
iter->left = n;
|
|
return;
|
|
} else {
|
|
iter = iter->left;
|
|
}
|
|
} else if(iter->element < element) {
|
|
if(iter->right == NULL) {
|
|
iter->right = n;
|
|
return;
|
|
} else {
|
|
iter = iter->right;
|
|
}
|
|
} else {
|
|
free(n);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void tree_remove(Tree t, int element) {
|
|
Nodeptr iter = *t;
|
|
Nodeptr parent = NULL;
|
|
while(iter != NULL) {
|
|
if(iter->element > element) {
|
|
parent = iter;
|
|
iter = iter->left;
|
|
} else if(iter->element < element) {
|
|
parent = iter;
|
|
iter = iter->right;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
if(iter == NULL) return; // Not found
|
|
|
|
if(iter->right == NULL) {
|
|
if(parent == NULL) *t = iter->left;
|
|
else if(parent->left == iter) parent->left = iter->left;
|
|
else if(parent->right == iter) parent->right = iter->left;
|
|
else assert(0);
|
|
free(iter);
|
|
} else if(iter->left == NULL) {
|
|
if(parent == NULL) *t = iter->right;
|
|
else if(parent->left == iter) parent->left = iter->right;
|
|
else if(parent->right == iter) parent->right = iter->right;
|
|
else assert(0);
|
|
free(iter);
|
|
} else {
|
|
Nodeptr iter2, parent2;
|
|
iter2 = iter->left;
|
|
parent2 = NULL;
|
|
while(iter2->right != NULL) {
|
|
parent2 = iter2;
|
|
iter2 = iter2->right;
|
|
}
|
|
if(parent2 == NULL) {
|
|
iter->left = iter2->left;
|
|
} else {
|
|
parent2->right = iter2->left;
|
|
}
|
|
iter->element = iter2->element;
|
|
free(iter2);
|
|
}
|
|
}
|
|
|
|
int tree_contains(Tree t, int element) {
|
|
Nodeptr iter = *t;
|
|
while(iter != NULL) {
|
|
if(iter->element > element) {
|
|
iter = iter->left;
|
|
} else if(iter->element < element) {
|
|
iter = iter->right;
|
|
} else {
|
|
return 1;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
void tree_print_node_rec(Nodeptr n, int level) {
|
|
if(n == NULL) return;
|
|
|
|
tree_print_node_rec(n->right,level+1);
|
|
|
|
for(int i = 0; i < level; i++) printf("\t");
|
|
printf("%d\n", n->element);
|
|
|
|
tree_print_node_rec(n->left, level+1);
|
|
}
|
|
|
|
void tree_print(Tree t) {
|
|
tree_print_node_rec(*t, 0);
|
|
printf("----------\n");
|
|
}
|
|
|
|
void tree_nodefree_rec(Nodeptr n) {
|
|
if(n == NULL) return;
|
|
tree_nodefree_rec(n->left);
|
|
tree_nodefree_rec(n->right);
|
|
free(n);
|
|
}
|
|
|
|
void tree_free(Tree t) {
|
|
tree_nodefree_rec(*t);
|
|
free(t);
|
|
}
|
|
|
|
int main( int argc, char *argv[] ) {
|
|
int data[10] = {5,7,2,8,6,4,3,1,9,0};
|
|
Tree t = tree_create();
|
|
for(int i = 0; i < 10; i++) {
|
|
tree_add(t,data[i]);
|
|
}
|
|
tree_print(t);
|
|
for(int i = 0; i < 10; i++) {
|
|
assert(tree_contains(t,data[i]));
|
|
}
|
|
for(int i = 0; i < 5; i++) {
|
|
tree_remove(t,data[i]);
|
|
}
|
|
tree_print(t);
|
|
for(int i = 5; i < 10; i++) {
|
|
assert(tree_contains(t,data[i]));
|
|
}
|
|
tree_free(t);
|
|
return 0;
|
|
}
|