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

100

Tengo un montón de pares nombre-nombre del padre, que me gustaría convertir en la menor cantidad posible de estructuras jerárquicas de árbol. Entonces, por ejemplo, estos podrían ser los emparejamientos:

Child : Parent
    H : G
    F : G
    G : D
    E : D
    A : E
    B : C
    C : E
    D : NULL

Que necesita ser transformado en (un) árbol (s) jerárquico:

D
├── E
   ├── A
      └── B
   └── C   
└── G
    ├── F
    └── H

El resultado final que quiero es un conjunto de <ul>elementos anidados , cada uno <li>con el nombre del niño.

No hay inconsistencias en los emparejamientos (el niño es su propio padre, el padre es el hijo del niño, etc.), por lo que probablemente se puedan hacer un montón de optimizaciones.

¿Cómo, en PHP, pasaría de una matriz que contiene pares hijo => padre, a un conjunto de <ul>s anidados ?

Tengo la sensación de que se trata de una recursividad, pero no estoy lo suficientemente despierto para pensar en ello.

Eric
fuente

Respuestas:

129

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 '<ul>';
        foreach($tree as $node) {
            echo '<li>'.$node['name'];
            printTree($node['children']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

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 '<ul>';
        foreach($tree as $child => $parent) {
            if($parent == $root) {                    
                unset($tree[$child]);
                echo '<li>'.$child;
                parseAndPrintTree($child, $tree);
                echo '</li>';
            }
        }
        echo '</ul>';
    }
}

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.

Tatu Ulmanen
fuente
2
Tatu. ¿Cómo podría cambiar la función printTree para que no se haga eco directamente del html del árbol sino que guarde todo el html de salida en una variable y lo devuelva? gracias
Enrique
Hola, creo que la declaración de la función debe ser parseAndPrintTree ($ tree, $ root = null) y la llamada recursiva será parseAndPrintTree ($ child, $ tree); Saludos cordiales
razor7
55

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 utilizando la función recursiva.

Alexander Konstantinov
fuente
+1 - Muy inteligente. Aunque encuentro la solución recursiva más lógica. Pero prefiero el formato de salida de tu función.
Eric
@Eric más lógico? Siento disentir. No hay nada "lógico" en la recursividad; OTOH tiene una sobrecarga cognitiva severa al analizar funciones / llamadas recursivas. Si no hay una asignación de pila explícita, tomaría la iteración sobre la recursividad todos los días.
29

Otra forma más simplificada de convertir la estructura plana $treeen 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 resolví eso usando un RecursiveIteratorIteratory buscando getDepth()y otra metainformación que Iteratorproporcionó mi propio escrito : Obtener un modelo de conjunto anidado en un <ul>subárbol "cerrado" pero oculto . 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 <ul>y <li>elementos.

El concepto básico que se me ocurrió es el siguiente:

  1. TreeNode- Resumen cada elemento en un TreeNodetipo simple que puede proporcionar su valor (por ejemplo Name) y si tiene hijos o no.
  2. TreeNodesIterator- A RecursiveIteratorque puede iterar sobre un conjunto (matriz) de estos TreeNodes. Eso es bastante simple porque el TreeNodetipo ya sabe si tiene hijos y cuáles.
  3. RecursiveListIterator- A RecursiveIteratorIteratorque 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. Esto RecursiveListIteratorsolo proporciona estos eventos en forma de llamadas a funciones. las listas secundarias, como es típico en las <ul><li>listas, se abren y cierran dentro de su <li>elemento padre . Por lo tanto, el endElementevento se dispara después del endChildrenevento correspondiente. 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.
  4. ListDecorator- Una clase "decoradora" que es solo un receptor de los eventos de RecursiveListIterator.

Empiezo con la lógica de salida principal. Tomada la $treematriz ahora jerárquica , 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%s\n", $inset, $item->getName());
}

En primer lugar mirada nos dejó en el ListDecoratorque simplemente se envuelve las <ul>y los <li>elementos y está decidiendo sobre cómo la estructura de la lista de salida es:

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. insetes 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<li>\n", $this->inset());
    }
    public function endElement()
    {
        printf("%s</li>\n", $this->inset());
    }
    public function beginChildren()
    {
        printf("%s<ul>\n", $this->inset(-1));
    }
    public function endChildren()
    {
        printf("%s</ul>\n", $this->inset(-1));
    }
    public function beginIteration()
    {
        printf("%s<ul>\n", $this->inset());
    }
    public function endIteration()
    {
        printf("%s</ul>\n", $this->inset());
    }
}

Con estas funciones de salida en mente, este es el ciclo / resumen de salida principal nuevamente, lo reviso paso a paso:

$root = new TreeNode($tree);

Cree la raíz TreeNodeque se utilizará para iniciar la iteración en:

$it = new TreeNodesIterator(array($root));

Esta TreeNodesIteratores una RecursiveIteratorque permite la iteración recursiva sobre un solo $rootnodo. 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 TreeNodeelementos.

$rit = new RecursiveListIterator($it);

Este RecursiveListIteratores un RecursiveIteratorIteratorque proporciona dichos eventos. Para hacer uso de él, solo es ListDecoratornecesario proporcionar un (la clase anterior) y asignarle addDecorator:

$decor = new ListDecorator($rit);
$rit->addDecorator($decor);

Luego, todo está configurado para pasarlo foreachy generar cada nodo:

foreach($rit as $item)
{
    $inset = $decor->inset(1);
    printf("%s%s\n", $inset, $item->getName());
}

Como muestra este ejemplo, toda la lógica de salida está encapsulada en la ListDecoratorclase 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 de recursividad.

El basado en eventos le ListDecoratorpermite modificar la salida específicamente y proporcionar múltiples tipos de listas para la misma estructura de datos. Incluso es posible cambiar la entrada ya que se han encapsulado los datos de la matriz TreeNode.

El ejemplo de código completo:

<?php
namespace My;

$tree = array('H' => '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)
    {
        $depth = $this->getDepth() + $depthOffset;      
        isset($this->elements[$depth]) || $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<li>\n", $this->inset(1));
    }
    public function endElement()
    {
        printf("%s</li>\n", $this->inset(1));
    }
    public function beginChildren()
    {
        printf("%s<ul>\n", $this->inset());
    }
    public function endChildren()
    {
        printf("%s</ul>\n", $this->inset());
    }
    public function beginIteration()
    {
        printf("%s<ul>\n", $this->inset());
    }
    public function endIteration()
    {
        printf("%s</ul>\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%s\n", $inset, $item->getName());
}

Outpupt:

<ul>
  <li>
    D
    <ul>
      <li>
        G
        <ul>
          <li>
            H
          </li>
          <li>
            F
          </li>
        </ul>
      </li>
      <li>
        E
        <ul>
          </li>
          <li>
            A
          </li>
          <li>
            C
            <ul>
              <li>
                B
              </li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

Demostración (variante PHP 5.2)

Una posible variante sería un iterador que itera sobre cualquiera RecursiveIteratory 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:

hakre
fuente
3
Tan "bien diseñada" como está esta solución, ¿cómo es exactamente "una forma más simplificada" que los ejemplos anteriores? Parece una solución demasiado diseñada para el mismo problema
Andre
@Andre: Por el grado de encapsulación IIRC. En otra respuesta relacionada, tengo un fragmento de código completamente no encapsulado que es mucho más pequeño y, por lo tanto, podría estar "más simplificado" dependiendo de POV.
hakre
@hakre ¿Cómo puedo modificar la clase "ListDecorator" para agregar 'id' a LI, que se está obteniendo de la matriz de árbol?
Gangesh
1
@Gangesh: más fácilmente con un visitante de nodo. ^^ Bromeando un poco, sencillo es extender el decorador y editar beginElement (), obtener el iterador interno (ver el método inset () para un ejemplo) y el trabajo con el atributo id.
hakre
@hakre Gracias. Lo intentaré.
Gangesh
8

Bueno, primero convertiría la matriz directa de pares clave-valor en una matriz jerárquica

function convertToHeiarchical(array $input) {
    $parents = array();
    $root = array();
    $children = array();
    foreach ($input as $item) {
        $parents[$item['id']] = &$item;
        if ($item['parent_id']) {
            if (!isset($children[$item['parent_id']])) {
                $children[$item['parent_id']] = array();
            }
            $children[$item['parent_id']][] = &$item;
        } else {
            $root = $item['id'];
        }
    }
    foreach ($parents as $id => &$item) {
        if (isset($children[$id])) {
            $item['children'] = $children[$id];
        } else {
            $item['children'] = array();
        }
    }
    return $parents[$root];
}

Eso puede convertir una matriz plana con parent_id e id en una jerárquica:

$item = array(
    'id' => 'A',
    'blah' => 'blah',
    'children' => array(
        array(
            'id' => 'B',
            'blah' => 'blah',
            'children' => array(
                array(
                    'id' => 'C',
                    'blah' => 'blah',
                    'children' => array(),
                ),
             ),
            'id' => 'D',
            'blah' => 'blah',
            'children' => array(
                array(
                    'id' => 'E',
                    'blah' => 'blah',
                    'children' => array(),
                ),
            ),
        ),
    ),
);

Luego, simplemente cree una función de renderizado:

function renderItem($item) {
    $out = "Your OUtput For Each Item Here";
    $out .= "<ul>";
    foreach ($item['children'] as $child) {
        $out .= "<li>".renderItem($child)."</li>";
    }
    $out .= "</ul>";
    return $out;
}
ircmaxell
fuente
5

Si bien la solución de Alexander-Konstantinov puede no parecer tan fácil de leer al principio, es genial y exponencialmente mejor en términos de rendimiento, esta debería haber sido votada como la mejor respuesta.

Gracias amigo, hice un benchmark en tu honor para comparar las 2 soluciones presentadas en este post.

Tenía un árbol plano @ 250k con 6 niveles que tenía que convertir y estaba buscando una mejor manera de hacerlo y evitar iteraciones recursivas.

Recurrencia vs referencia:

// Generate a 6 level flat tree
$root = null;
$lvl1 = 13;
$lvl2 = 11;
$lvl3 = 7;
$lvl4 = 5;
$lvl5 = 3;
$lvl6 = 1;    
$flatTree = [];
for ($i = 1; $i <= 450000; $i++) {
    if ($i % 3 == 0)  { $lvl5 = $i; $flatTree[$lvl6] = $lvl5; continue; }
    if ($i % 5 == 0)  { $lvl4 = $i; $flatTree[$lvl5] = $lvl4; continue; }
    if ($i % 7 == 0)  { $lvl3 = $i; $flatTree[$lvl3] = $lvl2; continue; }
    if ($i % 11 == 0) { $lvl2 = $i; $flatTree[$lvl2] = $lvl1; continue; }
    if ($i % 13 == 0) { $lvl1 = $i; $flatTree[$lvl1] = $root; continue; }
    $lvl6 = $i;
}

echo 'Array count: ', count($flatTree), PHP_EOL;

// Reference function
function treeByReference($flatTree)
{
    $flat = [];
    $tree = [];

    foreach ($flatTree as $child => $parent) {
        if (!isset($flat[$child])) {
            $flat[$child] = [];
        }
        if (!empty($parent)) {
            $flat[$parent][$child] =& $flat[$child];
        } else {
            $tree[$child] =& $flat[$child];
        }
    }

    return $tree;
}

// Recursion function
function treeByRecursion($flatTree, $root = null)
{
    $return = [];
    foreach($flatTree as $child => $parent) {
        if ($parent == $root) {
            unset($flatTree[$child]);
            $return[$child] = treeByRecursion($flatTree, $child);
        }
    }
    return $return ?: [];
}

// Benchmark reference
$t1 = microtime(true);
$tree = treeByReference($flatTree);
echo 'Reference: ', (microtime(true) - $t1), PHP_EOL;

// Benchmark recursion
$t2 = microtime(true);
$tree = treeByRecursion($flatTree);
echo 'Recursion: ', (microtime(true) - $t2), PHP_EOL;

La salida habla por sí sola:

Array count: 255493
Reference: 0.3259289264679 (less than 0.4s)
Recursion: 6604.9865279198 (almost 2h)
ntt
fuente
2

Bueno, para analizar UL y LI, sería algo como:

$array = array (
    'H' => 'G'
    'F' => 'G'
    'G' => 'D'
    'E' => 'D'
    'A' => 'E'
    'B' => 'C'
    'C' => 'E'
    'D' => 'NULL'
);


recurse_uls ($array, 'NULL');

function recurse_uls ($array, $parent)
{
    echo '<ul>';
    foreach ($array as $c => $p)  {
        if ($p != $parent) continue;
        echo '<li>'.$c.'</li>';
        recurse_uls ($array, $c);
    }
    echo '</ul>';
}

Pero me encantaría ver una solución que no requiera que recorra la matriz con tanta frecuencia ...

arnorhs
fuente
2

Esto es lo que se me ocurrió:

$arr = array(
            'H' => 'G',
            'F' => 'G',
            'G' => 'D',
            'E' => 'D',
            'A' => 'E',
            'B' => 'C',
            'C' => 'E',
            'D' => null );

    $nested = parentChild($arr);
    print_r($nested);

    function parentChild(&$arr, $parent = false) {
      if( !$parent) { //initial call
         $rootKey = array_search( null, $arr);
         return array($rootKey => parentChild($arr, $rootKey));
      }else { // recursing through
        $keys = array_keys($arr, $parent);
        $piece = array();
        if($keys) { // found children, so handle them
          if( !is_array($keys) ) { // only one child
            $piece = parentChild($arr, $keys);
           }else{ // multiple children
             foreach( $keys as $key ){
               $piece[$key] = parentChild($arr, $key);
             }
           }
        }else {
           return $parent; //return the main tag (no kids)
        }
        return $piece; // return the array built via recursion
      }
    }

salidas:

Array
(
    [D] => Array
        (
            [G] => Array
                (
                    [H] => H
                    [F] => F
                )

            [E] => Array
                (
                    [A] => A
                    [C] => Array
                        (
                            [B] => B
                        )    
                )    
        )    
)
Dan Heberden
fuente
1

Relación padre-hijo Matriz anidada
Obtiene todo el registro de la base de datos y crea una matriz anidada.

$data = SampleTable::find()->all();
$tree = buildTree($data);
print_r($tree);

public function buildTree(array $elements, $parentId = 0) {
    $branch = array();
    foreach ($elements as $element) {
        if ($element['iParentId'] == $parentId) {
            $children =buildTree($elements, $element['iCategoriesId']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[] = $element;
        }
    }
    return $branch;
}

Imprimir datos de categorías y subcategorías en formato json

public static function buildTree(array $elements, $parentId = 0){
    $branch = array();
    foreach($elements as $element){
        if($element['iParentId']==$parentId){
            $children =buildTree($elements, $element['iCategoriesId']);
            if ($children) {
                $element['children'] = $children;

            }
                $branch[] = array(
                    'iCategoriesId' => $element->iCategoriesId,
                    'iParentId'=>$element->iParentId,
                    'vCategoriesName'=>$element->vCategoriesName,
                    'children'=>$element->children,
            );
        }
    }
    return[
        $branch
    ];
}
Mistry Akshay
fuente
0
$tree = array(
    'H' => 'G',
    'F' => 'G',
    'G' => 'D',
    'E' => 'D',
    'A' => 'E',
    'B' => 'C',
    'C' => 'E',
    'D' => null,
    'Z' => null,
    'MM' =>'Z',
    'KK' =>'Z',
    'MMM' =>'MM',
    // 'MM'=>'DDD'
);

$ aa = $ this-> parseTree ($ árbol);

public function get_tress($tree,$key)
{

    $x=array();
    foreach ($tree as $keys => $value) {
        if($value==$key){
        $x[]=($keys);
        }
    }
    echo "<li>";
    foreach ($x as $ke => $val) {
    echo "<ul>";
        echo($val);
        $this->get_tress($tree,$val);
    echo "</ul>";
    }
    echo "</li>";


}
function parseTree($tree, $root = null) {

    foreach ($tree as $key => $value) {
        if($value==$root){

            echo "<ul>";
            echo($key);
            $this->get_tress($tree,$key);
            echo "</ul>";
        }
    }
Bharat
fuente
0

Pregunta vieja, pero yo también tuve que hacer esto y los ejemplos con recursividad me dieron dolor de cabeza. En mi base de datos tenemos una locationstabla, que era un loca_idPK (Child) y una autorreferencia loca_parent_id(Parent).

El objetivo es representar esta estructura en HTML. Por supuesto, la consulta simple puede devolver los datos en un orden fijo, pero no encontré lo suficientemente bien como para mostrar dichos datos de una manera natural. Lo que realmente quería era el manejo del recorrido del árbol de Oracle LEVELpara ayudar con la visualización.

Decidí utilizar la idea de una "ruta" para identificar de forma única cada entrada. Por ejemplo:

Ordenar la matriz por la ruta debería facilitar el proceso para una visualización significativa.

Me doy cuenta de que el uso de matrices y clases asociativas es una trampa, ya que oculta la complejidad recursiva de las operaciones, pero para mí esto parece más simple:

<table>
<?php
    
    $sql = "
    
    SELECT l.*,
           pl.loca_name parent_loca_name,
           '' loca_path
    FROM locations l
    LEFT JOIN locations pl ON l.loca_parent_id = pl.loca_id
    ORDER BY l.loca_parent_id, l.loca_id
    
    ";
    
    function print_row ( $rowdata )
    {
    ?>
                      <tr>
                          <td>
                              <?=$rowdata['loca_id']?>
                          </td>
                          <td>
                              <?=$rowdata['loca_path']?>
                          </td>
                          <td>
                              <?=$rowdata['loca_type']?>
                          </td>
                          <td>
                              <?=$rowdata['loca_status']?>
                          </td>
                      </tr>
    <?php
    
    }
    
    $stmt  = $dbh->prepare($sql);
    $stmt->execute();
    $result = $stmt->get_result();
    $data = $result->fetch_all(MYSQLI_ASSOC);
    
    $printed = array();
    
    // To get tree hierarchy usually means recursion of data.
    // Here we will try to use an associate array and set a
    // 'path' value to represent the hierarchy tree in one
    // pass. Sorting this array by the path value should give
    // a nice tree order and reference.
// The array key will be the unique id (loca_id) for each row.
// The value for each key will the complete row from the database.
// The row contains a element 'loca_path' - we will write the path
// for each row here. A child's path will be parent_path/child_name.
// For any child we encounter with a parent we look up the parents path
// using the loca_parent_id as the key.
// Caveat, although tested quickly, just make sure that all parents are
// returned first by the query.
    
    foreach ($data as $row)
    {
    
       if ( $row['loca_parent_id'] == '' ) // Root Parent
       {
          $row['loca_path'] = $row['loca_name'] . '/';
          $printed[$row['loca_id']] = $row;
       }
       else // Child/Sub-Parent
       {
          $row['loca_path'] = $printed[$row['loca_parent_id']]['loca_path'] . $row['loca_name'] . '/';
          $printed[$row['loca_id']] = $row;
       }
    }
    
    // Array with paths built, now sort then print
    
    array_multisort(array_column($printed, 'loca_path'), SORT_ASC, $printed);
    
    foreach ( $printed as $prow )
    {
       print_row ( $prow );
    }
    ?>
    </table>
TenG
fuente
-1

Cómo crear un menú y una vista de árbol dinámicos

Paso 1: Primero crearemos una tabla de vista de árbol en la base de datos mysql. esta tabla contiene cuatro columnas. id es el id de la tarea y name es el nombre de la tarea.

-
-- Table structure for table `treeview_items`
--

CREATE TABLE IF NOT EXISTS `treeview_items` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(200) NOT NULL,
  `title` varchar(200) NOT NULL,
  `parent_id` varchar(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB  DEFAULT CHARSET=latin1 AUTO_INCREMENT=7 ;

--
-- Dumping data for table `treeview_items`
--

INSERT INTO `treeview_items` (`id`, `name`, `title`, `parent_id`) VALUES
(1, 'task1', 'task1title', '2'),
(2, 'task2', 'task2title', '0'),
(3, 'task3', 'task1title3', '0'),
(4, 'task4', 'task2title4', '3'),
(5, 'task4', 'task1title4', '3'),
(6, 'task5', 'task2title5', '5');

Paso 2: Método recursivo de vista de árbol que he creado debajo del método createTreeView () del árbol que llama recursivo si la identificación de la tarea actual es mayor que la identificación de la tarea anterior.

function createTreeView($array, $currentParent, $currLevel = 0, $prevLevel = -1) {

foreach ($array as $categoryId => $category) {

if ($currentParent == $category['parent_id']) {                       
    if ($currLevel > $prevLevel) echo " <ol class='tree'> "; 

    if ($currLevel == $prevLevel) echo " </li> ";

    echo '<li> <label for="subfolder2">'.$category['name'].'</label> <input type="checkbox" name="subfolder2"/>';

    if ($currLevel > $prevLevel) { $prevLevel = $currLevel; }

    $currLevel++; 

    createTreeView ($array, $categoryId, $currLevel, $prevLevel);

    $currLevel--;               
    }   

}

if ($currLevel == $prevLevel) echo " </li>  </ol> ";

}

Paso 3: Cree un archivo de índice para mostrar la vista de árbol. Este es el archivo principal del ejemplo de vista de árbol. Aquí llamaremos al método createTreeView () con los parámetros requeridos.

 <body>
<link rel="stylesheet" type="text/css" href="_styles.css" media="screen">
<?php
mysql_connect('localhost', 'root');
mysql_select_db('test');


$qry="SELECT * FROM treeview_items";
$result=mysql_query($qry);


$arrayCategories = array();

while($row = mysql_fetch_assoc($result)){ 
 $arrayCategories[$row['id']] = array("parent_id" => $row['parent_id'], "name" =>                       
 $row['name']);   
  }
?>
<div id="content" class="general-style1">
<?php
if(mysql_num_rows($result)!=0)
{
?>
<?php 

createTreeView($arrayCategories, 0); ?>
<?php
}
?>

</div>
</body>

Paso 4: Cree el archivo CSS style.css Aquí escribiremos todas las clases relacionadas con CSS, actualmente estoy usando la lista de pedidos para crear una vista de árbol. también puede cambiar la ruta de la imagen aquí.

img { border: none; }
input, select, textarea, th, td { font-size: 1em; }

/* CSS Tree menu styles */
ol.tree
{
    padding: 0 0 0 30px;
    width: 300px;
}
    li 
    { 
        position: relative; 
        margin-left: -15px;
        list-style: none;
    }
    li.file
    {
        margin-left: -1px !important;
    }
        li.file a
        {
            background: url(document.png) 0 0 no-repeat;
            color: #fff;
            padding-left: 21px;
            text-decoration: none;
            display: block;
        }
        li.file a[href *= '.pdf']   { background: url(document.png) 0 0 no-repeat; }
        li.file a[href *= '.html']  { background: url(document.png) 0 0 no-repeat; }
        li.file a[href $= '.css']   { background: url(document.png) 0 0 no-repeat; }
        li.file a[href $= '.js']        { background: url(document.png) 0 0 no-repeat; }
    li input
    {
        position: absolute;
        left: 0;
        margin-left: 0;
        opacity: 0;
        z-index: 2;
        cursor: pointer;
        height: 1em;
        width: 1em;
        top: 0;
    }
        li input + ol
        {
            background: url(toggle-small-expand.png) 40px 0 no-repeat;
            margin: -0.938em 0 0 -44px; /* 15px */
            height: 1em;
        }
        li input + ol > li { display: none; margin-left: -14px !important; padding-left: 1px; }
    li label
    {
        background: url(folder-horizontal.png) 15px 1px no-repeat;
        cursor: pointer;
        display: block;
        padding-left: 37px;
    }

    li input:checked + ol
    {
        background: url(toggle-small.png) 40px 5px no-repeat;
        margin: -1.25em 0 0 -44px; /* 20px */
        padding: 1.563em 0 0 80px;
        height: auto;
    }
        li input:checked + ol > li { display: block; margin: 0 0 0.125em;  /* 2px */}
        li input:checked + ol > li:last-child { margin: 0 0 0.063em; /* 1px */ }

Más detalles


fuente