2 Simple binary search tree implementation.
10 /* these are the functions that are defines in this file */
11 void *bst_insert(void *tree,void *data,int size,int (*compare)());
12 void *bst_find(void *tree,void *data,int (*compare)());
16 struct bst_struct *ltree;
17 struct bst_struct *rtree;
23 /* find an element in a tree */
24 void *bst_find(void *tree,void *data,int (*compare)())
27 struct bst_struct *bstree = tree;
28 if (!bstree || !data || !compare) return(NULL);
30 ret = compare(data,bstree->data);
32 return(bst_find(bstree->ltree,data,compare));
34 return(bst_find(bstree->rtree,data,compare));
39 /* create a bst bode */
40 void *bst_create_node(coid *data,int size)
42 struct bst_struct *bstree = (struct bst_struct *)malloc(sizeof(*bstree));
45 bstree->data = malloc(size);
48 free(bstree); return(NULL);
50 memcpy(bstree->data,data,size);
51 bstree->data_len = size;
54 /* insert an element into a tree, returning the new tree */
55 void *bst_insert(void *tree,void *data,int size,int (*compare)())
58 struct bst_struct *bstree = tree;
59 if (!data || !compare) return(NULL);
62 return(bst_create_node(data,size));
64 ret = compare(data,bstree->data);
66 bstree->ltree = bst_insert(bstree->ltree,data,size,compare);
68 bstree->rtree = bst_insert(bstree->rtree,data,size,compare);
72 /* replace the existing element */
73 if (bstree->data) free(bstree(data));
74 bstree->data = (void *)malloc(size);
75 if (!bstree->data) return(NULL);
76 memcpy(bstree->data,data,size);
77 bstree->data_len = size;
84 /* find an element in a tree */
85 void bst_inorder(void *tree,int (*fn)())
87 struct bst_struct *bstree = tree;
88 if (!bstree || !fn) return;
90 bst_inorder(bstree->ltree,fn);
91 fn(bstree->data,bstree->data_len);
92 bst_inorder(bstree->rtree,fn);