Trees

Single path from each node to the trees root

Applications

Data organization
Searching
Sorting
Language processing
Graphics
Compression

Typically implemented using pointers to nodes:

typedef struct tree_s {
        tree_t      data;
        struct tree_s   *left, *right;
        short       bal;
    }
    tree;

Processing algorithms are also recursive:

tree_t
tree_srch(tree **ppr_tree, int (*pfi_compare)(), tree_t p_user)
{
    register int    i_comp;

    if (*ppr_tree) {
        i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
        if (i_comp > 0)
            return (tree_srch(&(**ppr_tree).right, pfi_compare, p_user))
        if (i_comp < 0)
            return (tree_srch(&(**ppr_tree).left, pfi_compare, p_user))
        /* not higher, not lower... this must be the one.
         */
        return ((**ppr_tree).data)
    }
    /* grounded. NOT found.
     */
    return (NULL)
}