Mercurial > data_structures

view src/bst.c @ 4:5dfdc70e3025

find changesets by author, revision, files, or words in the commit message
Binary Search Tree in progress
author Eris Caffee <discordia@eldalin.com>
date Wed, 26 Sep 2012 10:48:01 -0500
parents
children b38243d51aea
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #include "bst.h"
5
6 // Private functions.
7 void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data));
8 void * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
9 void * bst_node_minimum(struct bst_node * node);
10 void * bst_node_maximum(struct bst_node * node);
11
12 ////////////////////////////////////////////////////////////////////////////////
13 struct bst *
14 bst_new(bool (*le)(void * a, void * b),
15 bool (*eq)(void * a, void * b))
16 {
17 if ( (NULL == le) || (NULL == eq) )
18 return NULL;
19
20 struct bst * bst = malloc(sizeof(struct bst));
21 if (NULL == bst)
22 return NULL;
23
24 bst->root = NULL;
25 bst->size = 0;
26 bst->le = le;
27 bst->eq = eq;
28 return bst;
29 }
30
31
32 ////////////////////////////////////////////////////////////////////////////////
33 void
34 bst_delete(struct bst * bst)
35 {
36 if (NULL == bst) return;
37 if (0 < bst->size)
38 {
39 // Walk the tree and delete the nodes.
40 // This will cause memory leaks, so hopefully the user has already
41 // emptied the tree.
42 }
43 free(bst);
44 }
45
46 ////////////////////////////////////////////////////////////////////////////////
47 void *
48 bst_insert(struct bst * bst, void * data)
49 {
50 if ( (NULL == bst) || (NULL == data) )
51 return NULL;
52
53 struct bst_node * new = malloc(sizeof(struct bst_node));
54 if (NULL == new)
55 return NULL;
56 new->left = new->right = new->parent = NULL;
57 new->data = data;
58
59 if (NULL == bst->root)
60 {
61 bst->root = new;
62 return new->data;
63 }
64
65 struct bst_node * p = NULL;
66 struct bst_node * c = bst->root;
67
68 while (NULL != c)
69 {
70 p = c;
71 if (bst->le(new->data, c->data))
72 c = c->left;
73 else
74 c = c->right;
75 }
76 new->parent = p;
77 if (bst->le(new->data, p->data))
78 p->left = new;
79 else
80 p->right = new;
81
82 return new->data;
83 }
84
85
86 ////////////////////////////////////////////////////////////////////////////////
87 void bst_walk_inorder(struct bst * bst, void (*op)(void * data))
88 {
89 if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
90 return;
91
92 bst_node_walk_inorder(bst->root, op);
93 }
94
95 ////////////////////////////////////////////////////////////////////////////////
96 void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data))
97 {
98 if (NULL != node)
99 {
100 bst_node_walk_inorder(node->left, op);
101 op(node->data);
102 bst_node_walk_inorder(node->right, op);
103 }
104 }
105
106 ////////////////////////////////////////////////////////////////////////////////
107 void * bst_search(struct bst * bst, void * data)
108 {
109 if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
110 return NULL;
111
112 return bst_node_search(bst, bst->root, data);
113 }
114
115 ////////////////////////////////////////////////////////////////////////////////
116 // Recursive
117 void * bst_node_search(struct bst * bst, struct bst_node * node, void * data)
118 {
119 if (NULL == node)
120 return NULL;
121
122 if (bst->eq(data, node->data))
123 return node->data;
124
125 if (bst->le(data, node->data))
126 return bst_node_search(bst, node->left, data);
127 else
128 return bst_node_search(bst, node->right, data);
129 }
130
131 ////////////////////////////////////////////////////////////////////////////////
132 // Iterative
133 void * bst_search_iterative(struct bst * bst, void * data)
134 {
135 if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
136 return NULL;
137
138 struct bst_node * node = bst->root;
139 while (1)
140 {
141 if (NULL == node)
142 return NULL;
143
144 if (bst->eq(data, node->data))
145 return node->data;
146
147 if (bst->le(data, node->data))
148 node = node->left;
149 else
150 node = node->right;
151 }
152 }
153
154 ////////////////////////////////////////////////////////////////////////////////
155 void * bst_minimum(struct bst * bst)
156 {
157 if (NULL == bst)
158 return NULL;
159
160 return bst_node_minimum(bst->root);
161 }
162
163 ////////////////////////////////////////////////////////////////////////////////
164 void * bst_node_minimum(struct bst_node * node)
165 {
166 while ( (NULL != node) && (NULL != node->left) )
167 node = node->left;
168 if (NULL == node)
169 return NULL;
170 return node->data;
171 }
172
173 ////////////////////////////////////////////////////////////////////////////////
174 void * bst_maximum(struct bst * bst)
175 {
176 if (NULL == bst)
177 return NULL;
178
179 return bst_node_maximum(bst->root);
180 }
181
182 ////////////////////////////////////////////////////////////////////////////////
183 void * bst_node_maximum(struct bst_node * node)
184 {
185 while ( (NULL != node) && (NULL != node->right) )
186 node = node->right;
187 if (NULL == node)
188 return NULL;
189 return node->data;
190 }