burkey.co /docs/libflint/binarytree
index binarytree
~/docs/libflint/binarytree.md
libflint

Binarytree

libflint·Data Structures

A binary tree built by attaching left and right children, not by key order. For insert, find, and remove by comparison, see bst.

Usage#

Attach children by hand. Payloads are stored as pointers and are not copied. Pass NULL for the destructor when the payloads must not be freed. The handle can live on the stack.

int seen;

void visit_int(void *data) {
    seen = *(int *)data;
}

BinTree tree;
bintree_init(&tree, NULL);
int root = 1;
int left = 2;
int right = 3;
if (bintree_ins_left(&tree, NULL, &root) == 0 &&
    bintree_ins_left(&tree, tree.root, &left) == 0 &&
    bintree_ins_right(&tree, tree.root, &right) == 0) {
    bintree_traverse(&tree, tree.root, BINTREE_INORDER, visit_int);
    /* inorder writes 2, then 1, then 3; seen == 3 */
}
bintree_destroy(&tree);

The example uses stack payloads, so the destructor is NULL. bintree_destroy frees every node and does not free the handle. With a destructor, each payload needs its own lifetime. The callback runs on every removed payload, including a NULL payload, after that node's children have been removed.

Structs#

BinTree#

typedef struct {
    size_t size;

    void (*destroy)(void *data);

    struct BinTreeNode *root;
} BinTree;

size is the node count. root is the root node, or NULL when the tree is empty. destroy is the payload callback. Read size and root. Do not write the fields.

BinTreeNode#

typedef struct BinTreeNode {
    void *data;
    struct BinTreeNode *left;
    struct BinTreeNode *right;
} BinTreeNode;

data is the stored payload pointer. left and right are the children, or NULL. Read them. Do not write left or right. Replacing data does not free the previous pointer.

Functions#

bintree_init#

Sets size to 0, root to NULL, and destroy to the payload callback. The callback may be NULL. The handle is not allocated here. A NULL tree is not checked.

void bintree_init(BinTree *tree, void (*destroy)(void *data));

bintree_destroy#

Removes every node, then zeros the handle, including the destructor pointer. Does not free the handle. A NULL tree is not checked. A second call on a zeroed handle is safe. The handle may be passed to bintree_init again.

void bintree_destroy(BinTree *tree);

bintree_ins_left / bintree_ins_right#

Creates a node that stores data and links it as the left or right child of node. Pass NULL for node to insert the root, and only when size is 0. Either call inserts that root. A non-NULL node must already belong to tree. Membership is not checked.

Returns 0 on success. Returns -1 if the tree is not empty and node is NULL, if that child is already present, if allocation fails, or if size is SIZE_MAX. Failure leaves the tree unchanged. A NULL tree is not checked.

int bintree_ins_left(BinTree *tree, BinTreeNode *node, void *data);
int bintree_ins_right(BinTree *tree, BinTreeNode *node, void *data);

bintree_rem_left / bintree_rem_right#

bintree_rem_left removes the subtree at the left child of node. bintree_rem_right removes the subtree at the right child. NULL node removes the whole tree for either call. A missing child is a no-op, and an empty tree is a no-op. A non-NULL node must already belong to tree. Membership is not checked. A NULL tree is not checked.

For each removed node, the children are removed first. The payload destructor then runs if one is set, including when data is NULL, and the node is freed. size drops by the number of nodes removed. The destructor pointer on the handle is left as it was.

void bintree_rem_left(BinTree *tree, BinTreeNode *node);
void bintree_rem_right(BinTree *tree, BinTreeNode *node);

bintree_merge#

Joins left and right under a new root in merge that stores data. merge, left, and right must be non-NULL and distinct. merge must be empty (root is NULL and size is 0). left->destroy and right->destroy must be the same pointer, and both NULL counts as the same. Returns 0 on success. Returns -1 if any of those checks fail, if 1 + left->size + right->size would exceed SIZE_MAX, or if the root node cannot be allocated.

On success, merge adopts left->destroy, links both existing subtrees without copying them, and sets size to one plus the two source sizes. A later destroy of merge passes data to that destructor. left and right are left empty (root NULL, size 0) and are not destroyed. Their destructor pointers stay as they were. Any failure before the root allocation leaves all three trees unchanged. If that allocation fails, merge->destroy has already been set to left->destroy, and neither source tree is taken.

int bintree_merge(BinTree *merge, BinTree *left, BinTree *right, void *data);

bintree_traverse#

Walks the subtree rooted at node and passes each stored payload to visitor. BINTREE_PREORDER visits the node, then the left subtree, then the right. BINTREE_INORDER visits the left subtree, the node, then the right. BINTREE_POSTORDER visits the left subtree, the right subtree, then the node. Any other order visits nothing.

A NULL node returns without calling visitor. When node is non-NULL and order is one of those three, visitor must be non-NULL and must not modify the tree. The tree argument is not read.

void bintree_traverse(BinTree *tree, BinTreeNode *node, int order,
                      void (*visitor)(void *data));

bintree_debug_print#

Prints a text drawing of the tree to stdout. A NULL print_fn formats each payload as an int, so the payload must be a non-NULL pointer to an int. Otherwise print_fn must write a NUL-terminated label that fits in buf_sz. An empty tree prints nothing. A NULL tree is not checked.

void bintree_debug_print(BinTree *tree,
                         void (*print_fn)(void *data, char *buf, size_t buf_sz));

Macros#

bintree_is_eob is true when node is NULL. bintree_is_leaf is true when node is non-NULL and both children are NULL. NULL is not a leaf.

#define bintree_is_eob(node) ((node) == NULL)
#define bintree_is_leaf(node) ((node) != NULL && \
    ((const BinTreeNode *)(node))->left == NULL && \
    ((const BinTreeNode *)(node))->right == NULL)