Después de de esta extensa selección de datos dimos con la respuesta esta cuestión que suelen tener muchos los usuarios. Te brindamos la respuesta y nuestro deseo es servirte de gran apoyo.
Solución:
Esto requiere una función recursiva muy básica para analizar los pares hijo / padre en una estructura de árbol y otra función recursiva para imprimirla. Solo una función sería suficiente, pero aquí hay dos para mayor claridad (se puede encontrar una función combinada al final de esta respuesta).
Primero inicialice la matriz de pares hijo / padre:
$tree = array(
'H' => 'G',
'F' => 'G',
'G' => 'D',
'E' => 'D',
'A' => 'E',
'B' => 'C',
'C' => 'E',
'D' => null
);
Luego, la función que analiza esa matriz en una estructura de árbol jerárquica:
function parseTree($tree, $root = null)
$return = array();
# Traverse the tree and search for direct children of the root
foreach($tree as $child => $parent)
# A direct child is found
if($parent == $root)
# Remove item from tree (we don't need to traverse this again)
unset($tree[$child]);
# Append the child into result array and parse its children
$return[] = array(
'name' => $child,
'children' => parseTree($tree, $child)
);
return empty($return) ? null : $return;
Y una función que atraviesa ese árbol para imprimir una lista desordenada:
function printTree($tree)
if(!is_null($tree) && count($tree) > 0)
echo '';
foreach($tree as $node)
echo '- '.$node['name'];
printTree($node['children']);
echo '
';
echo '
';
Y el uso real:
$result = parseTree($tree);
printTree($result);
Aquí está el contenido de $result
:
Array(
[0] => Array(
[name] => D
[children] => Array(
[0] => Array(
[name] => G
[children] => Array(
[0] => Array(
[name] => H
[children] => NULL
)
[1] => Array(
[name] => F
[children] => NULL
)
)
)
[1] => Array(
[name] => E
[children] => Array(
[0] => Array(
[name] => A
[children] => NULL
)
[1] => Array(
[name] => C
[children] => Array(
[0] => Array(
[name] => B
[children] => NULL
)
)
)
)
)
)
)
)
Si desea un poco más de eficiencia, puede combinar esas funciones en una y reducir la cantidad de iteraciones realizadas:
function parseAndPrintTree($root, $tree)
$return = array();
if(!is_null($tree) && count($tree) > 0)
echo '';
foreach($tree as $child => $parent)
if($parent == $root)
unset($tree[$child]);
echo '- '.$child;
parseAndPrintTree($child, $tree);
echo '
';
echo '
';
Solo guardará 8 iteraciones en un conjunto de datos tan pequeño como este, pero en conjuntos más grandes podría marcar la diferencia.
Otra función más para hacer un árbol (sin recursividad involucrada, usa referencias en su lugar):
$array = array('H' => 'G', 'F' => 'G', ..., 'D' => null);
function to_tree($array)
$flat = array();
$tree = array();
foreach ($array as $child => $parent)
if (!isset($flat[$child]))
$flat[$child] = array();
if (!empty($parent))
$flat[$parent][$child] =& $flat[$child];
else
$tree[$child] =& $flat[$child];
return $tree;
Devuelve una matriz jerárquica como esta:
Array(
[D] => Array(
[G] => Array(
[H] => Array()
[F] => Array()
)
...
)
)
Que se puede imprimir fácilmente como una lista HTML usando la función recursiva.
Otra forma más simplificada de convertir la estructura plana en el $tree
en una jerarquía. Solo se necesita una matriz temporal para exponerlo:
// add children to parents
$flat = array(); # temporary array
foreach ($tree as $name => $parent)
$flat[$name]['name'] = $name; # self
if (NULL === $parent)
# no parent, is root element, assign it to $tree
$tree = &$flat[$name];
else
# has parent, add self as child
$flat[$parent]['children'][] = &$flat[$name];
unset($flat);
Eso es todo para colocar la jerarquía en una matriz multidimensional:
Array
(
[children] => Array
(
[0] => Array
(
[children] => Array
(
[0] => Array
(
[name] => H
)
[1] => Array
(
[name] => F
)
)
[name] => G
)
[1] => Array
(
[name] => E
[children] => Array
(
[0] => Array
(
[name] => A
)
[1] => Array
(
[children] => Array
(
[0] => Array
(
[name] => B
)
)
[name] => C
)
)
)
)
[name] => D
)
El resultado es menos trivial si desea evitar la recursividad (puede ser una carga con estructuras grandes).
Siempre quise resolver el “dilema” de UL / LI para generar una matriz. El dilema es que cada elemento no sabe si los niños seguirán o no o cuántos elementos precedentes deben cerrarse. En otra respuesta ya lo resolví usando un RecursiveIteratorIterator
y buscando getDepth()
y otra metainformación que he escrito Iterator
proporcionado: Obtener el modelo de conjunto anidado en un
- pero ocultando subárboles “cerrados”. Esa respuesta también muestra que con los iteradores eres bastante flexible.
TreeNode
– Resume cada elemento en un simpleTreeNode
tipo que puede proporcionar su valor (p. ej.Name
) y si tiene hijos o no.TreeNodesIterator
– ARecursiveIterator
que es capaz de iterar sobre un conjunto (matriz) de estosTreeNodes
. Eso es bastante simple como elTreeNode
type ya sabe si tiene hijos y cuáles.RecursiveListIterator
– ARecursiveIteratorIterator
que tiene todos los eventos necesarios cuando itera de forma recursiva sobre cualquier tipo deRecursiveIterator
:beginIteration
/endIteration
– Comienzo y final de la lista principal.beginElement
/endElement
– Comienzo y final de cada elemento.beginChildren
/endChildren
– Comienzo y final de cada lista de niños. EstaRecursiveListIterator
solo proporciona estos eventos en forma de llamadas a funciones. listas de niños, como es típico deendElement
El evento se dispara después de que el acuerdoendChildren
evento. Esto podría cambiarse o configurarse para ampliar el uso de esta clase. Los eventos se distribuyen como llamadas de función a un objeto decorador para mantener las cosas separadas.
ListDecorator
– Una clase de “decorador” que es solo un receptor de los eventos deRecursiveListIterator
.
Sin embargo, esa era una lista ordenada previamente, por lo que no sería adecuada para su ejemplo. Además, siempre quise resolver esto para una especie de estructura de árbol estándar y HTML
- y
elementos.
El concepto básico que se me ocurrió es el siguiente:
Empiezo con la lógica de salida principal. Tomado el ahora jerárquico $tree
matriz, el código final se parece a lo siguiente:
$root = new TreeNode($tree);
$it = new TreeNodesIterator(array($root));
$rit = new RecursiveListIterator($it);
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);
foreach($rit as $item)
$inset = $decor->inset(1);
printf("%s%sn", $inset, $item->getName());
Primero echemos un vistazo a la ListDecorator
que simplemente envuelve el
- y
elementos y está decidiendo cómo se genera la estructura de la lista:
class ListDecorator
private $iterator;
public function __construct(RecursiveListIterator $iterator)
$this->iterator = $iterator;
public function inset($add = 0)
return str_repeat(' ', $this->iterator->getDepth()*2+$add);
El constructor toma el iterador de lista en el que está trabajando. inset
es solo una función auxiliar para una buena sangría de la salida. El resto son solo las funciones de salida para cada evento:
public function beginElement()
printf("%sn", $this->inset());
public function endElement()
printf("%s n", $this->inset());
public function beginChildren()
printf("%sn", $this->inset(-1));
public function endChildren()
printf("%s
n", $this->inset(-1));
public function beginIteration()
printf("%sn", $this->inset());
public function endIteration()
printf("%s
n", $this->inset());
Con estas funciones de salida en mente, este es el resumen / bucle de salida principal nuevamente, lo reviso paso a paso:
$root = new TreeNode($tree);
Crea la raíz TreeNode
que se utilizará para iniciar la iteración en:
$it = new TreeNodesIterator(array($root));
Esta TreeNodesIterator
es un RecursiveIterator
que permite la iteración recursiva sobre el único $root
nodo. Se pasa como una matriz porque esa clase necesita algo sobre lo que iterar y permite la reutilización con un conjunto de elementos secundarios que también es una matriz de TreeNode
elementos.
$rit = new RecursiveListIterator($it);
Esta RecursiveListIterator
es un RecursiveIteratorIterator
que proporciona dichos eventos. Para hacer uso de él, solo un ListDecorator
debe ser proporcionado (la clase anterior) y asignado con addDecorator
:
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);
Entonces todo está configurado para foreach
sobre él y la salida de cada nodo:
foreach($rit as $item)
$inset = $decor->inset(1);
printf("%s%sn", $inset, $item->getName());
Como muestra este ejemplo, toda la lógica de salida está encapsulada en el ListDecorator
clase y este single foreach
. Todo el recorrido recursivo se ha encapsulado completamente en iteradores recursivos SPL que proporcionaron un procedimiento apilado, lo que significa que internamente no se realizan llamadas a funciones recursivas.
El evento basado ListDecorator
le permite modificar la salida específicamente y proporcionar varios tipos de listas para la misma estructura de datos. Incluso es posible cambiar la entrada ya que los datos de la matriz se han encapsulado en TreeNode
.
El ejemplo de código completo:
'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null);
// add children to parents
$flat = array(); # temporary array
foreach ($tree as $name => $parent)
$flat[$name]['name'] = $name; # self
if (NULL === $parent)
# no parent, is root element, assign it to $tree
$tree = &$flat[$name];
else
# has parent, add self as child
$flat[$parent]['children'][] = &$flat[$name];
unset($flat);
class TreeNode
protected $data;
public function __construct(array $element)
if (!isset($element['name']))
throw new InvalidArgumentException('Element has no name.');
if (isset($element['children']) && !is_array($element['children']))
throw new InvalidArgumentException('Element has invalid children.');
$this->data = $element;
public function getName()
return $this->data['name'];
public function hasChildren()
return isset($this->data['children']) && count($this->data['children']);
/**
* @return array of child TreeNode elements
*/
public function getChildren()
$children = $this->hasChildren() ? $this->data['children'] : array();
$class = get_called_class();
foreach($children as &$element)
$element = new $class($element);
unset($element);
return $children;
class TreeNodesIterator implements RecursiveIterator
private $nodes;
public function __construct(array $nodes)
$this->nodes = new ArrayIterator($nodes);
public function getInnerIterator()
return $this->nodes;
public function getChildren()
return new TreeNodesIterator($this->nodes->current()->getChildren());
public function hasChildren()
return $this->nodes->current()->hasChildren();
public function rewind()
$this->nodes->rewind();
public function valid()
return $this->nodes->valid();
public function current()
return $this->nodes->current();
public function key()
return $this->nodes->key();
public function next()
return $this->nodes->next();
class RecursiveListIterator extends RecursiveIteratorIterator
private $elements;
/**
* @var ListDecorator
*/
private $decorator;
public function addDecorator(ListDecorator $decorator)
$this->decorator = $decorator;
public function __construct($iterator, $mode = RecursiveIteratorIterator::SELF_FIRST, $flags = 0)
parent::__construct($iterator, $mode, $flags);
private function event($name)
// event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)n", $name, $this->getDepth(), @$this->elements[$this->getDepth()]);
$callback = array($this->decorator, $name);
is_callable($callback) && call_user_func($callback);
public function beginElement()
$this->event('beginElement');
public function beginChildren()
$this->event('beginChildren');
public function endChildren()
$this->testEndElement();
$this->event('endChildren');
private function testEndElement($depthOffset = 0)
$this->elements[$depth] = 0;
$this->elements[$depth] && $this->event('endElement');
public function nextElement()
$this->testEndElement();
$this->event('nextElement');
$this->event('beginElement');
$this->elements[$this->getDepth()] = 1;
public function beginIteration()
$this->event('beginIteration');
public function endIteration()
$this->testEndElement();
$this->event('endIteration');
class ListDecorator
private $iterator;
public function __construct(RecursiveListIterator $iterator)
$this->iterator = $iterator;
public function inset($add = 0)
return str_repeat(' ', $this->iterator->getDepth()*2+$add);
public function beginElement()
printf("%sn", $this->inset(1));
public function endElement()
printf("%s n", $this->inset(1));
public function beginChildren()
printf("%sn", $this->inset());
public function endChildren()
printf("%s
n", $this->inset());
public function beginIteration()
printf("%sn", $this->inset());
public function endIteration()
printf("%s
n", $this->inset());
$root = new TreeNode($tree);
$it = new TreeNodesIterator(array($root));
$rit = new RecursiveListIterator($it);
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);
foreach($rit as $item)
$inset = $decor->inset(2);
printf("%s%sn", $inset, $item->getName());
Outpupt:
-
D
-
G
-
H
-
F
-
E
-
A
-
C
-
B
Demostración (variante PHP 5.2)
Una posible variante sería un iterador que itera sobre cualquier RecursiveIterator
y proporciona una iteración sobre todos los eventos que pueden ocurrir. Un interruptor / caso dentro del bucle foreach podría lidiar con los eventos.
Relacionado:
- Lista anidada con RecursiveArrayIterator
- La clase RecursiveIteratorIterator
Te invitamos a añadir valor a nuestro contenido informacional asistiendo con tu experiencia en las anotaciones.