Arrays PHP: ¿cómo hacer una matriz unidimensional en una matriz multidimensional anidada?

Question

Al recuperar una estructura jerárquica de MySQL (tabla con una ID de columna y una columna PADRES significando las relaciones jerárquicas), I Mapa el resultado en una matriz enumerada como sigue (para este ejemplo los números son arbitrarios):

Array ([3] => Array ([7] => Array()), [7] => Array ([8] => Array())) 

El aviso 3 es el padre de 7 y el 7 es el padre de 8 (esto podría seguir y seguir, y cualquier padre podría tener varios hijos).

yo quería reducir esta matriz en una matriz multidimensional anidada de la siguiente manera:

Array ([3] => Array ([7] => Array ([8] => Array()))) 

Es decir, cada nuevo ID se le asigna automáticamente una matriz vacía. De todos modos, los hijos de cualquier ID serán empujados a la matriz de sus padres.

Tome un vistazo a la siguiente ilustración para mayor aclaración:

alt text http://img263.imageshack.us/img263/4986/array.gif

Esto probablemente se traducirá en una operación recursiva complicado, ya que siempre tengo que comprobar si uno de los padres con cualquier determinado ID ya existe (y si es así, inserte el valor en su matriz).

¿Hay una función de php incorporada que pueda ayudarme con esto? ¿Tienes alguna idea de cómo construir esto? Por lo que vale, estoy usando esto para construir una barra de navegación en wordpress (que puede contener categorías, subcategorías, publicaciones ... esencialmente cualquier cosa).

Answer 1

La idea es que conserve una matriz auxiliar con todos los nodos (padres e hijos) que encuentre. Los valores de estas matrices son referencias que respaldan su resultado.

Esto construye el árbol en tiempo lineal (array_key_exists realiza una consulta de tabla de dispersión, que está en O media (1)):

//table contains (id, parent) 
$orig = array(
    11 => 8, 
    7 => 3, 
    8 => 7, 
    99 => 8, 
    16 => 8, 
); 

$childrenTable = array(); 
$result = array(); 

foreach ($orig as $n => $p) { 
    //parent was not seen before, put on root 
    if (!array_key_exists($p, $childrenTable)) { 
     $childrenTable[$p] = array(); 
     $result[$p] = &$childrenTable[$p]; 
    } 
    //child was not seen before 
    if (!array_key_exists($n, $childrenTable)) { 
     $childrenTable[$n] = array(); 
    } 

    //root node has a parent after all, relocate 
    if (array_key_exists($n, $result)) { 
     unset($result[$n]); 
    } 

    $childrenTable[$p][$n] = &$childrenTable[$n]; 
} 
unset($childrenTable); 

var_dump($result); 

da

array(1) { 
    [3]=> 
    array(1) { 
    [7]=> 
    array(1) { 
     [8]=> 
     array(3) { 
     [11]=> 
     array(0) { 
     } 
     [99]=> 
     array(0) { 
     } 
     [16]=> 
     array(0) { 
     } 
     } 
    } 
    } 
} 

EDIT: unset $childrenTable en el finalizar para borrar los indicadores de referencia. En la práctica, es probable que desee realizar la operación dentro de una función de todos modos.

Answer 2

Esta es la pregunta y sus respuestas debería ser útil para usted: turn database result into array.

Asegúrese de leer la presentación en PDF de @Bill Karwin, específicamente los temas relacionados con la tabla de Cierre.