Konwertować serię relacji rodzic-dziecko w hierarchiczne drzewo?

Mam kilka par nazwa-nazwa nadrzędna, które chciałbym przekształcić w jak najmniej heirarchicznych struktur drzewiastych. Na przykład mogą to być pary:

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

Które należy przekształcić w (a) drzewo (drzewa) heirarchiczne:

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

Wynik końcowy, którego szukam, to zagnieżdżony zestaw <ul>elementów, z których każdy <li>zawiera imię dziecka.

W parach nie ma niespójności (dziecko jest własnym rodzicem, rodzic jest dzieckiem itp.), Więc prawdopodobnie można wprowadzić kilka optymalizacji.

Jak w PHP miałbym przejść od tablicy zawierającej pary child => parent do zbioru zagnieżdżonych <ul>s?

Mam wrażenie, że w grę wchodzi rekurencja, ale nie jestem wystarczająco przytomny, aby to przemyśleć.

Wymaga to bardzo podstawowej funkcji rekurencyjnej do przeanalizowania par dziecko / rodzic do struktury drzewa i innej funkcji rekurencyjnej do jej wydrukowania. Wystarczyłaby tylko jedna funkcja, ale dla jasności są dwie (połączoną funkcję można znaleźć na końcu tej odpowiedzi).

Najpierw zainicjalizuj tablicę par dziecko / rodzic:

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

Następnie funkcja, która analizuje tę tablicę w hierarchiczną strukturę drzewa:

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

I funkcja, która przechodzi przez to drzewo, aby wydrukować nieuporządkowaną listę:

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

A rzeczywiste użycie:

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

Oto zawartość $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
                            )
                        )
                    )
                )
            )
        )
    )
)

Jeśli chcesz nieco większej wydajności, możesz połączyć te funkcje w jedną i zmniejszyć liczbę wykonywanych iteracji:

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

Zaoszczędzisz tylko 8 iteracji na tak małym zbiorze danych, ale w przypadku większych zestawów może to mieć znaczenie.

Jeszcze inna funkcja do tworzenia drzewa (bez rekursji, zamiast tego używa odwołań):

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

Zwraca hierarchiczną tablicę, taką jak ta:

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

Które można łatwo wydrukować jako listę HTML za pomocą funkcji rekurencyjnej.

Kolejny, bardziej uproszczony sposób na przekształcenie płaskiej struktury w $treehierarchię. Do jej udostępnienia potrzebna jest tylko jedna tymczasowa tablica:

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

To wszystko, aby uzyskać hierarchię w wielowymiarowej tablicy:

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
)

Wynik jest mniej trywialny, jeśli chcesz uniknąć rekursji (może być obciążeniem przy dużych strukturach).

Zawsze chciałem rozwiązać „dylemat” UL / LI dotyczący wyprowadzania tablicy. Dylemat polega na tym, że każda pozycja nie wie, czy dzieci będą kontynuowały lub ile elementów poprzedzających należy zamknąć. W innej odpowiedzi już to rozwiązałem, używając RecursiveIteratorIteratorszukania getDepth()a i innych metainformacji, które dostarczył mój własny Iterator: Przekształcanie zagnieżdżonego modelu zbioru w <ul>ale ukrywające „zamknięte” poddrzewa . Ta odpowiedź pokazuje również, że dzięki iteratorom jesteś dość elastyczny.

Jednak była to wstępnie posortowana lista, więc nie byłaby odpowiednia dla twojego przykładu. Dodatkowo zawsze chciałem rozwiązać to dla pewnego rodzaju standardowej struktury drzewa oraz HTML <ul>i <li>elementów.

Podstawowa koncepcja, którą wymyśliłem, jest następująca:

1. TreeNode- Abstrahuje każdy element do prostego TreeNodetypu, który może zapewnić jego wartość (np. Name) I określa, czy ma on dzieci.
2. TreeNodesIterator- A RecursiveIteratorktóra jest w stanie wykonać iterację po zestawie (tablicy) tych TreeNodes. Jest to dość proste, ponieważ TreeNodetyp już wie, czy ma dzieci i które z nich.
3. RecursiveListIterator- A, RecursiveIteratorIteratorktóra zawiera wszystkie potrzebne zdarzenia, gdy rekurencyjnie wykonuje iterację dowolnego rodzaju RecursiveIterator:
   • beginIteration/ endIteration- Początek i koniec głównej listy.
   • beginElement/ endElement- Początek i koniec każdego elementu.
   • beginChildren/ endChildren- Początek i koniec każdej listy dzieci. Zapewnia to RecursiveListIteratortylko te zdarzenia w postaci wywołań funkcji. listy dzieci, jak to jest typowe dla <ul><li>list, są otwierane i zamykane wewnątrz <li>elementu nadrzędnego . Dlatego endElementzdarzenie jest uruchamiane po odpowiednim endChildrenzdarzeniu. Można to zmienić lub skonfigurować w celu rozszerzenia zastosowania tej klasy. Zdarzenia są następnie dystrybuowane jako wywołania funkcji do obiektu dekoratora, aby oddzielić rzeczy.
4. ListDecorator- Klasa „dekorator” będąca tylko odbiorcą wydarzeń z RecursiveListIterator.

Zacznę od głównej logiki wyjściowej. Biorąc pod uwagę hierarchiczną $treetablicę now , ostateczny kod wygląda następująco:

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

Wygląd Zacznijmy Into the ListDecoratorże po prostu opakowuje <ul>i <li>elementy i decyduje o tym, jak struktura lista jest wyjście:

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

Konstruktor pobiera iterator listy, nad którym pracuje. insetjest tylko funkcją pomocniczą do ładnego wcięcia danych wyjściowych. Reszta to tylko funkcje wyjściowe dla każdego zdarzenia:

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

Mając na uwadze te funkcje wyjściowe, jest to ponownie główne zawijanie / pętla wyjścia, przechodzę przez to krok po kroku:

$root = new TreeNode($tree);

Utwórz root, TreeNodektóry będzie używany do rozpoczęcia iteracji po:

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

To TreeNodesIteratorjest, RecursiveIteratorktóre umożliwia rekurencyjną iterację w pojedynczym $rootwęźle. Jest przekazywana jako tablica, ponieważ ta klasa wymaga czegoś do iteracji i umożliwia ponowne użycie z zestawem elementów potomnych, który jest również tablicą TreeNodeelementów.

$rit = new RecursiveListIterator($it);

To RecursiveListIteratorjest, RecursiveIteratorIteratorktóre zapewnia wspomniane zdarzenia. Aby z niego skorzystać, wystarczy ListDecoratorpodać (klasę powyżej) i przypisać addDecorator:

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

Następnie wszystko jest ustawione tak, aby tuż foreachnad nim i wyprowadzało każdy węzeł:

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

Jak pokazuje ten przykład, cała logika wyjściowa jest zawarta w ListDecoratorklasie i tym pojedynczym foreach. Całe przechodzenie rekurencyjne zostało w pełni zahermetyzowane w iteratorach rekurencyjnych SPL, które zapewniały procedurę stosową, co oznacza, że ​​wewnętrznie nie są wykonywane żadne wywołania funkcji rekurencyjnych.

Oparta na zdarzeniach ListDecoratorumożliwia konkretną modyfikację danych wyjściowych i zapewnienie wielu typów list dla tej samej struktury danych. Można nawet zmienić dane wejściowe, gdy dane tablicy zostały hermetyzowane TreeNode.

Przykład pełnego kodu:

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

Demo (wariant PHP 5.2)

Możliwym wariantem byłby iterator, który iteruje po każdym RecursiveIteratori zapewnia iterację po wszystkich zdarzeniach, które mogą wystąpić. Przełącznik / przypadek wewnątrz pętli foreach mógłby wtedy obsługiwać zdarzenia.

Związane z:

• Lista zagnieżdżona z RecursiveArrayIterator
• Klasa RecursiveIteratorIterator

Cóż, najpierw zamieniłbym prostą tablicę par klucz-wartość w tablicę hierarchiczną

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

To może przekonwertować płaską tablicę z parent_id i id na hierarchiczną:

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

Następnie po prostu utwórz funkcję renderującą:

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

Podczas gdy Alexander-Konstantinov może początkowo wydawać się nie tak łatwe do odczytania, jest zarówno genialne, jak i wykładniczo lepsze pod względem wydajności, to powinno zostać uznane za najlepszą odpowiedź.

Dzięki kolego, na twoją cześć wykonałem benchmark, aby porównać 2 rozwiązania przedstawione w tym poście.

Miałem płaskie drzewo @ 250k z 6 poziomami, które musiałem przekonwertować i szukałem lepszego sposobu, aby to zrobić i uniknąć rekurencyjnych iteracji.

Rekursja a odniesienie:

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

Wynik mówi sam za siebie:

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

Cóż, aby przeanalizować UL i LI, byłoby to coś takiego:

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

Ale chciałbym zobaczyć rozwiązanie, które nie wymaga tak częstego iterowania tablicy ...

Oto co wymyśliłem:

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

wyjścia:

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

            [E] => Array
                (
                    [A] => A
                    [C] => Array
                        (
                            [B] => B
                        )    
                )    
        )    
)

Zagnieżdżona relacja rodzic-dziecko Tablica
Pobieranie całego rekordu z bazy danych i tworzenie tablicy zagnieżdżonej.

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

Drukuj dane kategorii i podkategorii w formacie 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
    ];
}

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

Stare pytanie, ale ja też musiałem to zrobić, a przykłady z rekurencją przyprawiały mnie o ból głowy. W mojej bazie danych mamy locationstabelę, która była loca_idPK (Child) i odwoływała się do siebie loca_parent_id(Parent).

Celem jest przedstawienie tej struktury w HTML. Proste zapytanie couyrse może zwrócić dane w ustalonym porządku, ale nie znalazłem wystarczająco dobrze, aby wyświetlić takie dane w naturalny sposób. To, czego naprawdę chciałem, to obsługa chodzenia po drzewach OracleLEVEL aby pomóc w wyświetlaniu.

Zdecydowałem się wykorzystać ideę „ścieżki”, aby jednoznacznie zidentyfikować każdy wpis. Na przykład:

Posortowanie tablicy według ścieżki powinno ułatwić przetwarzanie w celu uzyskania sensownego wyświetlania.

Zdaję sobie sprawę, że użycie tablic asocjacyjnych i sortowań jest oszustwem, ponieważ ukrywa rekurencyjną złożoność operacji, ale dla mnie wygląda to prościej:

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

Jak stworzyć dynamiczny widok drzewa i menu

Krok 1: Najpierw utworzymy tabelę treeview w bazie danych mysql. ta tabela zawiera cztery kolumny. id to identyfikator zadania, a nazwa to nazwa zadania.

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

Krok 2: Metoda rekurencyjna widoku drzewa Stworzyłem poniżej metodę createTreeView () drzewa, która wywołuje rekursywną, jeśli identyfikator bieżącego zadania jest większy niż identyfikator poprzedniego zadania.

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

}

Krok 3: Utwórz plik indeksu, aby wyświetlić widok drzewa. To jest główny plik przykładu treeview, tutaj wywołamy metodę createTreeView () z wymaganymi parametrami.

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

Krok 4: Utwórz plik CSS style.css Tutaj napiszemy wszystkie klasy związane z CSS, obecnie używam listy zamówień do tworzenia widoku drzewa. możesz także zmienić ścieżkę obrazu tutaj.

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

Więcej szczegółów