Witam mam problem z rekurencyjnym wyświetlaniem menu. Chcę aby wizualizacja mojego menu wyglądała następująco:

[XML] pobierz, plaintext 
menu1->menu2->menu3
           ->menu4->menu5->itd
                         ->menu19->menu23
[XML] pobierz, plaintext 

mam wszystkie metody wyciągające kategorie główne oraz podkategorie pierwszego poziomu. Problem pojawił się przy wyświetlaniu. Menu może mieć nieskończoną liczbę poziomów.

tak wygląda szczątkowy kod:

[PHP] pobierz, plaintext 
 
public static function recurMenu($menu, $text = null)
{
       echo = "<div style='height: 100px; width: 100px;'>$record->t_menu_name</div>";
       foreach($menu as $record)
        {
            $submenu = MenuHelper::getSubmenuAtDepth($record->t_id, 1);
            if($submenu)
            {
                //................
 
 
            }
        }
}
 
[PHP] pobierz, plaintext 

Nie wiem jak to ugryźć od strony wizualizacji. Może łatwiej byłoby zbudować jakąś macierz. W parametrze jest przekazywana tablica obiektów menu lub podmenu. Mapowanie kategorii mam poprzez odwzorowanie wszystkich relacji pomiędzy kategoriami (w sumie to nieważne). Może ktoś się spotkał z takim czymś i ma już doświadczenie. Zwykle używa się konkretnego menu i wyciaga jego podkategorie potem znowu itd i wtedy nie ma problemu, ale tym razem musze przedstawić całą mapę kategorii.

Proszę o pomoc

Problem drzewek jest stary jak świat i wystarczy dobrze poszukać, aby odnaleźć to, co Cię interesuje. Jakoś nie bardzo jestem sobie w stanie wyobrazić macierz opisującą drzewko (chyba że za mało świata widziałem).

Generalnie: albo rekurencja, albo iteracja. Przy czym ta pierwsza ma swoje ograniczenia i jest bardziej zasobożerna.

Nie możemy o większej ilości konkretów pogadać, bo nie wiemy, jak drzewko masz zapisane - LP, binarne, czy jeszcze jakieś inne (chociażby "płaskie" z pomocą kolumn kolejności i zagłębienia).

[PHP] pobierz, plaintext 
$submenu = MenuHelper::getSubmenuAtDepth($record->t_id, 1);
[PHP] pobierz, plaintext 

Mam nadzieję, że nie wywołujesz w tym miejscu zapytań rekurencyjnie...

[PHP] pobierz, plaintext 
 
$submenu = MenuHelper::getSubmenuAtDepth($record->t_id, 1);
[PHP] pobierz, plaintext 

to nie jest rekurencyjne. To jest zapytanie o podkategorie. a same kategorie sa zawarte w dwóch tabelkach. w jednej jest nazwa, opisy itd a druga tabela zawiera relacje tych kategorii. Np. 1=>2=>3 w kategorii relacji oznacza tak:

1. ojciec 1, syn 2, glebokosc 1
2. ojcec 1, syn 3, glebokosc 2
3.ojciec 2, syn3, glebokosc 1


i to tyle. Wiem że występuje tu nadmiarowosc ale za to tego typu rozwiazanie pozawala na naprawde bardzo duzo bez wiekszego mielenia bazy. Korzystam z niego długo i jak narazie sie sprawdza....problem tylko przedstawienia na ekranie n-zagnieżdżonej tabeli....

Witam
Ja wykorzystuje rekurencje.
Trzymam wszystkie pozycje menu w jednej tabeli. Pole ID_PARENT wskazuje mi kategorie nadrzedna.
Kategorie glowne maja ID_PARENT = 0
Ponizej funkcja wyswietlajaca "drzewko menu"

[PHP] pobierz, plaintext 
function generate_menu($id_parent)
{
    global $mysql_link;
    $content = '';
 
	 $content = '<ul>';
 
	 $m = "SELECT ID, NAZWA FROM MENU WHERE ID_PARENT='".$id_parent."'";
	 $result = mysql_query($m, $mysql_link) or die ("$m<BR>\n" . mysql_error());
 
	 while( $aw = mysql_fetch_assoc($result) ) {
 
	 $content .= '<li>'.stripslashes($aw['NAZWA']).'</li>';
 
	 generate_menu($aw['ID']);
 
	 $content .= '</ul>';
	 }
 
         return $content;
 
} // end func
 
//sposob uzycia banalnie prosty
 
echo generate_menu(0);
[PHP] pobierz, plaintext 

woooow niezly zabijaka.. jesli ta funckja jest wg ciebie gotowa do uzytku to niezly z niej babol...
pomysl ze mam menu z 10 elementow i na kazda pozycje mam 10 pod elementow co mi daje 100 zapytan do bazy podczas samego rysowania menu nie mowiac o zapytaniach ktore sa mi potrzbne w dalszej czesci aplikacji, zreszta ta rekurencja nie ma ograniczenia co do rodzica, ogolnie funkcja jest to wywalenia jak sie na nia popatrzy

Moze i babol (zasobozerny to fakt), ale z checia obejrze rozwiazanie kolegi na menu powiedzmy 100 elementowe i powiedzmy zagniezdzone do 6 poziomow w glab z mozliwoscia wyswietlania dowolnej ilosc zagniezdzen.
Na pewno skorzystam z Twojego rozwiazania.

Kombinujecie z tym jak nie wiem co...

1. Jedno menu = jedna tabela w bazie
2. Jedno menu = jedno zapytanie, które zrzuca całe menu do tablicy (ewentualnie wybraną gałąź)
3. Do wyświetlenia tablicy użyjemy rekurencji

tu macie pierwszy lepszy przykład:
http://blog.mwojcik.pl/2008/02/17/drzewa-k...-php-metoda-ip/

Dobrze też, aby tablica menu leciała z cache.

Za próbę uruchomienia czegoś takiego, PHP powinno wywalać fatal error LEAVE KEYBOARD ALONE!

http://eriz.pcinside.pl/weblog/php-feat-my...rzewka-143.html - i mogę sobie sobię zagnieżdżać nawet kilkaset poziomów, a RAM i serwer SQL tego nie poczują. [;

Od dawna czegoś takiego szukałem! Dzięki wielkie za wstawkę

A gdyby zrobić coś takiego:

[PHP] pobierz, plaintext 
$q = $sql ->query('SELECT id, parentID FROM menu ORDER BY parentID');
while($r = $q -> fetch_assoc())
{
  if(isset($arrays[$r['id']])
      $r['childs'] = $arrays[$r['id']]['childs];
  $arrays[$r['id']] = $r;  // myk pierwszy
 
  if($parentID == 0)
    $result[] = &$arrays[$r['id']]; // myk drugi
  else
    $arrays[$r['parentID']]['childs][] = &$arrays[$r['id']]; // myk drugi
}
return $result;
[PHP] pobierz, plaintext 

W efekcie mamy coś takiego:

[PHP] pobierz, plaintext 
$arrays = array ( 
   1  =>    array(parentID => 0, id=>1),
   3  =>    array(parentID => 0, id=>3),
   4  =>    array(parentID => 1, id=>4),
   5  =>    array(parentID => 4, id=>5),
   6  =>    array(parentID => 3, id=>6),
   7  =>    array(parentID => 4, id=>7),
)
 
$result = array(
    array(
        'parentID' => 0,
        'id' => 1,
        'childs' => array(
            array(
                'parentID' => 1,
                'id' => 4,
                'childs' => array(
                    array(
                        'parentID' => 4,
                        'id' => 5
                    ),
                    array(
                        'parentID' => 4,
                        'id' => 7
                    )
                )
            )
        )
    ),
    array(
        'parentID' => 0,
        'id' => 3,
        'childs' => array(
            array(
                'parentID' => 3,
                'id' => 1)
        )
    )
);
);
[PHP] pobierz, plaintext 

Powinno działać? I żadnego kombinowania z levelami

Hmmm... znam troszkę przekombinowaną wg niektórych metodę ale póki co... idealną na moje potrzeby. KAŻDA inna metoda jaką próbowałem miała swoje wady. Ta którą używam nazywana jest po prostu Nested Tree. Zasada jej działania jest opisana tutaj

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

pod nagłówkiem The Nested Set Model. Żeby niektórzy szybciej załapali to w skrócie powiem o co chodzi. Każdy element tablicy opisany jest za pomocą 2 właściwości. LEWA i PRAWA :-D. Czym jest lewa i prawa sami określcie. Najczęściej stosuje się trzecią wskazującą na poziom zagnieżdżenia. Rzecz przydatna ale nie jest niezbędna.

Jak to wygląda w praktyce ?
Elemenyt 1 --- LEWA 1 | PRAWA 2 | LVL 1

Wartość lewa to po prostu numeracja. Wartość prawa jest obliczana wg prostego wzoru:

PRAWA = LEWA + (ILOŚĆ_DZIECI * 2) + 1;

W tym wypadku jak chcemy dodać element 2, robimy to tak

Element1 --- LEWA 1 | PRAWA 2 | LVL 1
Element1 --- LEWA 3 | PRAWA 4 | LVL 1

Debilnie proste prawda ? Skoro 1 i 2 są zajęte to kolejny element dostaje cyfrę 3 na lewo i na prawo obliczamy wg wzorca: PRAWA = 3 ( 0*2 ) + 1; czyli 4.
I tak z każdym kolejnym elementem.

Teraz pytanie... co z dziećmi ? A no najpierw może pokaże jak wygląda drzewo z dzieckiem a potem wyjaśnię:

Element1 --- LEWA 1 | PRAWA 4 | LVL 1
Element3 --- LEWA 2 | PRAWA 3 | LVL 2
Element2 --- LEWA 5 | PRAWA 6 | LVL 1

Dodajmy kolejny element

Element1 --- LEWA 1 | PRAWA 6 | LVL 1
Element3 --- LEWA 2 | PRAWA 3 | LVL 2
Element4 --- LEWA 4 | PRAWA 5 | LVL 2
Element2 --- LEWA 7 | PRAWA 8 | LVL 1

Teraz jeszcze dla jasności do elementu 3 coś dodamy:

Element1 --- LEWA 1 | PRAWA 8 | LVL 1
Element3 --- LEWA 2 | PRAWA 5 | LVL 2
Element5 --- LEWA 3 | PRAWA 4 | LVL 3
Element4 --- LEWA 6 | PRAWA 7 | LVL 2
Element2 --- LEWA 9 | PRAWA 10 | LVL 1

Zobaczcie że zasada jest WSZĘDZIE taka sama. Wzór dla element1 to PRAWA = 1 + (3 * 2) + 1 czyli PRAWA = 1 + 6 + 1 czyli 8.
Kiedy dokładamy element WEWNĄTRZ drzewa to WSZYSTKIE elementy które są wyżej mają wartość PRAWĄ o 2 większą. Z kolei elementy niżej mają LEWĄ I PRAWĄ o 2 WIĘKSZĄ.
A zasada jest prosta. ILOŚĆ DOKŁADANYCH ELEMENTÓW * 2 więc jak na raz wsadzicie 10 elementów to wartość prawa tych wyżej wzrasta o 20 a lewa i prawa niżej o tyle samo.


_______________________________________________

Teraz pewnie chcecie mnie skrytykować, będziecie twierdzić że metoda jest dzika, skomplikowana i w ogóle zła. Cóż... raczej nie macie racji. Wystarczy troszkę pomyśleć nad zaletami i wadami tej metody.

ZALETY:
1. W tabeli BD, wszystkie rekordy są przechowywane za porządkiem i nie musimy z niczym kombinować. Po prostu do tabeli mamy 2 lub 3 pola więcej.
2. Sortując elementy od LEWEJ wartości dostajemy drzewo w odpowiedniej kolejności. Jak nałożycie indeksy na LEWA / PRAWA to BD tego nawet nie poczuje. A i bez tego nie ma problemu bo mamy tu do czynienia z wartościami numerycznymi.
3. Niemal WSZYSTKIE operacje wybierania robimy na 2 zapytaniach do bazy.
4. Metoda nie ma ograniczeń co do wielkości. Problem napotkacie jak się wam big int skończy
5. Metoda jest bardzo szybka.
6. Mamy PEŁNĄ kontrolę nad kolejnością elementów w drzewie (z czym również niektóre metody sobie nie radzą do końca).

WADY:
1. No niestety musicie zastosować ten tragicznie trudny wzór jaki Wam podałem i zasadę zwiększania wartości jak dodamy coś do bazy.
2. Dodawanie / usuwanie i przenoszenie elementów w bazie wymaga 3-5 zapytań.
3. Trzeba pomyśleć żeby metodę zaimplementować ?

PRZYKŁADY MOŻLIWOŚCI:
( wybieramy wartość LEWĄ I PRAWĄ elementu X który nas interesuje)

1. Zakładamy że potrzeba nam całe drzewko w odpowiedniej kolejności
- select z sortowaniem wg wartości lewej
2. Potrzeba nam wybraną gałąź drzewa (element X)
- Teraz jak chcemy np wszystko co znajduje się w tym elemencie to pobieramy wartość LEWA WIĘKSZĄ JAK LEWA X oraz LEWA MNIEJSZĄ JAK PRAWA X. Gotowe.
3. Potrzeba nam wszystko POZA wybraną gałęzią drzewa (poza elementem X)
- to samo tylko wartość LEWA MNIEJSZA od LEWA X i LEWA WIĘKSZA od PRAWA X.
4. Potrzeba nam wszystkich RODZICÓW elementu X, tu parę metod ma problem (np wymaga wielokrotnych zapytań do bazy). Tutaj:
- wybieramy wartość PRAWA WIĘKSZA OD PRAWA X i LEWA MNIEJSZA OD LEWA X.
5. Potrzeba nam elementy BEZ DZIECI
- PRAWA - LEWA - 1 ma wynosić 0
6. Potrzeba nam elementy z dziećmi
- PRAWA - LEWA - 1 > 0
7. Potrzeba nam elementy z 5 dziećmi
- (PRAWA - LEWA - 1) / 2 = 5
itp...
itd...
etc...

Możliwości jest na prawdę dużo a mają wybrany element (jego wartość lewą i prawą) możemy dowiedzieć się o nim wszystko. Na większość operacji potrzeba 1-2 zapytań (przy czym jedno zapytanie to właśnie odnalezienie lewej i prawej wartości elementu którego np dzieci możemy poszukać.

LVL przydaje się w paru przypadkach więc warto go mieć w bazie. Np wypisując drzewo zagnieżdżam je właśnie wg lvl. Sortując wg lewej wartości drzewo mam pewność że kolejność jest odpowiednia. Jeżeli LVL się zwiększył o 1, otwieram UL i zapamiętuje nowy LVL, jak się zmniejszył to zamykam UL i zapamiętuje nowy lvl. Proste. Jak nie chcemy mieć zagnieżdżonych list to lvl może nam powiedzieć jak duże wcięcie zrobić (prosto łatwo i skutecznie).

Problemem są operacje manipulowania drzewem ale przecież na ogół takowe się często nie zmienia. Chodzi o to musimy zwiększyć wartość prawą u elementów go poprzedzających, lewą i prawą następujących a potem wstawić element.
Przy usuwaniu trzeba zrobić to samo ale odwrotnie. Czyli usunąć element, zmniejszyć wartość prawą u rodziców i lewą oraz prawą wśród dzieci.
Przy przenoszeniu elementów w drzewie właściwie robimy jedno i drugie. Najpierw traktujemy element jak by był usunięty a potem "udajemy że go wstawiamy".

Przenoszenie może Wam się przy czymś takim wymagającym obliczeń wydawać dzikie ale nie jest. Lewa i prawa wartość jest stała bo jest obliczana ze wzoru. Zawsze jest to ilość elementów wewnątrz * 2 + 1 + lewa. Więc co wystarczy zrobić ? Jak przenosimy element to musimy znaleźć lewą i prawą wartość elementu gdzie jest on przenoszony a następnie obliczyć różnicę :-) I tak korygujemy wartości lewe, prawe i lvl bez skomplikowanych obliczeń.

Pozdrawiam i będę zdziwiony jak ktoś ten post doczyta do tego momentu. Wybaczcie że tego dokładniej nie opisałem ale nie chciało mi się robić obrazków i wykresów. Jak chcecie mieć jakieś wizualne przedstawienie metody to wejdźcie na link do dev.mysql który podałem. Opisuje on metodę i na okręgach pokazuje dokładnie o co chodzi.

Owszem, ale wadą tej jest konieczność wykonywania wielu zapytań...

Wiesz, młotkiem przybijesz gwoździa ale na pewno bym się 3x zastanowił zanim bym nim utłukł muchę na głowie. Każda metoda ma swoje wady i zalety... oraz swoje zastosowania. Wielu zapytań wykonywać nie trzeba przy pobieraniu danych. Tylko przy manipulowaniu drzewem.

Jeżeli potrzebne Ci drzewko które będzie zmieniane przez użytkowników a użytkowników jest setki czy tysiące to trzeba się liczyć z paroma zapytaniami. Ciężkie nie są ale jednak trzeba je wykonać.

A w wypadku gdy drzewo nie jest za często modyfikowane to metoda jest idealna. Jak pisałem, jeżeli chcesz dowiedzieć się COKOLWIEK związanego z danym elementem to potrzeba Ci 2 zapytania. Pierwsze które pobierze LEWA, PRAWA i LVL a drugie które wybierze to co Cie interesuje. Cała reszta może być wykonana jednym zapytaniem. Działasz na wartościach numerycznych więc wszelkie sortowania i inne cuda działają bardzo szybko.

Nie polecał bym jej tylko na portalu gdzie są setki jak nie tysiące użytkowników którzy cały czas robią rzeczy drzewko takie modyfikujące. Wtedy można pomyśleć nad czymś prostszym. Kwestia też taka - co wymagasz od swojego drzewa ? Przykładowo jak ważna jest dla mnie kolejność elementów to również nie widzę lepszej metody.

W skrócie - na 95% przypadków ta metoda nadała się idealnie. Pozostałe 5% to były przypadki jak opisałem wyżej. Duża liczba użytkowników, brak jakiś konkretnych wymagań co do pozycji elementów itp. Posłużyłem się wtedy prostszą metodą i przy okazji bardziej ograniczoną.