creare albero matrice da lista di array

Question

ho una lista come questa:

array(
    array(id=>100, parentid=>0, name=>'a'), 
    array(id=>101, parentid=>100, name=>'a'), 
    array(id=>102, parentid=>101, name=>'a'), 
    array(id=>103, parentid=>101, name=>'a'), 
) 

ma molto più grande quindi ho bisogno di un modo efficace per fare questo in un albero come la struttura come questa:

array(
    id=>100, parentid=>0, name=>'a', children=>array(
    id=>101, parentid=>100, name=>'a', children=>array(
     id=>102, parentid=>101, name=>'a', 
     id=>103, parentid=>101, name=>'a', 
    ) 
) 
) 

Non posso usare cose come il set annidato o cose del genere perché posso aggiungere valori di sinistra e destra nel mio database. qualche idea?

Answer 1

oke è così che ho risolto:

$arr = array(
    array('id'=>100, 'parentid'=>0, 'name'=>'a'), 
    array('id'=>101, 'parentid'=>100, 'name'=>'a'), 
    array('id'=>102, 'parentid'=>101, 'name'=>'a'), 
    array('id'=>103, 'parentid'=>101, 'name'=>'a'), 
); 

$new = array(); 
foreach ($arr as $a){ 
    $new[$a['parentid']][] = $a; 
} 
$tree = createTree($new, array($arr[0])); 
print_r($tree); 

function createTree(&$list, $parent){ 
    $tree = array(); 
    foreach ($parent as $k=>$l){ 
     if(isset($list[$l['id']])){ 
      $l['children'] = createTree($list, $list[$l['id']]); 
     } 
     $tree[] = $l; 
    } 
    return $tree; 
} 

Answer 2

Un modo per farlo è con una funzione ricorsiva che prima trova tutti i valori inferiori della lista, aggiungendoli a una nuova matrice. Quindi, per ogni nuovo id, si utilizza la stessa funzione su quell'id, prendendo l'array restituito e inserendolo nella nuova matrice figli di quell'elemento. Alla fine, restituisci il tuo nuovo array.

Non voglio fare tutto il lavoro per voi, ma i parametri della funzione avrà un aspetto simile:

recursiveChildren funzione ($ items_array, $ parent_id = 0)

Essenzialmente, accorgerete tutto quelli con il genitore di 0, quindi per ognuno di quelli troverà tutti quelli con quell'id come genitore, e per ognuno di quelli .. così via.

Il risultato finale dovrebbe essere quello che stai cercando.

Answer 3

('basandomi mentre a piccole fix se avete bisogno di più di 1 parentid [0] elemento :)

$arr = array(
    array('id'=>100, 'parentid'=>0, 'name'=>'a'), 
    array('id'=>101, 'parentid'=>100, 'name'=>'a'), 
    array('id'=>102, 'parentid'=>101, 'name'=>'a'), 
    array('id'=>103, 'parentid'=>101, 'name'=>'a'), 
); 

$new = array(); 
foreach ($arr as $a){ 
    $new[$a['parentid']][] = $a; 
} 
$tree = createTree($new, $new[0]); // changed 
print_r($tree); 

function createTree(&$list, $parent){ 
    $tree = array(); 
    foreach ($parent as $k=>$l){ 
     if(isset($list[$l['id']])){ 
      $l['children'] = createTree($list, $list[$l['id']]); 
     } 
     $tree[] = $l; 
    } 
    return $tree; 
} 

Answer 4

ho creato un insolito 'invece di ricorsiva) ma multidimensionale funzione di ordinamento che cammina nell'array finché non ci sono orfani. Qui la funzione:

function treeze(&$a, $parent_key, $children_key) 
{ 
    $orphans = true; $i; 
    while($orphans) 
    { 
     $orphans = false; 
     foreach($a as $k=>$v) 
     { 
      // is there $a[$k] sons? 
      $sons = false; 
      foreach($a as $x=>$y) 
      if(isset($y[$parent_key]) and $y[$parent_key]!=false and $y[$parent_key]==$k) 
      { 
       $sons=true; 
       $orphans=true; 
       break; 
      } 

      // $a[$k] is a son, without children, so i can move it 
      if(!$sons and isset($v[$parent_key]) and $v[$parent_key]!=false) 
      { 
       $a[$v[$parent_key]][$children_key][$k] = $v; 
       unset($a[$k]); 
      } 
     } 
    } 
} 

Raccomandazione: la chiave di ciascun elemento della matrice deve essere l'ID fo dell'elemento stesso. Esempio:

$ARRAY = array(
    1 => array('label' => "A"), 
    2 => array('label' => "B"), 
    3 => array('label' => "C"), 
    4 => array('label' => "D"), 
    5 => array('label' => "one", 'father' => '1'), 
    6 => array('label' => "two", 'father' => '1'), 
    7 => array('label' => "three", 'father' => '1'), 
    8 => array('label' => "node 1", 'father' => '2'), 
    9 => array('label' => "node 2", 'father' => '2'), 
    10 => array('label' => "node 3", 'father' => '2'), 
    11 => array('label' => "I", 'father' => '9'), 
    12 => array('label' => "II", 'father' => '9'), 
    13 => array('label' => "III", 'father' => '9'), 
    14 => array('label' => "IV", 'father' => '9'), 
    15 => array('label' => "V", 'father' => '9'), 
); 

Uso: la funzione deve $ a (l'array), $ parent_key (il nome della colonna in cui viene salvato l'id del padre), $ children_key (il nome della colonna in cui i bambini saranno spostati). Non restituisce nulla (la matrice è cambiata per riferimento). Esempio:

treeze($ARRAY, 'father', 'children'); 
echo "<pre>"; print_r($ARRAY); 

Answer 5

Qui è il mio adattamento da arthur's rework:

/* Recursive branch extrusion */ 
function createBranch(&$parents, $children) { 
    $tree = array(); 
    foreach ($children as $child) { 
     if (isset($parents[$child['id']])) { 
      $child['children'] = 
       $this->createBranch($parents, $parents[$child['id']]); 
     } 
     $tree[] = $child; 
    } 
    return $tree; 
} 

/* Initialization */ 
function createTree($flat, $root = 0) { 
    $parents = array(); 
    foreach ($flat as $a) { 
     $parents[$a['parent']][] = $a; 
    } 
    return $this->createBranch($parents, $parents[$root]); 
} 

Usa:

$tree = createTree($flat); 

Answer 6

C'è un motivo questo metodo tre pass non avrebbe funzionato? Non ho fatto alcun test per confrontare la velocità con alcune delle soluzioni ricorsive, ma sembrava più stretto. Se il tuo array iniziale è già associativo con gli ID che rappresentano la chiave, puoi saltare il primo foreach().

function array_tree(&$array) { 
    $tree = array(); 

    // Create an associative array with each key being the ID of the item 
    foreach($array as $k => &$v) $tree[$v['id']] = &$v; 

    // Loop over the array and add each child to their parent 
    foreach($tree as $k => &$v) { 
     if(!$v['parent']) continue; 
     $tree[$v['parent']]['children'][] = &$v; 
    } 

    // Loop over the array again and remove any items that don't have a parent of 0; 
    foreach($tree as $k => &$v) { 
     if(!$v['parent']) continue; 
     unset($tree[$k]); 
    } 

    return $tree; 
} 

Answer 7

Ancora una rilavorazione di Thunderstriker's variant - tutta la logica in una funzione:

function buildTree($flat, $pidKey, $idKey = null) 
{ 
    $grouped = array(); 
    foreach ($flat as $sub){ 
     $grouped[$sub[$pidKey]][] = $sub; 
    } 

    $fnBuilder = function($siblings) use (&$fnBuilder, $grouped, $idKey) { 
     foreach ($siblings as $k => $sibling) { 
      $id = $sibling[$idKey]; 
      if(isset($grouped[$id])) { 
       $sibling['children'] = $fnBuilder($grouped[$id]); 
      } 
      $siblings[$k] = $sibling; 
     } 

     return $siblings; 
    }; 

    $tree = $fnBuilder($grouped[0]); 

    return $tree; 
} 

// Example: 
$flat = [ 
    ['id'=>100, 'parentID'=>0, 'name'=>'a'], 
    ['id'=>101, 'parentID'=>100, 'name'=>'a'], 
    ['id'=>102, 'parentID'=>101, 'name'=>'a'], 
    ['id'=>103, 'parentID'=>101, 'name'=>'a'], 
]; 

$tree = buildTree($flat, 'parentID', 'id'); 
print_r($tree); 

Playground: https://www.tehplayground.com/5V8QSqnmFJ2wcIoj

Answer 8

//if order by parentid, id 
$arr = array(
    array('id'=>100, 'parentid'=>0, 'name'=>'a'), 
    array('id'=>101, 'parentid'=>100, 'name'=>'a'), 
    array('id'=>102, 'parentid'=>101, 'name'=>'a'), 
    array('id'=>103, 'parentid'=>101, 'name'=>'a'), 
); 

$arr_tree = array(); 
$arr_tmp = array(); 

foreach ($arr as $item) { 
    $parentid = $item['parentid']; 
    $id = $item['id']; 

    if ($parentid == 0) 
    { 
     $arr_tree[$id] = $item; 
     $arr_tmp[$id] = &$arr_tree[$id]; 
    } 
    else 
    { 
     if (!empty($arr_tmp[$parentid])) 
     { 
      $arr_tmp[$parentid]['children'][$id] = $item; 
      $arr_tmp[$id] = &$arr_tmp[$parentid]['children'][$id]; 
     } 
    } 
} 

unset($arr_tmp); 
echo '<pre>'; print_r($arr_tree); echo "</pre>";