1 #ifndef BST_H_

2 #define BST_H_

3

4 #include <stddef.h>

5 #include <stdbool.h>

6

7 struct bst_node

8 {

9 struct bst_node * parent;

10 struct bst_node * left;

11 struct bst_node * right;

12 void * data;

13 };

14

15 struct bst

16 {

17 struct bst_node * root;

18 size_t size;

19 bool (*le)(void * a, void * b);

20 bool (*eq)(void * a, void * b);

21 };

22

23 struct bst_iterator

24 {

25 struct bst * bst;

26 struct bst_node * curr;

27 };

28

29 struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));

30 void bst_delete(struct bst * bst);

31

32 void * bst_insert(struct bst * bst, void * data);

33

34 void * bst_search(struct bst * bst, void * data);

35 void * bst_search_iterative(struct bst * bst, void * data);

36

37 void * bst_minimum(struct bst * bst);

38 void * bst_maximum(struct bst * bst);

39

40 void bst_walk_inorder(struct bst * bst, void (*op)(void * data));

41 void bst_walk_preorder(struct bst * bst, void (*op)(void * data));

42 void bst_walk_postorder(struct bst * bst, void (*op)(void * data));

43

44

45 struct bst_iterator * bst_begin(struct bst * bst);

46 struct bst_iterator * bst_end(struct bst * bst);

47 struct bst_iterator * bst_next(struct bst_iterator * it);

48 struct bst_iterator * bst_prev(struct bst_iterator * it);

49 void * bst_value(struct bst_iterator * it);

50

51 void * bst_find(struct bst_iterator * it, void * data);

52 void * bst_remove(struct bst_iterator * it);

53

54 #endif