Trees

This page has been automatically translated using the Google Translate API services. We are working on improving texts. Thank you for your understanding and patience.

Header

#include <core/treest.h>

Functions

Not all data models are linear (Arrays) or organized under a single sort key (Sets). Information is often structured hierarchically, through parent-child relationships: a file system, a family genealogical tree, the structure of an XML/JSON document, a decision tree or a store's category catalog. To represent this kind of relationship, NAppGUI provides the TreeSt type, an N-ary tree (Figure 1), where each node can have an arbitrary number of descendants (0, 1 or more), unlike the binary search trees that underpin Sets.

Unlike Sets, a TreeSt does not maintain any sort or key-search criteria. Its purpose is not to efficiently locate elements, but to express and traverse hierarchical relationships. On the other hand, just as happens with the nodes of a SetSt, each tree node is individually allocated on the heap, so inserting or deleting nodes anywhere in the tree does not invalidate the pointers we keep to other existing nodes, something that could happen with the elements of an Arrays when its internal memory block is relocated.

Because each node needs to keep, in addition to the user data, the links required for navigation (parent and children), TreeSt does not work directly with pointers to the user type as Arrays or Sets do. Instead, most functions receive and return a node (NodeSt(type)), an opaque wrapper that represents the position within the tree. To access or modify the user data associated with a node, we must use treest_node_data.

1. Create trees

• Use treest_create to create an empty tree.
• Use treest_root_new to create the root node.
• Use treest_node_insert to add child nodes.
• Use treest_node_data to access a node's data.
• Use treest_destroy to destroy a tree and all its nodes.

When creating a tree with treest_create, it contains no nodes, not even the root. The first step will be to create it using treest_root_new, an operation that can only be performed once per tree. From there, each node (the root or another already existing one) can receive new children using treest_node_insert, indicating the position in which they will be inserted with respect to their siblings. Both treest_root_new and treest_node_insert return a node with indeterminate content, which we must initialize by accessing its data with treest_node_data (Listing 1).

Just as in Arrays and Sets, to work with user types it is necessary to declare the DeclSt macro (or DeclPt for pointers, see Pointer trees). A single declaration simultaneously enables the ArrSt, SetSt and TreeSt containers for that type, so it is not necessary to repeat it if we have already used it with another container.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

typedef struct _category_t Category;
struct _category_t
{
    String *name;
};

DeclSt(Category);

static void i_remove(Category *cat)
{
    str_destroy(&cat->name);
}

TreeSt(Category) *categories = treest_create(Category);
NodeSt(Category) *root = treest_root_new(categories, Category);
Category *cat = treest_node_data(root, Category);
cat->name = str_c("Electronics");

NodeSt(Category) *computers = treest_node_insert(root, 0, Category);
cat = treest_node_data(computers, Category);
cat->name = str_c("Computers");

NodeSt(Category) *laptops = treest_node_insert(computers, 0, Category);
cat = treest_node_data(laptops, Category);
cat->name = str_c("Laptops");

NodeSt(Category) *audio = treest_node_insert(root, 1, Category);
cat = treest_node_data(audio, Category);
cat->name = str_c("Audio and Video");
...
treest_destroy(&categories, i_remove, Category);

2. Tree traversal

• Use treest_dfs_first and treest_next to traverse the tree forward.
• Use treest_dfs_last and treest_prev to traverse it backward.
• Use treest_foreach or treest_forback to traverse it in a more elegant way.

TreeSt traverses its nodes depth-first (Depth-First Search or DFS): starting from the root, it visits all the descendants of a node before moving on to the next sibling (Figure 2). Just as happens with sets (see Sets), the tree keeps a single internal iterator that moves with treest_next or treest_prev, starting at treest_dfs_first or treest_dfs_last respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

treest_foreach_const(cat, categories, Category)
    uint32_t i, depth = treest_node_depth(cat_node, Category);
    for (i = 0; i < depth; ++i)
        bstd_printf("  ");
    bstd_printf("%s\n", tc(cat->name));
treest_end()

// Output:
// Electronics
//   Computers
//     Laptops
//   Audio and Video

While the tree is being traversed, nodes cannot be inserted or deleted (treest_node_insert, treest_node_delete). If we leave a treest_foreach or treest_forback early (for example with break or return), we must call treest_dfs_stop to release the tree's internal iterator.

3. Navigating between nodes

• Use treest_node_parent to get the parent node.
• Use treest_node_get to get a specific child.
• Use treest_node_size to find out how many children a node has.
• Use treest_node_index to find out the position of a node with respect to its parent.
• Use treest_node_depth to find out the depth of a node.

In addition to sequential traversal, any node allows local navigation to its parent or to a specific child, without needing to traverse the entire tree (Listing 3). By combining treest_node_parent recursively we can, for example, reconstruct the full path of a node up to the root (Listing 4).

1
2
3
4
5
6
7

uint32_t i, n = treest_node_size(root, Category);
for (i = 0; i < n; ++i)
{
    const NodeSt(Category) *child = treest_node_get_const(root, i, Category);
    const Category *cat = treest_node_data_const(child, Category);
    bstd_printf("%s\n", tc(cat->name));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

static void i_print_path(const NodeSt(Category) *node)
{
    const NodeSt(Category) *parent = treest_node_parent_const(node, Category);
    const Category *cat = treest_node_data_const(node, Category);
    if (parent != NULL)
    {
        i_print_path(parent);
        bstd_printf(" > ");
    }
    bstd_printf("%s", tc(cat->name));
}

i_print_path(laptops);
bstd_printf("\n");
// Output: Electronics > Computers > Laptops

4. Tree copy

Use treest_copy to copy a tree.

Just as in Arrays, we must provide a copy method that correctly initializes the fields of each node from another already existing one. The copy is recursive: the root is duplicated and, afterwards, the entire descendant subtree (Listing 5).

1
2
3
4
5
6
7
8

static void i_copy(Category *dest, const Category *src)
{
    dest->name = str_copy(src->name);
}

TreeSt(Category) *ncategories = treest_copy(categories, i_copy, Category);
...
treest_destroy(&ncategories, i_remove, Category);

5. Tree serialization

• Use treest_read to read a tree from a Streams.
• Use treest_write to write a tree to a Streams.

Just as in Arrays, (de)serializing a tree consists of (de)serializing each of its nodes recursively, storing alongside each one the number of children that follow it (Listing 6).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

static void i_read(Stream *stm, Category *cat)
{
    cat->name = str_read(stm);
}

static void i_write(Stream *stm, const Category *cat)
{
    str_write(stm, cat->name);
}

TreeSt(Category) *categories = treest_read(istream, i_read, Category);
...
treest_write(ostream, categories, i_write, Category);
treest_destroy(&categories, i_remove, Category);

6. Deleting nodes and trees

• Use treest_node_delete to delete a node and its subtree.
• Use treest_clear to empty a tree.
• Use treest_destroy to destroy the entire tree.

Deleting a node with treest_node_delete also recursively removes the entire subtree that hung from it (Listing 7). treest_clear does the same with the root, leaving the tree empty but reusable (we will be able to create a root again with treest_root_new).

1
2
3
4
5
6
7

// Remove "Audio and Video" (2nd child of root) and its subtree
treest_node_delete(root, 1, i_remove, Category);

// Remove all nodes (the tree remains usable, without a root)
treest_clear(categories, i_remove, Category);

treest_destroy(&categories, i_remove, Category);

7. Tree limitations

TreeSt is the right structure to model hierarchical relationships, but it is worth keeping in mind:

• No key search: there is no equivalent to setst_get or arrst_search. To locate a specific node you have to traverse the tree, or keep an auxiliary structure (for example, a Sets that indexes nodes by identifier).
• A single active iterator: as in Sets, only one traversal can be in progress per tree at a time. Two treest_foreach cannot be nested over the same tree, nor can its structure be modified while it is being traversed.
• Opaque or shared objects: if the data type is not public, or we need to share references to the nodes with other structures in the model, we must use pointer trees. See Pointer trees.

treest_create ()

Create an empty tree, without a root node.

TreeSt(type)*
treest_create(type);

Return

The new tree.

Remarks

See Create trees.

treest_copy ()

Create a complete copy of a tree.

TreeSt(type)*
treest_copy(const TreeSt(type) *tree,
            FPtr_scopy func_copy,
            type);

Return

The copy of the original tree.

Remarks

The copy function should allocate memory to the fields that require it, but NOT to the object itself. If we pass NULL, a byte-by-byte copy of each node will be made. See Tree copy.

treest_read ()

Create a tree by reading its contents from a Streams.

TreeSt(type)*
treest_read(Stream *stream,
            FPtr_read_init func_read,
            type);

Return

The tree readed.

Remarks

See Tree serialization.

treest_read_ex ()

Create a tree by reading its contents from a Streams. The read function accepts data from the user.

TreeSt(type)*
treest_read_ex(Stream *stream,
               FPtr_read_init_ex func_read,
               dtype *data,
               type,
               dtype);

Return

The tree readed.

Remarks

See Tree serialization.

treest_destroy ()

Destroy a tree and all its nodes.

void
treest_destroy(TreeSt(type) **tree,
               FPtr_remove func_remove,
               type);

Remarks

See Deleting nodes and trees.

treest_destopt ()

Destroy a tree and all its nodes, as long as the tree object is not NULL.

void
treest_destopt(TreeSt(type) **tree,
               FPtr_remove func_remove,
               type);

treest_clear ()

Delete all the nodes of the tree, including the root, leaving it empty without destroying the container.

void
treest_clear(TreeSt(type) *tree,
             FPtr_remove func_remove,
             type);

Remarks

See Deleting nodes and trees.

treest_write ()

Write a tree in a Streams.

void
treest_write(Stream *stream,
             const TreeSt(type) *tree,
             FPtr_write func_write,
             type);

Remarks

See Tree serialization.

treest_write_ex ()

Write a tree in a Streams. The write function accepts user data.

void
treest_write_ex(Stream *stream,
                const TreeSt(type) *tree,
                FPtr_write_ex func_write,
                const dtype *data,
                type,
                dtype);

Remarks

See Tree serialization.

treest_esize ()

Get the size in bytes of the data type stored in each node.

uint32_t
treest_esize(const TreeSt(type) *tree,
             type);

Return

Size in bytes.

treest_mem ()

Get the total memory, in bytes, occupied by the tree and all its nodes.

uint32_t
treest_mem(const TreeSt(type) *tree,
           type);

Return

Memory in bytes.

treest_root_get ()

Get the root node of the tree.

NodeSt(type)*
treest_root_get(TreeSt(type) *tree,
                type);

Return

The root node, or NULL if the tree is empty.

Remarks

See Create trees.

treest_root_get_const ()

Const version of treest_root_get.

const NodeSt(type)*
treest_root_get_const(const TreeSt(type) *tree,
                      type);

Return

The root node.

treest_root_new ()

Create the root node of an empty tree.

NodeSt(type)*
treest_root_new(TreeSt(type) *tree,
                type);

Return

The new root node, with indeterminate content.

Remarks

It can only be invoked once per tree. Use treest_node_data to initialize its fields and treest_node_insert to add descendants to it. See Create trees.

treest_dfs_first ()

Set the internal iterator to the first node of the depth-first traversal (the root).

NodeSt(type)*
treest_dfs_first(TreeSt(type) *tree,
                 type);

Return

The first node, or NULL if the tree is empty.

Remarks

See Tree traversal.

treest_dfs_first_const ()

Const version of treest_dfs_first.

const NodeSt(type)*
treest_dfs_first_const(const TreeSt(type) *tree,
                       type);

Return

The first node.

treest_dfs_last ()

Set the internal iterator to the last node of the depth-first traversal (the deepest descendant of the root's last child).

NodeSt(type)*
treest_dfs_last(TreeSt(type) *tree,
                type);

Return

The last node, or NULL if the tree is empty.

Remarks

See Tree traversal.

treest_dfs_last_const ()

Const version of treest_dfs_last.

const NodeSt(type)*
treest_dfs_last_const(const TreeSt(type) *tree,
                      type);

Return

The last node.

treest_next ()

Advance the internal iterator to the next node of the depth-first traversal.

NodeSt(type)*
treest_next(TreeSt(type) *tree,
            type);

Return

The next node, or NULL if the traversal has finished.

Remarks

See Tree traversal.

treest_next_const ()

Const version of treest_next.

const NodeSt(type)*
treest_next_const(const TreeSt(type) *tree,
                  type);

Return

The next node.

treest_prev ()

Move the internal iterator back to the previous node of the depth-first traversal.

NodeSt(type)*
treest_prev(TreeSt(type) *tree,
            type);

Return

The previous node, or NULL if the traversal has finished.

Remarks

See Tree traversal.

treest_prev_const ()

Const version of treest_prev.

const NodeSt(type)*
treest_prev_const(const TreeSt(type) *tree,
                  type);

Return

The previous node.

treest_dfs_stop ()

Cancel a traversal in progress before reaching its end, releasing the tree's internal iterator.

void
treest_dfs_stop(TreeSt(type) *tree,
                type);

Remarks

It is necessary to call it if we leave a treest_foreach or treest_forback using break or return, since while the tree is "being traversed" nodes cannot be inserted or deleted. See Tree traversal.

treest_node_size ()

Get the number of direct children of a node.

uint32_t
treest_node_size(const NodeSt(type) *node,
                 type);

Return

Number of children.

Remarks

See Navigating between nodes.

treest_node_depth ()

Get the depth of a node, that is, its distance to the root.

uint32_t
treest_node_depth(const NodeSt(type) *node,
                  type);

Return

The depth. The root has depth 0.

Remarks

See Navigating between nodes.

treest_node_index ()

Get the position of a node among its parent's children.

uint32_t
treest_node_index(const NodeSt(type) *node,
                  type);

Return

The node's index.

Remarks

See Navigating between nodes.

treest_node_parent ()

Get the parent node.

NodeSt(type)*
treest_node_parent(NodeSt(type) *node,
                   type);

Return

The parent node, or NULL if node is the root.

Remarks

See Navigating between nodes.

treest_node_parent_const ()

Const version of treest_node_parent.

const NodeSt(type)*
treest_node_parent_const(const NodeSt(type) *node,
                         type);

Return

The parent node.

treest_node_get ()

Get the child located at position pos.

NodeSt(type)*
treest_node_get(NodeSt(type) *node,
                const uint32_t pos,
                type);

Return

The child node.

Remarks

See Navigating between nodes.

treest_node_get_const ()

Const version of treest_node_get.

const NodeSt(type)*
treest_node_get_const(const NodeSt(type) *node,
                      const uint32_t pos,
                      type);

Return

The child node.

treest_node_insert ()

Insert a new child node at position pos.

NodeSt(type)*
treest_node_insert(NodeSt(type) *node,
                   const uint32_t pos,
                   type);

Return

The new node, with indeterminate content.

Remarks

Use treest_node_data to initialize its fields. See Create trees.

treest_node_delete ()

Delete a child node and the entire subtree that hangs from it.

void
treest_node_delete(NodeSt(type) *node,
                   const uint32_t pos,
                   FPtr_remove func_remove,
                   type);

Remarks

See Deleting nodes and trees.

treest_node_data ()

Get a pointer to the user data stored in a node.

type*
treest_node_data(NodeSt(type) *node,
                 type);

Return

Pointer to the object.

treest_node_data_const ()

Const version of treest_node_data.

const type*
treest_node_data_const(const NodeSt(type) *node,
                       type);

Return

Pointer to the object.

treest_foreach ()

Traverse all the nodes of the tree depth-first. Use treest_end to close the loop.

void
treest_foreach(type *elem,
               TreeSt(type) *tree,
               type);

1
2
3

treest_foreach(cat, categories, Category)
    bstd_printf("%s\n", tc(cat->name));
treest_end()

Remarks

See Tree traversal.

treest_foreach_const ()

Const version of treest_foreach.

void
treest_foreach_const(const type *elem,
                     const TreeSt(type) *tree,
                     type);

treest_forback ()

Traverse all the nodes of the tree in reverse order of the depth-first traversal. Use treest_end to close the loop.

void
treest_forback(type *elem,
               TreeSt(type) *tree,
               type);

Remarks

See Tree traversal.

treest_forback_const ()

Const version of treest_forback.

void
treest_forback_const(const type *elem,
                     const TreeSt(type) *tree,
                     type);

treest_end ()

Close the loop opened by treest_foreach, treest_foreach_const, treest_forback or treest_forback_const.

void
treest_end(void);