Algoritmo para implementar árboles no binarios usando un vector de 1 dimensión?

Question

Cada nodo del árbol puede tener un número arbitrario de hijos. Necesito una forma de construir y atravesar tales árboles, pero implementarlos usando un vector dimensional o una lista.

Answer 1

Si sólo se puede utilizar un vector (no especificada en cuestión), y los nodos no debe contener su propia lista, sólo algunos indicadores (direcciones en el vector), entonces usted puede probar esto:

1. cada nodo ejerce en la dirección de su hermano
2. primer nodo después de dado (si no es su hermano) es niño, con el puntero al segundo hijo y así sucesivamente
3. cada uno de sus hijos tiene sus propios hijos

así que para t ree así:

A 
| \ 
B E ___ 
|\ \ \ \ 
C D F G H 

su vector se vería así:

idx: 0 1 2 3 4 5 6 7 
nodes: A B C D E F G H 
next: _ 4 3 _ _ 6 7 _ 

donde _ es puntero nulo

Editar:
Otro enfoque:

1. cada nodo tiene dirección de la región en el vector ocupada por sus hijos
2. niños están uno junto al otro
3. existe nodo nulo en el vector, el marcado final de los hermanos grupo

Para que el enfoque dado árbol se vería así:

idx: 0 1 2 3 4 5 6 7 8 9 A B 
nodex: A _ B E _ C D _ F G H _ 
child: 2 5 8 _ _ _ _ _ 

De esta forma puede encontrar fácilmente hijos de cualquier nodo dado aleatoriamente y reorganizar una matriz sin mover todos los elementos (simplemente copie los elementos secundarios al final de la tabla, actualice el puntero y agregue el siguiente elemento al final de la tabla)

Answer 2

La forma estándar de almacenar un árbol binario completo en una matriz (como se usa para implementaciones de montón binario) es agradable porque puede representar el árbol con una matriz de elementos en el orden de un recorrido de árbol de orden de nivel. Usando ese esquema, hay trucos rápidos para calcular las posiciones del nodo padre e hijo. Pasar a un árbol en el que cada nodo puede tener un número arbitrario de elementos genera una llave en ese tipo de esquema.

Existen, sin embargo, varios esquemas para representar árboles arbitrarios como árboles binarios. Se discuten con gran detalle en el Arte de la Programación de Computadora de Donald Knuth, Volumen I, Sección 2.3.

Si los nodos en sí tienen permiso para contener un puntero, puede almacenar una lista de indicadores secundarios para cada nodo. ¿Es eso posible en tu caso?

Answer 3

Sin restricciones en los valores de los nodos, y suponiendo que sólo puede utilizar una única lista, me construir de la siguiente manera:

representar cada nodo como (val ; [ int ; ...]) donde val es el valor del nodo y cada int es el puesto en la lista de uno de sus hijos. Use un separador no imprimible si es necesario.

El recorrido es muy lento.

Answer 4

Puede implementarlo utilizando una lista vinculada unidimensional con poca sobrecarga.

Todos los padres contendrán punteros a sus hijos. (Pero esto requiere decidir si la cantidad máxima de nodos se conoce de antemano).

Para un árbol que tenga A como nodo raíz y B, C, D como hijos, su representación será la siguiente.

A -> B A -> C A -> D

Nota que hay 3 enlaces de A.

Una forma de superar el limite superior en el número de nodos está teniendo puntero adicional en los nodos

lo tanto, ahora A -> (niño) B -> (adj) -> (adj) C -> (adj) -> D

En este caso, es bastante compleja para actualizar el árbol, cuando eliminación ocurre.

Es aún más fácil diseñar mejores estructuras de datos si puede decir sus límites de tiempo en las diversas operaciones.

Answer 5

Lo que básicamente hace es escribir los inicios de un administrador de memoria para un intérprete Lisp emparejando los elementos del vector en celdas cons. Aquí hay una cosa tal Tiré juntos en C hace un momento:?

#include <stdbool.h> 
#include <iso646.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <assert.h> 

#define MEMORY_SIZE 1024 
#define NIL 0 
#define IVAL_MASK 0x8000000 

struct pair 
{ 
    bool allocated; 
    size_t first; 
    size_t second; 
}; 

size_t allocate_pair(struct pair vector[]) 
{ 
    for (size_t i = 1; i < MEMORY_SIZE; i++) 
     { 
      if (not vector[i].allocated) 
       { 
        vector[i].allocated = true; 
        return i; 
       } 
     } 

    return NIL; 
} 

size_t make_pair(struct pair vector[], size_t a, size_t b) 
{ 
    size_t the_pair = allocate_pair(vector); 

    if (the_pair != NIL) 
     { 
      vector[the_pair].first = a; 
      vector[the_pair].second = b; 
      return the_pair; 
     } 
    else 
     { 
      fprintf(stderr, 
        "Out of pairs -- make_pair(%p, %zu, %zu)", 
        vector, 
        a, 
        b); 
      exit(EXIT_FAILURE); 
     } 
} 

size_t first(struct pair vector[], size_t index) 
{ 
    assert(vector[index].allocated); 

    return vector[index].first; 
} 


size_t second(struct pair vector[], size_t index) 
{ 
    assert(vector[index].allocated); 

    return vector[index].second; 
} 

void print_pair_aux(struct pair[], size_t, size_t); 
void print_pair(struct pair vector[], size_t p) 
{ 
    assert(vector[p].allocated); 

    size_t a = first(vector, p); 
    size_t b = second(vector, p); 

    printf("("); 

    print_pair_aux(vector, a, b); 

    printf(")"); 
} 

void print_pair_aux(struct pair vector[], size_t a, size_t b) 
{ 
    if (a == NIL) 
     printf("NIL"); 
    else if (a >= IVAL_MASK) 
     printf("%zu", a &~ IVAL_MASK); 
    else 
     print_pair(vector, a); 

    if (b == NIL) 
     printf(""); 
    else if (b >= IVAL_MASK) 
     printf(" . %zu", b &~ IVAL_MASK); 
    else 
     { 
      printf(" "); 
      print_pair_aux(vector, 
          first(vector, b), 
          second(vector, b)); 
     } 

} 

int main(void) 
{ 
    struct pair *vector = calloc(MEMORY_SIZE, sizeof *vector); 

#define cons(A,B) make_pair(vector, (A), (B)) 
#define ival(x) ((x) | IVAL_MASK) 

    size_t a = cons(ival(3), cons(ival(4), NIL)); 
    size_t b = cons(ival(2), cons(a, NIL)); 
    size_t c = cons(ival(6), cons(ival(7), cons(ival(8), NIL))); 
    size_t d = cons(ival(5), cons(c, NIL)); 
    size_t e = cons(ival(1), cons(b, cons(d, NIL))); 

    print_pair(vector, e); 
    puts(""); 
} 

 
$ cc -std=c99 try.c 
$ ./a.out 
(1 (2 (3 4)) (5 (6 7 8)))