Converter uma série de relacionamentos pai-filho em uma árvore hierárquica?

100

Eu tenho um monte de pares de nomes-pais, que gostaria de transformar no menor número possível de estruturas de árvore hierárquicas. Por exemplo, estes podem ser os pares:

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

Que precisa ser transformada em (a) árvore (s) hierárquica (s):

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

O resultado final que desejo é um conjunto aninhado de <ul>elementos, cada um <li>contendo o nome da criança.

Não há inconsistências nos pares (filho é seu próprio pai, pai é filho do filho, etc.), portanto, um monte de otimizações podem ser feitas.

Como, em PHP, eu iria de um array contendo child => pares parentais para um conjunto de Nested <ul>s?

Tenho a sensação de que há recursividade envolvida, mas não estou bem acordado para pensar a respeito.

Eric
fonte

Respostas:

129

Isso requer uma função recursiva muito básica para analisar os pares filho / pai em uma estrutura de árvore e outra função recursiva para imprimi-la. Apenas uma função seria suficiente, mas aqui estão duas para maior clareza (uma função combinada pode ser encontrada no final desta resposta).

Inicialize primeiro a matriz de pares filho / pai:

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

Em seguida, a função que analisa essa matriz em uma estrutura de árvore hierá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;    
}

E uma função que atravessa essa árvore para imprimir uma lista não ordenada:

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>';
    }
}

E o uso real:

$result = parseTree($tree);
printTree($result);

Aqui está o conteúdo 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
                            )
                        )
                    )
                )
            )
        )
    )
)

Se você quiser um pouco mais de eficiência, pode combinar essas funções em uma e reduzir o número de iterações feitas:

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>';
    }
}

Você salvará apenas 8 iterações em um conjunto de dados tão pequeno quanto este, mas em conjuntos maiores isso pode fazer a diferença.

Tatu Ulmanen
fonte
2
Tatu. Como eu poderia alterar a função printTree para não ecoar diretamente o html da árvore, mas salvar todo o html de saída em uma variável e retorná-lo? obrigado
Enrique
Olá, acho que a declaração da função deve ser parseAndPrintTree ($ tree, $ root = null) e a chamada recursiva deve ser parseAndPrintTree ($ child, $ tree); Atenciosamente
razor7
55

Outra função para fazer uma árvore (sem recursão envolvida, usa referências em vez disso):

$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;
}

Retorna uma matriz hierárquica como esta:

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

Que pode ser facilmente impressa como uma lista HTML usando a função recursiva.

Alexander Konstantinov
fonte
+1 - Muito inteligente. Embora eu ache a solução recursiva mais lógica. Mas eu prefiro o formato de saída de sua função.
Eric
@Eric mais lógico? Eu peço desculpa mas não concordo. Não há nada "lógico" na recursão; há OTOH uma sobrecarga cognitiva severa na análise de funções / chamadas recursivas. Se não houver alocação de pilha explícita, faria iteração sobre recursão todos os dias.
29

Outra maneira mais simplificada de converter a estrutura plana do $treeem uma hierarquia. Apenas uma matriz temporária é necessária para expô-lo:

// 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);

Isso é tudo para obter a hierarquia em uma 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
)

A saída é menos trivial se você quiser evitar a recursão (pode ser um fardo com estruturas grandes).

Sempre quis resolver o "dilema" UL / LI para gerar uma matriz. O dilema é que cada item não sabe se os filhos farão o acompanhamento ou não ou quantos elementos precedentes precisam ser encerrados. Em outra resposta, já resolvi isso usando um RecursiveIteratorIteratore procurando getDepth()e outras meta-informações Iteratorfornecidas por mim : Colocando o modelo de conjunto aninhado em um, <ul>mas ocultando subárvores “fechadas” . Essa resposta mostra também que, com iteradores, você é bastante flexível.

No entanto, essa era uma lista pré-classificada, portanto, não seria adequada para o seu exemplo. Além disso, sempre quis resolver isso para uma espécie de estrutura de árvore padrão e HTMLs <ul>e <li>elementos.

O conceito básico que criei é o seguinte:

  1. TreeNode- Abstrai cada elemento em um TreeNodetipo simples que pode fornecer seu valor (por exemplo Name) e se ele tem ou não filhos.
  2. TreeNodesIterator- Um RecursiveIteratorque é capaz de iterar sobre um conjunto (array) desses TreeNodes. Isso é bastante simples, pois o TreeNodetipo já sabe se tem filhos e quais.
  3. RecursiveListIterator- A RecursiveIteratorIteratorque tem todos os eventos necessários quando itera recursivamente sobre qualquer tipo de RecursiveIterator:
    • beginIteration/ endIteration- Início e fim da lista principal.
    • beginElement/ endElement- Início e fim de cada elemento.
    • beginChildren/ endChildren- Início e fim de cada lista de filhos. Isso RecursiveListIteratorsó fornece esses eventos na forma de chamadas de função. listas filhas, como é típico para <ul><li>listas, são abertas e fechadas dentro de seu <li>elemento pai . Portanto, o endElementevento é disparado após o endChildrenevento correspondente. Isso pode ser alterado ou configurado para ampliar o uso dessa classe. Os eventos são distribuídos como chamadas de função para um objeto decorador, para manter as coisas separadas.
  4. ListDecorator- Uma classe "decorador" que é apenas um receptor dos eventos de RecursiveListIterator.

Eu começo com a lógica de saída principal. Considerando a $treematriz agora hierárquica , o código final se parece com o seguinte:

$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());
}

Olhar Primeiro vamos para o ListDecoratorque simplesmente envolve os <ul>e <li>elementos e é decidir sobre a forma como a estrutura da lista é a saída:

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);
    }

O construtor pega o iterador de lista no qual está trabalhando. inseté apenas uma função auxiliar para uma boa indentação da saída. O resto são apenas as funções de saída 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());
    }
}

Com essas funções de saída em mente, este é o resumo / loop de saída principal novamente, passo a passo:

$root = new TreeNode($tree);

Crie a raiz TreeNodeque será usada para iniciar a iteração em:

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

Este TreeNodesIteratoré um RecursiveIteratorque permite a iteração recursiva sobre o único $rootnó. É passado como um array porque essa classe precisa de algo para iterar e permite a reutilização com um conjunto de filhos que também é um array de TreeNodeelementos.

$rit = new RecursiveListIterator($it);

Este RecursiveListIteratoré um RecursiveIteratorIteratorque fornece os referidos eventos. Para fazer uso dele, apenas um ListDecoratorprecisa ser fornecido (a classe acima) e atribuído com addDecorator:

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

Em seguida, tudo é configurado para apenas foreachsobre ele e a saída de cada nó:

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

Como mostra este exemplo, toda a lógica de saída é encapsulada na ListDecoratorclasse e neste único foreach. Todo o percurso recursivo foi totalmente encapsulado em iteradores recursivos SPL que forneceram um procedimento empilhado, o que significa que internamente nenhuma chamada de função de recursão é feita.

O evento baseado em ListDecoratorpermite que você modifique a saída especificamente e forneça vários tipos de listas para a mesma estrutura de dados. É ainda possível alterar a entrada conforme os dados do array foram encapsulados em TreeNode.

O exemplo 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>

Demonstração (variante do PHP 5.2)

Uma possível variante seria um iterador que itera sobre qualquer um RecursiveIteratore fornece uma iteração sobre todos os eventos que podem ocorrer. Um switch / case dentro do loop foreach poderia então lidar com os eventos.

Relacionado:

hakre
fonte
3
Por mais "bem projetada" que essa solução seja - exatamente como ela é "mais simplificada" do que os exemplos anteriores - parece apenas uma solução exagerada para o mesmo problema
André
@Andre: Pelo grau de encapsulamento IIRC. Em outra resposta relacionada, tenho um fragmento de código totalmente não encapsulado que é muito menor e pode, portanto, ser "mais simplificado" dependendo do POV.
hakre,
@hakre Como posso modificar a classe "ListDecorator" para adicionar 'id' ao LI, que está sendo obtido da matriz da árvore?
Gangesh
1
@Gangesh: Mais facilmente com um vistor de nó. ^^ Brincando um pouco, direto é estender o decorador e editar beginElement (), obter o iterador interno (veja o método inset () para um exemplo) e o trabalho com o atributo id.
hakre
@hakre Obrigado. Vou tentar isso.
Gangesh
8

Bem, primeiro eu transformaria a matriz direta de pares de valores-chave em uma matriz hierá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];
}

Isso pode converter uma matriz plana com parent_id e id em uma hierá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(),
                ),
            ),
        ),
    ),
);

Em seguida, basta criar uma função de renderização:

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
fonte
5

Enquanto Alexander-Konstantinov a solução de possa não parecer tão fácil de ler no início, ela é genial e exponencialmente melhor em termos de desempenho, ela deveria ter sido votada como a melhor resposta.

Obrigado colega, fiz um benchmark em sua homenagem para comparar as 2 soluções apresentadas neste post.

Eu tinha uma árvore plana do @ 250k com 6 níveis que precisava converter e estava procurando a melhor maneira de fazer isso e evitar iterações recursivas.

Recursão vs referência:

// 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;

O resultado fala por si:

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

Bem, para analisar em ULs e LIs, seria 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>';
}

Mas adoraria ver uma solução que não exija que você repita o array com tanta frequência ...

Arnorhs
fonte
2

Aqui está o que eu inventei:

$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
      }
    }

saídas:

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

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

Matriz aninhada de relacionamento pai-filho
Busca todos os registros do banco de dados e cria uma matriz aninhada.

$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 dados de categorias e subcategorias em 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
    ];
}
Akshay Mistry
fonte
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 ($ tree);

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
fonte
0

Pergunta antiga, mas eu também tive que fazer isso e os exemplos com recursão me deram dor de cabeça. Em meu banco de dados, temos uma locationstabela, que era um loca_idPK (Criança) e autorreferenciada loca_parent_id(Pai).

O objetivo é representar essa estrutura em HTML. A consulta simples pode, claro, retornar os dados em alguma ordem fixa, mas não achei bem o suficiente para exibir esses dados de uma forma natural. O que eu realmente queria era o Oracle tree walk LEVELpara ajudar na exibição.

Decidi usar a ideia de um 'caminho' para identificar de forma única cada entrada. Por exemplo:

Classificar a matriz pelo caminho deve facilitar o processamento para uma exibição significativa.

Percebo que o uso de matrizes e classificações associativas é enganoso, pois esconde a complexidade recursiva das operações, mas para mim isso parece mais simples:

<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
fonte
-1

Como criar menu e visualização em árvore dinâmica

Etapa 1: Primeiro, criaremos uma tabela treeview no banco de dados mysql. esta tabela contém quatro column.id é o id da tarefa e name é o nome da tarefa.

-
-- 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');

Etapa 2: Método recursivo de visualização em árvore que criei abaixo do método createTreeView () de árvore que chama recursivo se o id da tarefa atual for maior do que o id da tarefa 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> ";

}

Etapa 3: Crie um arquivo de índice para mostrar a visualização em árvore. Este é o arquivo principal do exemplo de treeview. Aqui, chamaremos o método createTreeView () com os parâmetros necessários.

 <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>

Etapa 4: Criar o arquivo CSS style.css Aqui, escreveremos todas as classes relacionadas ao CSS, atualmente estou usando a lista de pedidos para criar a visualização em árvore. você também pode alterar o caminho da imagem aqui.

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 */ }

Mais detalhes


fonte