Next: , Previous: Binary tree selection, Up: Binary trees


14.5 Inserting and deleting nodes in a binary tree

— Function: Bstnode * bst_insert (Bstree *bst, void *data, void *cmp_args)

Creates a node containing data, and inserts that node into the appropriate place in bst. Returns a pointer to the node thus created, or a null pointer if there was insufficient memory. cmp_args is passed as the last argument to bst's comparison function.

— Function: void bst_delete (Bstree *bst, Bstnode *node, cmp_args)

Delete node from bst, retaining the sorted property. cmp_args is passed as the last argument to bst's comparison function when inserting node's subtrees. node must be a member of bst.

— Function: void bst_wipe (Bstree *bst)

Deletes all the nodes in bst.

It is possible to selectively delete many nodes at once. This requires a `pruning' function.

— Function pointer: Bst_prune_f int (*) (void *obj, void *args)

The type of a function pointer used to determine whether to delete objects in a bstree. It is passed a reference to the contents of an element in obj, as well as a pointer to user-supplied arguments in args. It should return zero if and only if the element should not be deleted. Note that if the elements of a bstree were dynamically allocated, it is probably a good idea to make the pruning function free this dynamically allocated memory.

— Function: void bst_prune (Bstree *bst, Bst_prune_f *pruner, prune_args, cmp_args)

Deletes any objects in bst for which pruner is true. prune_args is passed as the last argument to pruner. cmp_args is passed as the last argument to bst's comparison function when inserting the subtrees of deleted nodes.