data_structures: b38243d51aea src/bst.c

view src/bst.c @ 7:b38243d51aea

A bit more on the bst

author	Eris Caffee <discordia@eldalin.com>
date	Wed, 26 Sep 2012 18:59:22 -0500
parents	5dfdc70e3025
children	6605a342e8f8

line source

1 #include <stdio.h>

2 #include <stdlib.h>

4 #include "bst.h"

6 // Private functions.

7 void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data));

8 void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data));

9 void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data));

11 void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n));

13 void * bst_node_search(struct bst * bst, struct bst_node * node, void * data);

14 void * bst_node_minimum(struct bst_node * node);

15 void * bst_node_maximum(struct bst_node * node);

16 void bst_node_free(struct bst_node * node);

18 ////////////////////////////////////////////////////////////////////////////////

19 struct bst *

20 bst_new(bool (*le)(void * a, void * b),

21 bool (*eq)(void * a, void * b))

22 {

23 if ( (NULL == le) || (NULL == eq) )

24 return NULL;

26 struct bst * bst = malloc(sizeof(struct bst));

27 if (NULL == bst)

28 return NULL;

30 bst->root = NULL;

31 bst->size = 0;

32 bst->le = le;

33 bst->eq = eq;

34 return bst;

35 }

38 ////////////////////////////////////////////////////////////////////////////////

39 void

40 bst_delete(struct bst * bst)

41 {

42 if (NULL == bst) return;

43 if (0 < bst->size)

44 {

45 // Walk the tree and delete the nodes.

46 // This may cause memory leaks, so hopefully the user has already

47 // emptied the tree.

48 bst_node_walk_postorder(bst->root, bst_node_free);

49 }

50 free(bst);

51 }

53 ////////////////////////////////////////////////////////////////////////////////

54 void

55 bst_node_free(struct bst_node * node)

56 {

57 free(node);

58 }

60 ////////////////////////////////////////////////////////////////////////////////

61 void *

62 bst_insert(struct bst * bst, void * data)

63 {

64 if ( (NULL == bst) || (NULL == data) )

65 return NULL;

67 struct bst_node * new = malloc(sizeof(struct bst_node));

68 if (NULL == new)

69 return NULL;

70 new->left = new->right = new->parent = NULL;

71 new->data = data;

73 if (NULL == bst->root)

74 {

75 bst->root = new;

76 return new->data;

77 }

79 struct bst_node * p = NULL;

80 struct bst_node * c = bst->root;

82 while (NULL != c)

83 {

84 p = c;

85 if (bst->le(new->data, c->data))

86 c = c->left;

87 else

88 c = c->right;

89 }

90 new->parent = p;

91 if (bst->le(new->data, p->data))

92 p->left = new;

93 else

94 p->right = new;

96 bst->size++;

97 return new->data;

98 }

100

101 ////////////////////////////////////////////////////////////////////////////////

102 void bst_walk_inorder(struct bst * bst, void (*op)(void * data))

103 {

104 if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )

105 return;

106

107 bst_data_walk_inorder(bst->root, op);

108 }

109

110 ////////////////////////////////////////////////////////////////////////////////

111 void bst_walk_postorder(struct bst * bst, void (*op)(void * data))

112 {

113 if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )

114 return;

115

116 bst_data_walk_postorder(bst->root, op);

117 }

118

119 ////////////////////////////////////////////////////////////////////////////////

120 void bst_walk_preorder(struct bst * bst, void (*op)(void * data))

121 {

122 if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )

123 return;

124

125 bst_data_walk_preorder(bst->root, op);

126 }

127

128 ////////////////////////////////////////////////////////////////////////////////

129 void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data))

130 {

131 if (NULL != node)

132 {

133 bst_data_walk_inorder(node->left, op);

134 op(node->data);

135 bst_data_walk_inorder(node->right, op);

136 }

137 }

138

139 ////////////////////////////////////////////////////////////////////////////////

140 void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data))

141 {

142 if (NULL != node)

143 {

144 bst_data_walk_postorder(node->left, op);

145 bst_data_walk_postorder(node->right, op);

146 op(node->data);

147 }

148 }

149

150 ////////////////////////////////////////////////////////////////////////////////

151 void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data))

152 {

153 if (NULL != node)

154 {

155 op(node->data);

156 bst_data_walk_preorder(node->left, op);

157 bst_data_walk_preorder(node->right, op);

158 }

159 }

160

161 ////////////////////////////////////////////////////////////////////////////////

162 void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n))

163 {

164 if (NULL != node)

165 {

166 bst_node_walk_postorder(node->left, op);

167 bst_node_walk_postorder(node->right, op);

168 op(node);

169 }

170 }

171

172 ////////////////////////////////////////////////////////////////////////////////

173 void * bst_search(struct bst * bst, void * data)

174 {

175 if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )

176 return NULL;

177

178 return bst_node_search(bst, bst->root, data);

179 }

180

181 ////////////////////////////////////////////////////////////////////////////////

182 // Recursive

183 void * bst_node_search(struct bst * bst, struct bst_node * node, void * data)

184 {

185 if (NULL == node)

186 return NULL;

187

188 if (bst->eq(data, node->data))

189 return node->data;

190

191 if (bst->le(data, node->data))

192 return bst_node_search(bst, node->left, data);

193 else

194 return bst_node_search(bst, node->right, data);

195 }

196

197 ////////////////////////////////////////////////////////////////////////////////

198 // Iterative

199 void * bst_search_iterative(struct bst * bst, void * data)

200 {

201 if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )

202 return NULL;

203

204 struct bst_node * node = bst->root;

205 while (1)

206 {

207 if (NULL == node)

208 return NULL;

209

210 if (bst->eq(data, node->data))

211 return node->data;

212

213 if (bst->le(data, node->data))

214 node = node->left;

215 else

216 node = node->right;

217 }

218 }

219

220 ////////////////////////////////////////////////////////////////////////////////

221 void * bst_minimum(struct bst * bst)

222 {

223 if (NULL == bst)

224 return NULL;

225

226 return bst_node_minimum(bst->root);

227 }

228

229 ////////////////////////////////////////////////////////////////////////////////

230 void * bst_node_minimum(struct bst_node * node)

231 {

232 while ( (NULL != node) && (NULL != node->left) )

233 node = node->left;

234 if (NULL == node)

235 return NULL;

236 return node->data;

237 }

238

239 ////////////////////////////////////////////////////////////////////////////////

240 void * bst_maximum(struct bst * bst)

241 {

242 if (NULL == bst)

243 return NULL;

244

245 return bst_node_maximum(bst->root);

246 }

247

248 ////////////////////////////////////////////////////////////////////////////////

249 void * bst_node_maximum(struct bst_node * node)

250 {

251 while ( (NULL != node) && (NULL != node->right) )

252 node = node->right;

253 if (NULL == node)

254 return NULL;

255 return node->data;

256 }

257

258 ////////////////////////////////////////////////////////////////////////////////

259 struct bst_iterator * bst_begin(struct bst * bst)

260 {

261 if ( (NULL == bst) || (NULL == bst->root) )

262 return NULL;

263

264 struct bst_node * min = bst->root;

265 while (min->left)

266 min = min->left;

267

268 struct bst_iterator * it = malloc(sizeof(struct bst_iterator));

269 if (NULL == it)

270 return NULL;

271

272 it->bst = bst;

273 it->curr = min;

274 return it;

275 }

276

277 ////////////////////////////////////////////////////////////////////////////////

278 struct bst_iterator * bst_end(struct bst * bst)

279 {

280 if ( (NULL == bst) || (NULL == bst->root) )

281 return NULL;

282

283 struct bst_node * max = bst->root;

284 while (max->right)

285 max = max->right;

286

287 struct bst_iterator * it = malloc(sizeof(struct bst_iterator));

288 if (NULL == it)

289 return NULL;

290

291 it->bst = bst;

292 it->curr = max;

293 return it;

294 }

295

296 ////////////////////////////////////////////////////////////////////////////////

297 struct bst_iterator * bst_next(struct bst_iterator * it)

298 {

299 if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )

300 return NULL;

301

302 if (NULL == it->curr->right)

303 {

304 struct bst_node * p = it->curr;

305 it->curr = it->curr->parent;

306 while ( (NULL != it->curr) && (p == it->curr->right) )

307 {

308 p = it->curr;

309 it->curr = it->curr->parent;

310 }

311

312 if (it->curr == NULL)

313 return NULL;

314 }

315 else

316 {

317 struct bst_node * min = it->curr->right;

318 while (min->left)

319 min = min->left;

320 it->curr = min;

321 }

322 return it;

323 }

324

325 ////////////////////////////////////////////////////////////////////////////////

326 struct bst_iterator * bst_prev(struct bst_iterator * it)

327 {

328 if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )

329 return NULL;

330

331 if (NULL == it->curr->left)

332 {

333 struct bst_node * p = it->curr;

334 it->curr = it->curr->parent;

335 while ( (NULL != it->curr) && (p == it->curr->left) )

336 {

337 p = it->curr;

338 it->curr = it->curr->parent;

339 }

340

341 if (it->curr == NULL)

342 return NULL;

343 }

344 else

345 {

346 struct bst_node * max = it->curr->left;

347 while (max->right)

348 max = max->right;

349 it->curr = max;

350 }

351 return it;

352 }

353

354 ////////////////////////////////////////////////////////////////////////////////

355 void * bst_value(struct bst_iterator * it)

356 {

357 if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )

358 return NULL;

359

360 return it->curr->data;

361 }

362

Mercurial > data_structures

view src/bst.c @ 7:b38243d51aea