Árboles

Cabecera

#include <core/treest.h>

Funciones

No todos los modelos de datos son lineales (Arrays) ni se organizan bajo una única clave de orden (Sets). Muchas veces la información se estructura de forma jerárquica, mediante relaciones padre-hijo: un sistema de archivos, el árbol genealógico de una familia, la estructura de un documento XML/JSON, un árbol de decisión o el catálogo de categorías de una tienda. Para representar este tipo de relaciones, NAppGUI ofrece el tipo TreeSt, un árbol N-ario (Figura 1), donde cada nodo puede tener un número arbitrario de descendientes (0, 1 o más), a diferencia de los árboles binarios de búsqueda que sustentan a Sets.

A diferencia de Sets, un TreeSt no mantiene ningún criterio de orden ni de búsqueda por clave. Su razón de ser no es localizar elementos de forma eficiente, sino expresar y recorrer relaciones jerárquicas. En contrapartida, al igual que ocurre con los nodos de un SetSt, cada nodo del árbol se reserva de forma individual en el heap, por lo que insertar o eliminar nodos en cualquier parte del árbol no invalida los punteros que mantengamos a otros nodos ya existentes, algo que sí podría ocurrir con los elementos de un Arrays al reubicarse su bloque interno de memoria.

Debido a que cada nodo necesita mantener, además de los datos del usuario, los enlaces necesarios para la navegación (padre e hijos), TreeSt no trabaja directamente con punteros al tipo de usuario como hacen Arrays o Sets. En su lugar, la mayoría de funciones reciben y devuelven un nodo (NodeSt(type)), una envoltura opaca que representa la posición dentro del árbol. Para acceder o modificar los datos de usuario asociados a un nodo, debemos utilizar treest_node_data.

1. Crear árboles

• Utiliza treest_create para crear un árbol vacío.
• Utiliza treest_root_new para crear el nodo raíz.
• Utiliza treest_node_insert para añadir nodos hijo.
• Utiliza treest_node_data para acceder a los datos de un nodo.
• Utiliza treest_destroy para destruir un árbol y todos sus nodos.

Al crear un árbol con treest_create, este no contiene ningún nodo, ni siquiera la raíz. El primer paso será crearla mediante treest_root_new, operación que solo puede realizarse una vez por árbol. A partir de ahí, cada nodo (la raíz u otro ya existente) puede recibir nuevos hijos mediante treest_node_insert, indicando en qué posición se insertarán respecto a sus hermanos. Tanto treest_root_new como treest_node_insert devuelven un nodo con contenido indeterminado, que deberemos inicializar accediendo a sus datos con treest_node_data (Listado 1).

Al igual que en Arrays y Sets, para trabajar con tipos de usuario es necesario declarar la macro DeclSt (o DeclPt para punteros, ver Árboles (punteros)). Una misma declaración habilita simultáneamente los contenedores ArrSt, SetSt y TreeSt para ese tipo, por lo que no es necesario repetirla si ya la hemos utilizado con otro contenedor.

 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. Recorrido de árboles

• Utiliza treest_dfs_first y treest_next para recorrer el árbol hacia adelante.
• Utiliza treest_dfs_last y treest_prev para recorrerlo hacia atrás.
• Utiliza treest_foreach o treest_forback para recorrerlo de forma más elegante.

TreeSt recorre sus nodos en profundidad (Depth-First Search o DFS): partiendo de la raíz, visita primero todos los descendientes de un nodo antes de pasar al siguiente hermano (Figura 2). Al igual que ocurre con los conjuntos (ver Sets), el árbol mantiene un único iterador interno que se desplaza con treest_next o treest_prev, comenzando en treest_dfs_first o treest_dfs_last respectivamente.

 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

Mientras el árbol está siendo recorrido no se pueden insertar ni eliminar nodos (treest_node_insert, treest_node_delete). Si abandonamos un treest_foreach o treest_forback antes de tiempo (por ejemplo con break o return), debemos llamar a treest_dfs_stop para liberar el iterador interno del árbol.

3. Navegación entre nodos

• Utiliza treest_node_parent para obtener el nodo padre.
• Utiliza treest_node_get para obtener un hijo concreto.
• Utiliza treest_node_size para saber cuántos hijos tiene un nodo.
• Utiliza treest_node_index para saber la posición de un nodo con respecto a su padre.
• Utiliza treest_node_depth para conocer la profundidad de un nodo.

Además del recorrido secuencial, cualquier nodo permite navegar de forma local a su padre o a un hijo concreto, sin necesidad de recorrer el árbol completo (Listado 3). Combinando treest_node_parent de forma recursiva podemos, por ejemplo, reconstruir el camino completo de un nodo hasta la raíz (Listado 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. Copia de árboles

Utiliza treest_copy para copiar un árbol.

Al igual que en Arrays, deberemos proveer un método de copia que inicialice correctamente los campos de cada nodo a partir de otro ya existente. La copia es recursiva: se duplica la raíz y, a continuación, todo el subárbol descendiente (Listado 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. Serialización de árboles

• Utiliza treest_read para leer un árbol desde un Streams.
• Utiliza treest_write para escribir un árbol a un Streams.

Al igual que en Arrays, (de)serializar un árbol consiste en (de)serializar cada uno de sus nodos de forma recursiva, guardando junto a cada uno el número de hijos que le siguen (Listado 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. Eliminar nodos y árboles

• Utiliza treest_node_delete para eliminar un nodo y su subárbol.
• Utiliza treest_clear para vaciar un árbol.
• Utiliza treest_destroy para destruir el árbol completo.

Eliminar un nodo con treest_node_delete elimina también, de forma recursiva, todo el subárbol que colgaba de él (Listado 7). treest_clear hace lo mismo con la raíz, dejando el árbol vacío pero reutilizable (podremos volver a crear una raíz con 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. Limitaciones de árboles

TreeSt es la estructura adecuada para modelar relaciones jerárquicas, pero conviene tener presente:

• Sin búsqueda por clave: no existe un equivalente a setst_get o arrst_search. Para localizar un nodo concreto hay que recorrer el árbol, o bien mantener una estructura auxiliar (por ejemplo, un Sets que indexe nodos por identificador).
• Un único iterador activo: como en Sets, solo se puede tener un recorrido en curso por árbol. No se pueden anidar dos treest_foreach sobre el mismo árbol, ni modificar su estructura mientras se recorre.
• Objetos opacos o compartidos: si el tipo de dato no es público, o necesitamos compartir referencias a los nodos con otras estructuras del modelo, deberemos utilizar árboles de punteros. Ver Árboles (punteros).

treest_create ()

Crea un árbol vacío, sin nodo raíz.

TreeSt(type)*
treest_create(type);

Retorna

El nuevo árbol.

Observaciones

Ver Crear árboles.

treest_copy ()

Crea una copia completa de un árbol.

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

Retorna

La copia del árbol original.

Observaciones

La función de copia debe asignar memoria a los campos que lo requieran, pero NO al objeto en sí mismo. Si pasamos NULL, se realizará una copia byte a byte de cada nodo. Ver Copia de árboles.

treest_read ()

Crea un árbol leyendo su contenido de un Streams.

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

Retorna

El árbol leído.

Observaciones

Ver Serialización de árboles.

treest_read_ex ()

Crea un árbol leyendo su contenido de un Streams. La función de lectura acepta datos del usuario.

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

Retorna

El árbol leído.

Observaciones

Ver Serialización de árboles.

treest_destroy ()

Destruye un árbol y todos sus nodos.

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

Observaciones

Ver Eliminar nodos y árboles.

treest_destopt ()

Destruye un árbol y todos sus nodos, siempre y cuando el objeto árbol no sea NULL.

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

treest_clear ()

Elimina todos los nodos del árbol, incluida la raíz, dejándolo vacío pero sin destruir el contenedor.

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

Observaciones

Ver Eliminar nodos y árboles.

treest_write ()

Escribe un árbol en un Streams.

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

Observaciones

Ver Serialización de árboles.

treest_write_ex ()

Escribe un árbol en un Streams. La función de escritura acepta datos del usuario.

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

Observaciones

Ver Serialización de árboles.

treest_esize ()

Obtiene el tamaño en bytes del tipo de dato almacenado en cada nodo.

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

Retorna

Tamaño en bytes.

treest_mem ()

Obtiene la memoria total, en bytes, ocupada por el árbol y todos sus nodos.

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

Retorna

Memoria en bytes.

treest_root_get ()

Obtiene el nodo raíz del árbol.

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

Retorna

El nodo raíz, o NULL si el árbol está vacío.

Observaciones

Ver Crear árboles.

treest_root_get_const ()

Versión const de treest_root_get.

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

Retorna

El nodo raíz.

treest_root_new ()

Crea el nodo raíz de un árbol vacío.

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

Retorna

El nuevo nodo raíz, con contenido indeterminado.

Observaciones

Solo se puede invocar una vez por árbol. Utiliza treest_node_data para inicializar sus campos y treest_node_insert para añadirle descendientes. Ver Crear árboles.

treest_dfs_first ()

Sitúa el iterador interno en el primer nodo del recorrido en profundidad (la raíz).

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

Retorna

El primer nodo, o NULL si el árbol está vacío.

Observaciones

Ver Recorrido de árboles.

treest_dfs_first_const ()

Versión const de treest_dfs_first.

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

Retorna

El primer nodo.

treest_dfs_last ()

Sitúa el iterador interno en el último nodo del recorrido en profundidad (el descendiente más profundo del último hijo de la raíz).

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

Retorna

El último nodo, o NULL si el árbol está vacío.

Observaciones

Ver Recorrido de árboles.

treest_dfs_last_const ()

Versión const de treest_dfs_last.

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

Retorna

El último nodo.

treest_next ()

Avanza el iterador interno al siguiente nodo del recorrido en profundidad.

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

Retorna

El siguiente nodo, o NULL si el recorrido ha finalizado.

Observaciones

Ver Recorrido de árboles.

treest_next_const ()

Versión const de treest_next.

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

Retorna

El siguiente nodo.

treest_prev ()

Retrocede el iterador interno al nodo anterior del recorrido en profundidad.

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

Retorna

El nodo anterior, o NULL si el recorrido ha finalizado.

Observaciones

Ver Recorrido de árboles.

treest_prev_const ()

Versión const de treest_prev.

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

Retorna

El nodo anterior.

treest_dfs_stop ()

Cancela un recorrido en curso antes de alcanzar su final, liberando el iterador interno del árbol.

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

Observaciones

Es necesario llamarla si abandonamos un treest_foreach o treest_forback mediante break o return, ya que mientras el árbol esté "en recorrido" no se pueden insertar ni eliminar nodos. Ver Recorrido de árboles.

treest_node_size ()

Obtiene el número de hijos directos de un nodo.

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

Retorna

Número de hijos.

Observaciones

Ver Navegación entre nodos.

treest_node_depth ()

Obtiene la profundidad de un nodo, es decir, su distancia hasta la raíz.

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

Retorna

La profundidad. La raíz tiene profundidad 0.

Observaciones

Ver Navegación entre nodos.

treest_node_index ()

Obtiene la posición de un nodo entre los hijos de su padre.

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

Retorna

El índice del nodo.

Observaciones

Ver Navegación entre nodos.

treest_node_parent ()

Obtiene el nodo padre.

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

Retorna

El nodo padre, o NULL si node es la raíz.

Observaciones

Ver Navegación entre nodos.

treest_node_parent_const ()

Versión const de treest_node_parent.

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

Retorna

El nodo padre.

treest_node_get ()

Obtiene el hijo situado en la posición pos.

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

Retorna

El nodo hijo.

Observaciones

Ver Navegación entre nodos.

treest_node_get_const ()

Versión const de treest_node_get.

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

Retorna

El nodo hijo.

treest_node_insert ()

Inserta un nuevo nodo hijo en la posición pos.

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

Retorna

El nuevo nodo, con contenido indeterminado.

Observaciones

Utiliza treest_node_data para inicializar sus campos. Ver Crear árboles.

treest_node_delete ()

Elimina un nodo hijo y todo el subárbol que cuelga de él.

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

Observaciones

Ver Eliminar nodos y árboles.

treest_node_data ()

Obtiene un puntero a los datos de usuario almacenados en un nodo.

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

Retorna

Puntero al objeto.

treest_node_data_const ()

Versión const de treest_node_data.

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

Retorna

Puntero al objeto.

treest_foreach ()

Recorre todos los nodos del árbol en profundidad. Usa treest_end para cerrar el bucle.

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()

Observaciones

Ver Recorrido de árboles.

treest_foreach_const ()

Versión const de treest_foreach.

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

treest_forback ()

Recorre todos los nodos del árbol en orden inverso al recorrido en profundidad. Usa treest_end para cerrar el bucle.

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

Observaciones

Ver Recorrido de árboles.

treest_forback_const ()

Versión const de treest_forback.

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

treest_end ()

Cierra el bucle abierto por treest_foreach, treest_foreach_const, treest_forback o treest_forback_const.

void
treest_end(void);