Forum PHP.pl > [PHP] Plaska struktura tablic do drzewa

Pomoc - Szukaj - Użytkownicy - Kalendarz

Pełna wersja: [PHP] Plaska struktura tablic do drzewa

Mastobol

15.08.2012, 09:41:36

Z bazy danych wyciagam po kolei rekordy i wrzucam je do tablicy asocjacyjnej tworzac plaska strukture. Obiekty sa node'ami w relacji parent->child z wieloma poziomami zagniezdenia. Przykladowa struktura posortowana po id wyglada tak :

[PHP] pobierz, plaintext 
Array
(
    [22] => Array
        (
            [Id] => 22
            [parentId] => 14
            [Name] => T2
        )
 
    [14] => Array
        (
            [Id] => 14
            [parentId] => null
            [Name] => T1
        )
 
    [43] => Array
        (
            [Id] => 43
            [parentId] => 22
            [Name] => T2 child
        )
 
    [42] => Array
        (
            [Id] => 42
            [parentId] => 14
            [leaf] => true
        )
 
    [41] => Array
        (
            [Id] => 41
            [parentId] => null
            [Name] => T4
        )
 
    [40] => Array
        (
            [Id] => 40
            [parentId] => null
            [Name] => T5
        )
)
[PHP] pobierz, plaintext

Parametr parentId wskazuje na rodzica wezla. Wartosc null oznacza,ze wezel jest pierwszym poziomem i bedzie dzieckiem root'a (ktory jest tworzony gdzie indziej i tutaj nigdy sie nie pojawi). I teraz pytanie. Jak zamienic to na drzewiasta strukture, gdzie dzieci wezla znajda sie w tablicy children ? :

[PHP] pobierz, plaintext 
[0] => Array
    (
        [Id] => 14
        [parentId] => null
        [Name] => T1
        [children] => Array
            (
                [0] => Array
                    (
                        [Id] => 22
                        [parentId] => 14
                        [Name] => T2
                        [children] => Array
                            (
                                [0] => Array
                                    (
                                        [Id] => 43
                                        [parentId] => 22
                                        [Name] => T2 child
                                    )
 
                            )
 
                    )
            )
    )
[PHP] pobierz, plaintext

Walcze z tym juz troche czasu i jak dotad ine udalo mi sie wykombinowac nic co bedzie dzialalo w kazdym przypadku. Znalazlem cos takiego :

[PHP] pobierz, plaintext 
$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]);
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;
}
[PHP] pobierz, plaintext

Ale w tym rozwiazaniu trzeba podac id pierwszego poziomu ($new[0], ktore u mnie jest null) a calosc mimo wszystko nie buduje poprawnej struktury. Z gory dziekuje za wszelka pomoc bo pehapowiec ze mnie zaden i normalnie zajmuje sie frontendem ale w czasie wakacji roznie to bywa :/

darko

15.08.2012, 12:44:14

Musiałbyś napisać swój komparator i przekazać go do funkcji uasort zob. przykład 1. - funkcja cmp. Taki komparator układałby Ci dzieci w odpowiedniej pozycji dla odpowiedniego node'a (po kolei) i sklejałby z tego jedną tablicę z wieloma zagłębieniami. Nie jest to mega skomplikowane, a eleganckim rozwiązaniem mogłoby być użycie rekurencji.

Mastobol

15.08.2012, 22:56:05

Czyli po kolei, co ma robic ten komparator ? Leci sobie po tablicy i znajduje pierwszego node'a (zalozmy, ze ma id=2):

- powiedzmy,ze wezel ma parentId=1
- szukam w tablicy wezla z id=1 i mu wezel z id=2 w tablice children

Tylko,ze teraz jesli jakis inny wezel ma parentId=2 to jak mam znalezc ten wezel, ktory jest w tablicy children wezla 1 ? Moglbym prosic o jakis pseudokod ?

darko

16.08.2012, 14:04:13

Hej! To po kolei, bez rekurencji i bez komparatora, na szybko spróbuj czegoś takiego:

[PHP] pobierz, plaintext 
echo '<pre>';
 
$arr = Array
(
    '22' => Array
        (
            'Id' => 22,
            'parentId' => 14,
            'Name' => 'T2'
        ),
 
    '14' => Array
        (
            'Id' => 14,
            'parentId' => null,
            'Name' => 'T1',
        ),
 
    '43' => Array
        (
            'Id' => 43,
            'parentId' => 22,
            'Name' => 'T2 child'
        ),
 
    '42' => Array
        (
            'Id' => 42,
            'parentId' => 14,
            'leaf' => true,
        ),
 
    '41' => Array
        (
            'Id' => 41,
            'parentId' => null,
            'Name' => 'T4'
        ),
 
    '40' => Array
        (
            'Id' => 40,
            'parentId' => null,
            'Name' => 'T5'
        )
);
 
print_r($arr);
 
$sortedArray = array();
//  znajdź rodziców
foreach($arr as $k => $v)
{
    if(is_null($v['parentId']))
    {
        $sortedArray[$k] = $v;
    }
}
// sortuj rodziców
asort($sortedArray);
 
function findChildren(array & $a1, array & $a2)
{
    foreach($a1 as $k => $v)
    {
        if(!is_null($v['parentId']))
        {
            if(array_key_exists($v['parentId'], $a2))
            {
                $a2[$v['parentId']]['children'][$v['Id']] = $v;
                unset($a1[$k]);
            }
        }
        else
        {
            unset($a1[$k]);
        }
    }
 
    foreach($a1 as $k => $v)
    {
        foreach($a2 as $x1 => $x2)
        {
            $temp = @$x2['children'];
            if(isset($temp))
            {
               if(array_key_exists($v['parentId'], $temp))
               {
                    $a2[$x1]['children'][$v['parentId']]['children'][$v['Id']] = $v;
                    unset($a1[$k]);
               }
            }
        }
    }
 
    return $a2;
}
 
echo findChildren($arr, $sortedArray);
 
echo '<hr/>';
//print_r($arr);
print_r($sortedArray);
[PHP] pobierz, plaintext

######### wynik: #########

Kod

Array
(
    [22] => Array
        (
            [Id] => 22
            [parentId] => 14
            [Name] => T2
        )

    [14] => Array
        (
            [Id] => 14
            [parentId] =>
            [Name] => T1
        )

    [43] => Array
        (
            [Id] => 43
            [parentId] => 22
            [Name] => T2 child
        )

    [42] => Array
        (
            [Id] => 42
            [parentId] => 14
            [leaf] => 1
        )

    [41] => Array
        (
            [Id] => 41
            [parentId] =>
            [Name] => T4
        )

    [40] => Array
        (
            [Id] => 40
            [parentId] =>
            [Name] => T5
        )

)
Array
Array
(
    [14] => Array
        (
            [Id] => 14
            [parentId] =>
            [Name] => T1
            [children] => Array
                (
                    [22] => Array
                        (
                            [Id] => 22
                            [parentId] => 14
                            [Name] => T2
                            [children] => Array
                                (
                                    [43] => Array
                                        (
                                            [Id] => 43
                                            [parentId] => 22
                                            [Name] => T2 child
                                        )

                                )

                        )

                    [42] => Array
                        (
                            [Id] => 42
                            [parentId] => 14
                            [leaf] => 1
                        )

                )

        )

    [40] => Array
        (
            [Id] => 40
            [parentId] =>
            [Name] => T5
        )

    [41] => Array
        (
            [Id] => 41
            [parentId] =>
            [Name] => T4
        )

)

W takiej postaci łatwo to przerobić na rekurencję i obsłużyć nieskończenie wiele (do limitu zagnieżdżeń tablic - ustawienia php) zagłębień relacji rodzic-dziecko.

Zob. przykład 2

Mastobol

21.08.2012, 10:11:36

Wielkie dzieki za pomoc. Ostateczna wersja wyglada tak :

[PHP] pobierz, plaintext 
$sortedArray = array();
// get first level
foreach($tasks as $k => $v){
    if($v['parentId'] == 'null'){
        $sortedArray[$k] = $v;
        unset($tasks[$k]);
    }
}
 
function getChildren(array & $a1, array & $a2){
    foreach($a1 as $k => $v){
        findChildren($v, $a2, $k);      
    }
}
 
function findChildren($rec1, array & $a2, $key){
 
    foreach($a2 as $k => $v){
        if($rec1['parentId'] == $v['Id']){
            $a2[$k]['children'][$rec1['Id']] = $rec1;
            unset($tasks[$key]);
        } else {
            if (isset($v['children'])){
                findChildren($rec1, $a2[$k]['children'], $key);
            }
        }
    }
}
 
function makeIndexed(array & $arr, array & $par = null){
    if(is_null($par)){
        $arr = array_values($arr);
    } else {
        $par['children'] = array_values($arr);
    }
 
    for($i=0; $i<count($arr); $i++) {   
        $temp = @$arr[$i]['children'];
        if(isset($temp)) {
            makeIndexed($arr[$i]['children'], $arr[$i]);
        }       
    }
}
 
getChildren($tasks, $sortedArray);
 
makeIndexed($sortedArray);
[PHP] pobierz, plaintext

Nie jest to ani najpiekniejszy ani najwydajniejszy kod php na tej planecie ale wydaje sie dzialac i jest szczytem moich obecnych mozliwosci

Funkcja 'makeIndexed' dodana dla stworzenia JSON'a, w ktorym dzieci sa tablicami obiektow a nie obiekiami.

To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.