====== binarytree ======

Binary tree with standard leaf operations

===== Usage =====

Create the tree. The user is responsible for memory management of the ''%%BinTree%%'' struct.

<code c>
BinTree *tree = malloc(sizeof(BinTree));
</code>

After the tree is created, init it. The second argument on ''%%bintree_init()%%'' is an optional memory freeing function pointer with signature ''%%void (*destroy)(void *data)%%''. Use ''%%free()%%'' from the stdlib if you are creating the data with ''%%malloc()%%''. If allocation of your data is more complex, you can pass your own memory deallocation function as long as it fits the signature.

In this example, we are passing ''%%NULL%%'' because all memory will be stack allocated.

<code c>
bintree_init(tree, NULL);
int root = 0;
int l1 = 1;
int l2 = 2;
int r1 = 12;
int r2 = 200;
</code>

Next lets insert our data into the tree. The insert functions signature is ''%%bintree_ins_...(tree, parent, data)%%''. If you are inserting data at the root of the tree, you may use either ''%%bintree_ins_left()%%'' or ''%%bintree_ins_right()%%'' as long as ''%%NULL%%'' is passed as the parent argument.

<code c>
bintree_ins_left(tree, NULL, &root);
bintree_ins_left(tree, tree->root, &l1);
bintree_ins_left(tree, tree->root->left, &l2);
bintree_ins_right(tree, tree->root->left, &r2);
bintree_ins_right(tree, tree->root, &r1);
bintree_ins_right(tree, tree->root->right, &r2);
bintree_ins_left(tree, tree->root->right, &l1);
</code>

We can use ''%%bintree_debug_print(tree)%%'' to print a graphical representation of the tree to ''%%stdout%%''

<code plaintext>
└──0
    ├──1
    │   ├──2
    │   └──200
    └──12
        ├──1
        └──200
</code>

To cleanup the tree, first destroy the nodes. If you passed a deallocation function, it will be called on the data member of each node before the node itself is freed. ''%%bintree_destroy()%%'' does not free the tree itself, just the nodes inside of it, hence we must also call ''%%free()%%'' on the tree.

<code c>
bintree_destroy(tree);
free(tree);
tree = NULL;
</code>

Here is the entire example:

<code c>
BinTree *tree = malloc(sizeof(BinTree));
bintree_init(tree, NULL);

int root = 0;
int l1 = 1;
int l2 = 2;
int r1 = 12;
int r2 = 200;

bintree_ins_left(tree, NULL, &root);
bintree_ins_left(tree, tree->root, &l1);
bintree_ins_left(tree, tree->root->left, &l2);
bintree_ins_right(tree, tree->root->left, &r2);
bintree_ins_right(tree, tree->root, &r1);
bintree_ins_right(tree, tree->root->right, &r2);
bintree_ins_left(tree, tree->root->right, &l1);

bintree_debug_print(tree);

bintree_destroy(tree);
free(tree);
tree = NULL;
</code>

===== Structs =====

==== BinTree ====

Binary tree struct

<code c>
typedef struct {
    int size;
    int (*compare)(const void *a, const void *b);
    void (*destroy)(void *data);
    struct BinTreeNode *root;
} BinTree;
</code>

Members:

  * ''%%size%%'': How many nodes the tree contains
  * ''%%compare%%'': Comparison function between data in two nodes. Currently not used for anything
  * ''%%destroy%%'': Optional deallocation function for data inside a node. Typical usage is ''%%NULL%%'' for stack allocated data and ''%%free()%%'' for data created with ''%%malloc()%%''
  * ''%%root%%'': The root node of the tree

==== BinTreeNode ====

Node of the tree

<code c>
typedef struct BinTreeNode {
    void *data;
    struct BinTreeNode *left;
    struct BinTreeNode *right;
} BinTreeNode;
</code>

Members: - ''%%data%%'': void pointer to data the node contains - ''%%left%%'': left facing leaf of the node - ''%%right%%'': right facing leaf of the node

===== Functions =====

==== bintree_init ====

Initialize the binary tree. User is responsible for freeing memory with ''%%bintree_destroy()%%''.

<code c>
void bintree_init(BinTree *tree, void (*destroy)(void *data))
</code>

==== bintree_destroy ====

Destroys the nodes inside a tree and calls the deallaction function on the data if one was provided. Does not deallocate the tree itself, that is left to the user.

<code c>
void bintree_destroy(BinTree *tree)
</code>

==== bintree_ins_left ====

Creates a new node containing ''%%data%%'' and inserts it as the left child of ''%%node%%''.

<code c>
int bintree_ins_left(BinTree *tree, BinTreeNode *node, void *data)
</code>

==== bintree_ins_right ====

Creates a new node containing ''%%data%%'' and inserts it as the right child of ''%%node%%''.

<code c>
int bintree_ins_right(BinTree *tree, BinTreeNode *node, void *data)
</code>

==== bintree_rem_left ====

Removes and deallocates the left child node of ''%%node%%''. Calls the deallocation function on the data if one was provided.

<code c>
void bintree_rem_left(BinTree *tree, BinTreeNode *node)
</code>

==== bintree_rem_right ====

Removes and deallocates the right child node of ''%%node%%''. Calls the deallocation function on the data if one was provided.

<code c>
void bintree_rem_right(BinTree *tree, BinTreeNode *node)
</code>

==== bintree_debug_print ====

Prints a representation of the tree to stdout. Gets very messy with large trees.

<code c>
void bintree_debug_print(BinTree *tree)
</code>

==== bintree_is_eob ====

Utility macro that checks if the node is the End Of Branch.

<code c>
#define bintree_is_eob(node) ((node) == NULL)
</code>

==== bintree_is_leaf ====

Utility macro that checks if a node has children.

<code c>
#define bintree_is_leaf(node) ((node)->left == NULL && (node)->right == NULL)
</code>