Árboles (punteros)

Cabecera

#include <core/treept.h>

Funciones

Al igual que vimos con ArrPt y SetPt, el tipo TreePt son árboles N-arios (ver Árboles) donde cada nodo almacena un puntero al objeto en lugar del objeto completo (Figura 1). Por tanto, sirve todo lo visto en Árboles (creación de la raíz, recorrido en profundidad, navegación entre nodos, copia, serialización...), sustituyendo cada función por su equivalente treept_*. Las particularidades a tener en cuenta son las mismas que ya vimos entre Arrays/Arrays (punteros) y Sets/Sets (punteros):

• Hay que crear y liberar memoria dinámica para cada objeto.
• Se puede almacenar el valor NULL en cualquier nodo.
• Es más seguro si otras partes de la aplicación mantienen punteros a los objetos almacenados en el árbol.
• Es la única opción para trabajar con objetos opacos.

1. Crear árboles de punteros

• Utiliza treept_create para crear un árbol vacío.
• Utiliza treept_root_new para crear el nodo raíz.
• Utiliza treept_node_insert para añadir nodos hijo.
• Utiliza DeclPt para declarar tipos de puntero a struct.

La principal diferencia respecto a Árboles radica en que tanto treept_root_new como treept_node_insert reciben como parámetro el puntero al objeto ya creado, en lugar de devolver una zona de memoria indeterminada que inicializar a posteriori (Listado 1).

 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

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

DeclPt(Category);

static Category *i_create(const char_t *name)
{
    Category *cat = heap_new(Category);
    cat->name = str_c(name);
    return cat;
}

static void i_destroy(Category **cat)
{
    str_destroy(&(*cat)->name);
    heap_delete(cat, Category);
}

TreePt(Category) *categories = treept_create(Category);
NodePt(Category) *root = treept_root_new(categories, i_create("Electronics"), Category);
NodePt(Category) *computers = treept_node_insert(root, 0, i_create("Computers"), Category);
treept_node_insert(computers, 0, i_create("Laptops"), Category);
treept_node_insert(root, 1, i_create("Audio and Video"), Category);
...
treept_destroy(&categories, i_destroy, Category);

El resto de operaciones (recorrido en profundidad, navegación entre nodos, copia, serialización o eliminación) funcionan exactamente igual que en Árboles, sustituyendo treest_node_data por treept_node_data, que en este caso devuelve el puntero almacenado en el nodo (que puede ser NULL).

treept_create ()

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

TreePt(type)*
treept_create(type);

Retorna

El nuevo árbol.

Observaciones

Ver Crear árboles de punteros.

treept_copy ()

Crea una copia completa de un árbol de punteros.

TreePt(type)*
treept_copy(const TreePt(type) *tree,
            FPtr_copy func_copy,
            type);

Retorna

La copia del árbol original.

Observaciones

La función de copia debe crear un objeto dinámico y asignar memoria para los campos internos que lo requieran. Si pasamos NULL, se copiarán los punteros originales, lo que puede suponer un riesgo de integridad ya que un mismo objeto podría ser destruido dos veces si no ponemos especial cuidado.

treept_read ()

Crea un árbol de punteros leyendo su contenido de un Streams.

TreePt(type)*
treept_read(Stream *stream,
            FPtr_read func_read,
            type);

Retorna

El árbol leído.

treept_read_ex ()

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

TreePt(type)*
treept_read_ex(Stream *stream,
               FPtr_read_ex func_read,
               dtype *data,
               type,
               dtype);

Retorna

El árbol leído.

treept_destroy ()

Destruye un árbol y todos sus nodos.

void
treept_destroy(TreePt(type) **tree,
               FPtr_destroy func_destroy,
               type);

treept_destopt ()

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

void
treept_destopt(TreePt(type) **tree,
               FPtr_destroy func_destroy,
               type);

treept_clear ()

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

void
treept_clear(TreePt(type) *tree,
             FPtr_destroy func_destroy,
             type);

treept_write ()

Escribe un árbol de punteros en un Streams.

void
treept_write(Stream *stream,
             const TreePt(type) *tree,
             FPtr_write func_write,
             type);

treept_write_ex ()

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

void
treept_write_ex(Stream *stream,
                const TreePt(type) *tree,
                FPtr_write_ex func_write,
                const dtype *data,
                type,
                dtype);

treept_esize ()

Obtiene el tamaño en bytes almacenado en cada nodo, es decir, el tamaño de un puntero.

uint32_t
treept_esize(const TreePt(type) *tree,
             type);

Retorna

Tamaño en bytes.

treept_mem ()

Obtiene la memoria total, en bytes, ocupada por la estructura del árbol (nodos y punteros, sin contar la memoria de los objetos referenciados).

uint32_t
treept_mem(const TreePt(type) *tree,
           type);

Retorna

Memoria en bytes.

treept_root_get ()

Obtiene el nodo raíz del árbol.

NodePt(type)*
treept_root_get(TreePt(type) *tree,
                type);

Retorna

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

Observaciones

Ver Crear árboles de punteros.

treept_root_get_const ()

Versión const de treept_root_get.

const NodePt(type)*
treept_root_get_const(const TreePt(type) *tree,
                      type);

Retorna

El nodo raíz.

treept_root_new ()

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

NodePt(type)*
treept_root_new(TreePt(type) *tree,
                type *ptr,
                type);

Retorna

El nuevo nodo raíz.

Observaciones

Solo se puede invocar una vez por árbol. Utiliza treept_node_insert para añadirle descendientes. Ver Crear árboles de punteros.

treept_dfs_first ()

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

NodePt(type)*
treept_dfs_first(TreePt(type) *tree,
                 type);

Retorna

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

treept_dfs_first_const ()

Versión const de treept_dfs_first.

const NodePt(type)*
treept_dfs_first_const(const TreePt(type) *tree,
                       type);

Retorna

El primer nodo.

treept_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).

NodePt(type)*
treept_dfs_last(TreePt(type) *tree,
                type);

Retorna

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

treept_dfs_last_const ()

Versión const de treept_dfs_last.

const NodePt(type)*
treept_dfs_last_const(const TreePt(type) *tree,
                      type);

Retorna

El último nodo.

treept_next ()

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

NodePt(type)*
treept_next(TreePt(type) *tree,
            type);

Retorna

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

treept_next_const ()

Versión const de treept_next.

const NodePt(type)*
treept_next_const(const TreePt(type) *tree,
                  type);

Retorna

El siguiente nodo.

treept_prev ()

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

NodePt(type)*
treept_prev(TreePt(type) *tree,
            type);

Retorna

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

treept_prev_const ()

Versión const de treept_prev.

const NodePt(type)*
treept_prev_const(const TreePt(type) *tree,
                  type);

Retorna

El nodo anterior.

treept_dfs_stop ()

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

void
treept_dfs_stop(TreePt(type) *tree,
                type);

treept_node_size ()

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

uint32_t
treept_node_size(const NodePt(type) *node,
                 type);

Retorna

Número de hijos.

treept_node_depth ()

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

uint32_t
treept_node_depth(const NodePt(type) *node,
                  type);

Retorna

La profundidad. La raíz tiene profundidad 0.

treept_node_index ()

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

uint32_t
treept_node_index(const NodePt(type) *node,
                  type);

Retorna

El índice del nodo.

treept_node_parent ()

Obtiene el nodo padre.

NodePt(type)*
treept_node_parent(NodePt(type) *node,
                   type);

Retorna

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

treept_node_parent_const ()

Versión const de treept_node_parent.

const NodePt(type)*
treept_node_parent_const(const NodePt(type) *node,
                         type);

Retorna

El nodo padre.

treept_node_get ()

Obtiene el hijo situado en la posición pos.

NodePt(type)*
treept_node_get(NodePt(type) *node,
                const uint32_t pos,
                type);

Retorna

El nodo hijo.

treept_node_get_const ()

Versión const de treept_node_get.

const NodePt(type)*
treept_node_get_const(const NodePt(type) *node,
                      const uint32_t pos,
                      type);

Retorna

El nodo hijo.

treept_node_insert ()

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

NodePt(type)*
treept_node_insert(NodePt(type) *node,
                   const uint32_t pos,
                   type *ptr,
                   type);

Retorna

El nuevo nodo.

Observaciones

Ver Crear árboles de punteros.

treept_node_delete ()

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

void
treept_node_delete(NodePt(type) *node,
                   const uint32_t pos,
                   FPtr_destroy func_destroy,
                   type);

treept_node_data ()

Obtiene el puntero al objeto almacenado en un nodo.

type*
treept_node_data(NodePt(type) *node,
                 type);

Retorna

El puntero almacenado, que puede ser NULL.

treept_node_data_const ()

Versión const de treept_node_data.

const type*
treept_node_data_const(const NodePt(type) *node,
                       type);

Retorna

El puntero almacenado.

treept_foreach ()

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

void
treept_foreach(type *elem,
               TreePt(type) *tree,
               type);

treept_foreach_const ()

Versión const de treept_foreach.

void
treept_foreach_const(const type *elem,
                     const TreePt(type) *tree,
                     type);

treept_forback ()

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

void
treept_forback(type *elem,
               TreePt(type) *tree,
               type);

treept_forback_const ()

Versión const de treept_forback.

void
treept_forback_const(const type *elem,
                     const TreePt(type) *tree,
                     type);

treept_end ()

Cierra el bucle abierto por treept_foreach, treept_foreach_const, treept_forback o treept_forback_const.

void
treept_end(void);