Sortierung Array abhängig von Eltern; ein Baum in einem eindimensionalen Array

Question

Wie kann ich ein Array mit allen Kindern nach ihren jeweiligen Eltern sortieren? Ich denke, ich versuche, einen Baum in einem eindimensionalen Array zu speichern. Ich habe versucht, dies mit usort herauszufinden, aber ich denke nicht, dass es das richtige Werkzeug für den Job ist.

Beispiel Eingangsarray:

array (0 => array ('id' => '1', 'parent' => '0',), 
1 => array ('id' => '2', 'parent' => '1',), 
2 => array ('id' => '3', 'parent' => '0',), 
3 => array ('id' => '5', 'parent' => '0',), 
4 => array ('id' => '17', 'parent' => '3',), 
5 => array ('id' => '31', 'parent' => '2',), 
6 => array ('id' => '32', 'parent' => '2',)) 

Beispiel Ausgang:

Answer 1

zunächst eine tatsächliche Baumerstellung, dann abzuflachen diesen Baum:

$array = array (0 => array ('id' => '1', 'parent' => '0',), 
       1 => array ('id' => '2', 'parent' => '1',), 
       2 => array ('id' => '3', 'parent' => '0',), 
       3 => array ('id' => '5', 'parent' => '0',), 
       4 => array ('id' => '17', 'parent' => '3',), 
       5 => array ('id' => '31', 'parent' => '2',), 
       6 => array ('id' => '32', 'parent' => '2',)); 

/* Building a tree. We also save a map of references to avoid         
    searching the tree for nodes */ 

//Helper to create nodes                  
$tree_node = function($id, $parent) { 
    return array('id' => $id, 'parent' => $parent, 'children' => array()); 
}; 

$tree = $tree_node(0, null); //root node              
$map = array(0 => &$tree); 
foreach($array as $cur) { 
    $id = (int) $cur['id']; 
    $parentId = (int) $cur['parent']; 
    $map[$id] =& $map[$parentId]['children'][]; 
    $map[$id] = $tree_node($id, $parentId); 
} 

//Now recursively flatten the tree:               
function flatter($node) { 
    //Create an array element of the node            
    $array_element = array('id' => (string) $node['id'], 
         'parent' => (string) $node['parent']); 
    //Add all children after me                 
    $result = array($array_element); 
    foreach($node['children'] as $child) { 
    $result = array_merge($result, flatter($child)); 
    } 
    return $result; 
} 

$array = flatter($tree); 
array_shift($array); //Remove the root node, which was only added as a helper     

print_r($array); 

Answer 2

<?php 

/** 
* @author Prasath A.R 
* @copyright 2012 
* @Date 2012-8-31 17:14 
*/ 

$array = array (0 => array ('id' => '1', 'parent' => '0',), 
       1 => array ('id' => '2', 'parent' => '1',), 
       2 => array ('id' => '3', 'parent' => '0',), 
       3 => array ('id' => '5', 'parent' => '0',), 
       4 => array ('id' => '17', 'parent' => '3',), 
       5 => array ('id' => '31', 'parent' => '2',), 
       6 => array ('id' => '32', 'parent' => '2',)); 

print_r($array); 
echo "<br />"; 

for($i=0;$i<count($array);$i++) 
{ 
for($j=$i;$j<count($array);$j++) 
{ 
     if($array[$i]['parent']>$array[$j]['parent']) 
     { 
      $temp=$array[$i]; 
      $array[$i]=$array[$j]; 
      $array[$j]=$temp; 
     } 
    } 
} 

echo "<h2>After Sorting</h2><br />"; 
print_r($array); 

?> 

Die Antwort wird sein:

Array ( [0] => Array ( [id] => 1 [parent] => 0 )

[1] => Array 
    (
     [id] => 2 
     [parent] => 1 
    ) 

[2] => Array 
    (
     [id] => 3 
     [parent] => 0 
    ) 

[3] => Array 
    (
     [id] => 5 
     [parent] => 0 
    ) 

[4] => Array 
    (
     [id] => 17 
     [parent] => 3 
    ) 

[5] => Array 
    (
     [id] => 31 
     [parent] => 2 
    ) 

[6] => Array 
    (
     [id] => 32 
     [parent] => 2 
    ) 

)

Nach dem Sortieren

Array ( [0] => Array ( [id] => 1 [parent] => 0 )

[1] => Array 
    (
     [id] => 3 
     [parent] => 0 
    ) 

[2] => Array 
    (
     [id] => 5 
     [parent] => 0 
    ) 

[3] => Array 
    (
     [id] => 2 
     [parent] => 1 
    ) 

[4] => Array 
    (
     [id] => 31 
     [parent] => 2 
    ) 

[5] => Array 
    (
     [id] => 32 
     [parent] => 2 
    ) 

[6] => Array 
    (
     [id] => 17 
     [parent] => 3 
    ) 

)