Saltar al contenido

¿Convertir una serie de relaciones entre padres e hijos en un árbol jerárquico?

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.

    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:

      1. TreeNode – Resume cada elemento en un simple TreeNode tipo que puede proporcionar su valor (p. ej. Name) y si tiene hijos o no.
      2. TreeNodesIterator – A RecursiveIterator que es capaz de iterar sobre un conjunto (matriz) de estos TreeNodes. Eso es bastante simple como el TreeNode type ya sabe si tiene hijos y cuáles.
      3. RecursiveListIterator – A RecursiveIteratorIterator que tiene todos los eventos necesarios cuando itera de forma recursiva sobre cualquier tipo de RecursiveIterator:
        • 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. Esta RecursiveListIterator solo proporciona estos eventos en forma de llamadas a funciones. listas de niños, como es típico de
          • listas, se abren y cierran dentro de su padre
          • elemento. Por lo tanto, el endElement El evento se dispara después de que el acuerdo endChildren 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 de RecursiveListIterator.

      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("%s
      • n", $this->inset()); public function endElement() printf("%s
      • n", $this->inset()); public function beginChildren() printf("%s
          n", $this->inset(-1)); public function endChildren() printf("%s
        n", $this->inset(-1)); public function beginIteration() printf("%s
          n", $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("%s
      • n", $this->inset(1)); public function endElement() printf("%s
      • n", $this->inset(1)); public function beginChildren() printf("%s
          n", $this->inset()); public function endChildren() printf("%s
        n", $this->inset()); public function beginIteration() printf("%s
          n", $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.

        ¡Haz clic para puntuar esta entrada!
        (Votos: 0 Promedio: 0)



        Utiliza Nuestro Buscador

        Deja una respuesta

        Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *