Drzewko - podejscie iteracyjne Opcje

[marcini82]

Witam!

Zalozmy, ze mamy w tabeli bazy danych proste drzewko. Kazdy wiersz ma 3 pola: id, parent_id i name.
Odczytalismy te rekordy z bazy, mamy je w dwuwymiarowej tablicy asocjacyjnej i chcemy wyswietlic w formie drzewka:

Kod

level1_1
    level2_1
        level3_1
        level3_2
        level3_3
    level2_2
    level2_3
level1_2
    level2_4
level1_3

Drzewko moze miec dowolna ilosc poziomow zaglebienia.
Jesli sie uzywa rekurencji to proste. Ale czy da sie to zrobic iteracyjnie? A jesli sie da, to jak?
Zakladam, ze jesli sie da, to bedzie wydajniej. Czy sie nie myle?

Ten post edytował marcini82 13.09.2007, 12:37:51

[marcini82]

Pokaz ta tablice bo nie potrafie sobie jej wyobrazic, i jak jest posortowana.

Przedstawia po prostu kolejne rekordy w bazie danych przy takim modelu drzewka:

Kod

Array
(
    [0] => Array
        (
            [id] => 2
            [name] => level1_1
            [parent_id] => 1
        )

    [1] => Array
        (
            [id] => 3
            [name] => level1_2
            [parent_id] => 1
        )

    [2] => Array
        (
            [id] => 4
            [name] => level1_3
            [parent_id] => 1
        )

    [3] => Array
        (
            [id] => 5
            [name] => level2_1
            [parent_id] => 2
        )

    [4] => Array
        (
            [id] => 6
            [name] => level2_2
            [parent_id] => 2
        )

    [5] => Array
        (
            [id] => 7
            [name] => level2_3
            [parent_id] => 2
        )

)

Istnieje podejście, choć oczywiście o innej strukturze danych niż opisana przez Ciebie. Ale rzeczywiście zwieksza wydajnosc:
wygugluj sobie 'celko tree'.

Chodzi ci o "nested sets"? Tez ciekawy temat, ogolnie drzewka to dosc obszerna i zawila sprawa, bo kazde podejscie ma plusy i minusy...
Ale w tej chwili zalezy mi glownie na wyrzuceniu rekurencji z tego konkretnego modelu drzewka.

Mam to w książce "Algorytmy i struktury danych" wyd. Helion. Niestety, trudny temat, jak na początek odpuściłem sobie go i wiele powiedzieć nie mogę.
Natomiast wygóglować można ciekawe informacje.

Poszukam troche i poczytam, ale dzis juz o tej porze to troche za ciezkie (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg) Musze poczekac na dobry dzien.