[php] - Alberi binari e ordinamento

[ringo_mato]

ciao a tutti
Piccolo grande problema con gli alberi binari

mi trovo in una situazione di avere un array di questo tipo

Array
(
    [1] => Array
        (
            [id] => 1
            [name] => Nodo1
            [parent] => 0
            [attivo] => 1
        )

    [2] => Array
        (
            [id] => 2
            [name] => Nodo2
            [parent] => 0
            [attivo] => 1
        )

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

    [4] => Array
        (
            [id] => 4
            [name] => Nodo4
            [parent] => 3
            [attivo] => 1
        )

) 

e vorrei creare un albero binario così

 |_ Nodo1
 |_ Nodo2 
    |_ Nodo3 
        |_ Nodo4

partendo dal presupposto che le strutture gerarchiche su db non ho intenzione di usarle ma voglio farlo con la ricorsività per ovvi motivi

io sono arrivato qui ma non funzica

    function BuildList($list,$parent = 999999)
    {
        // Reset delle variabili
        reset($list);
        unset($temp_array);
        unset($array);
                
        foreach($list as $k => $v)
        {          
            if (( $v['parent'] == 0 || $v['id'] == $parent ) ) 
            {
                    $temp_array[$v['id']] = $v;  // Prelevo i nodi genitori               
                }  
                elseif($v['parent'] !=0  ) 
                {
              $array[$v['id']] = $v;  // Prelevo i nodi figli
                }
        
        } // End-foreach
                
        echo '<pre>'; print_r($temp_array); echo '</pre>'; //DEBUG
        echo '<pre>'; info($array); echo '</pre>';//DEBUG
                  
        if (isset($temp_array)) 
        {
            foreach($temp_array as $k => $v)
            {               
               $array[$k] = BuildList($array,$k);
            }      
        }
        
        return (isset($array) ? $array : false);
        
    } // End-Method 

qualche anima pia che sa dirmi cosa sbaglio e come posso sistemare il problema dei nodi del figlio ??
grazie in anticipo a tutti

[filippo.toso]

Potresti postare un var_export() dell'array in modo da non doverlo ricostruire a mano?

[ringo_mato]

Originariamente inviato da filippo.toso
Potresti postare un var_export() dell'array in modo da non doverlo ricostruire a mano?

$array = array ( 0 => array ( 'id' => '1', 'name' => 'Nodo1', 'parent' => '0', 'attivo' => '1'), 
                      1 => array ( 'id' => '2', 'name' => 'Nodo2', 'parent' => '0', 'attivo' => '1'), 
                      2 => array ( 'id' => '3', 'name' => 'Nodo3', 'parent' => '2', 'attivo' => '1'), 
                      3 => array ( 'id' => '4', 'name' => 'Nodo4', 'parent' => '3', 'attivo' => '1')); 

Eccolo grazie

[filippo.toso]

Studiati questo codice:

<pre>
<?php 

$array = array ( 0 => array ( 'id' => '1', 'name' => 'Nodo1', 'parent' => '0', 'attivo' => '1'),
                      1 => array ( 'id' => '2', 'name' => 'Nodo2', 'parent' => '0', 'attivo' => '1'),
                      2 => array ( 'id' => '3', 'name' => 'Nodo3', 'parent' => '2', 'attivo' => '1'),
                      3 => array ( 'id' => '4', 'name' => 'Nodo4', 'parent' => '3', 'attivo' => '1'));
                      
function tree($nodes, $level = 0) {
    foreach ($nodes as $node) {
        $pre = str_repeat('   ', $level) . '|_ ';
        print("{$pre}{$node['name']}\r\n");
        tree($node['childs'], $level + 1);
    }
}

$items = array();
foreach ($array as $node) {
    $items[$node['id']] = $node;
    $items[$node['id']]['childs'] = array();
}
$items[0] = array('name' => 'root', 'parent' => -1, 'childs' => array());

foreach ($items as &$item) {
    $items[$item['parent']]['childs'][] = & $item;
}

tree($items[0]['childs']);

?>
</pre>

[ringo_mato]

Originariamente inviato da filippo.toso
Studiati questo codice:

<pre>
<?php 

$array = array ( 0 => array ( 'id' => '1', 'name' => 'Nodo1', 'parent' => '0', 'attivo' => '1'),
                      1 => array ( 'id' => '2', 'name' => 'Nodo2', 'parent' => '0', 'attivo' => '1'),
                      2 => array ( 'id' => '3', 'name' => 'Nodo3', 'parent' => '2', 'attivo' => '1'),
                      3 => array ( 'id' => '4', 'name' => 'Nodo4', 'parent' => '3', 'attivo' => '1'));
                      
function tree($nodes, $level = 0) {
    foreach ($nodes as $node) {
        $pre = str_repeat('   ', $level) . '|_ ';
        print("{$pre}{$node['name']}\r\n");
        tree($node['childs'], $level + 1);
    }
}

$items = array();
foreach ($array as $node) {
    $items[$node['id']] = $node;
    $items[$node['id']]['childs'] = array();
}
$items[0] = array('name' => 'root', 'parent' => -1, 'childs' => array());

foreach ($items as &$item) {
    $items[$item['parent']]['childs'][] = & $item;
}

tree($items[0]['childs']);

?>
</pre>

carino
e molto semplice
sono rimasto sconvolto da questo però

foreach ($items as &$item) {
    $items[$item['parent']]['childs'][] = & $item;
} 

grazie infinite filippo
avanzi un favore

[nICO80]

Non so se ti possa interessare, comunque io ho implementato questa soluzione (con qualche cambiamento minore) and it rocks! (guarda da metà pagina in poi quando parla del modello nested set)

http://dev.mysql.com/tech-resources/...ical-data.html