stromova struktura pres PHP

ahoj,
vyskytl se mi tu problem : mam urcitou strukturu slozek, ale nevim presne dopredu jak bude clenita...a potrebuju je vsechny vypsat treba stylem :
slozka1
->slozka1.1
->->slozka1.1.1
->slozka1.2
slozka2
slozka3
dokazal bych si s tim poradit, kdybych vedel jak am bejt ta struktura hluboka, ale takhle se mi na to nedari prijit. Jestli to pomuze, tak je jeste k dispozici celkovej pocet tech slozek...

jo a pro prochazeni slozek se soubory zatim pouzivam tenhle skriptik :

if($handle = opendir('members/'.$_SESSION['ses_id'])){
while (false !== ($file = readdir($handle))){
if($file != "." && $file != ".."){
$files_list[] = $file;
}
}
CloseDir($handle);
}

dekuju za pomoc :)

Zkus se podivat na internetu neco o "rekurzi". Rekurze je volani sebe sama.
V tvem pripade jde tedy o to, ze zavolas funkci, ten nacte vychozi obsah slozky (root) a uvnitr jeste otestuje, zda je aktualni polozka $file slozka(is_dir), nebo soubor. Jde-li o slozku, tak zavolas tu samou funkci (sebe sama) akorat vychozim obsahem je aktualni (ziskana - slozka1) slozka. No a toto se opakuje az do doby, pokud se nevycerpaji vsechny slozky.
Mozny problem bude s formatovanim tech sipek (->). Rekurze si nepamatuje predchozi stavy - urovne (teda aspon ja jsem na to zatim neprisel).

... pro hitech, kažád rekurze se dá přepsat na nerekurzivní podobu...
s úrovní to taky není tak těžké, prostě se do fce přidá číslo úrovně a v případě volání sama sebe se tohle číslo zvětší.

function rekurze($uroven) {
...
if ( mam se zanorit ) {
rekurze($uroven + 1);
} else {
proved akci;
}
}

odborníci ;-) taky ví, že průchodů stromem je více druhů, tzv preorder, inorder a postorder.
Tzn. (tyjo, už je to dlouho, co mě to učili, tak buďte tolerantní)
preorder - zpracuju uzel a vyřídím potomky
inorder - tady si nejsem jistý, ale uzel a pak, pokud má potomky začnu zpracovávat potomky, pak další uzel....
postorder - to kdybyste mě zabili netuší, ale někdo, kdo se to teď učí by to mohl upřesnit.
Pokud je to úplně blbě, tak se omlouvám, ale jsem přesvědčený, že je to dobře. ;-)

Pro průchod adresáři tyhle způsoby znamenají, co uvidím vypsané dřív (pokud je vypisuji).

Zkusím příklad (aspoň si to zopakuju):
<?php
$adresar = "e:/tmp/";

#preorder
function pruchod1($l=0, $adresar) {
$h = opendir($adresar);
while ( $f = readdir($h) ) {
echo $adresar.$f;
if ( is_dir($f) ) {
echo "/";
}
echo " --- level:$l<br/>\n";
}
rewinddir($h);
while ( $f = readdir($h) ) {
if ( is_dir($f) && $f != '.' && $f != '..') { # . a ..ne, tobychom se zacyklili
pruchod1($l+1, $adresar.$f.'/');
}
}
closedir($h);
}

#inorder
function pruchod2($l=0, $adresar) {
$h = opendir($adresar);
while ( $f = readdir($h) ) {
echo $adresar.$f;
if ( is_dir($f) ) {
echo "/";
}
echo " --- level:$l<br/>\n";
if ( is_dir($f) && $f != '.' && $f != '..' ) {
pruchod2($l+1, $adresar.$f.'/');
}
}
closedir($h);
}


#postorder
function pruchod3($l=0, $adresar) {
$h = opendir($adresar);
while ( $f = readdir($h) ) {
if ( is_dir($f) && $f != '.' && $f != '..' ) {
pruchod3($l+1, $adresar.$f.'/');
}
}
rewinddir($h);
echo "adresar $adresar <br/>\n";
while ( $f = readdir($h) ) {
echo $adresar.$f;
if ( is_dir($f) ) {
echo "/";
}
echo " --- level:$l<br/>\n";
}
closedir($h);
}

echo pruchod1(0, $adresar)."<hr/>";
echo pruchod2(0, $adresar)."<hr/>";
echo pruchod3(0, $adresar)."<hr/>";

?>

je to odzkoušené, ale kupodivu, ve win nefunguje pořádně is_dir(). Viz další vlákno.

nj, stromy... to jsme myslim loni brali... ale stejne jsem se radsi podival na wikipedi. ;-) takze je to takhle:
preorder: zpracuje rodicovsky uzel a pak synovsky (dceriny) uzly
postorder: zpracuje deti a pak rodice
inorder: zpracuje leve deti, pak rodice, pak prave deti
pak jsou k tomu jeste reverzni varianty... no me se to nechce prekladat, je to tu: http://en.wikipedia.org/wiki/Tree_traversal

jj, je to napsané blbě.
všude nacpěte
is_dir($adresar.$f)
místo
is_dir($f)
sorry za mistifikaci...

marek : dekuju moc :)
takhle vycerpavajici vyklad i s resenim sem necekal :)

manik, to víš, no, pěkný dotaz. ;-)

Každá rekurze se dá přepsat na nerekurzivní podobu - tak kontrétně u procházení stromové struktury o předem neznámé hloubce si to nějak bez rekurzí neumím představit.
Jinak už několikrát jsem v učebnici programování u zmínky rekurzí viděl výborný příklad na faktoriálu. No více neodůvodněné použití rekurze už snad ani nemůže být :)

u přepisu rekurzivní fce na nerekurzivní, si, samozřejmě, musíme pomoci nějakým ekvivalentem zásobníku. Příklad uvedu na nesmyslném faktroriálu:
<?php
#rekurzivni varianta

function f_rek($c) {
if ($c > 1) {
return f_rek($c-1)*$c;
} else {
return 1;
}
}

# nerekurzivni varianta
# pochopitelne z pohledu prepisu rekurzivni na nerekurzivni
function f_nerek($c) {
$stav = $c;
$r = 1;
while ($stav > 1) {
$r *= $stav;
$stav--;
}
return $r;
}

# bonus: optimalni reseni faktorialu, bez osetreni chyby, kdy faktorial je definovany pouze pro cela nezaporna cisla.
function f_opt($c) {
$r = 1;
for ($i=$c; $i > 1; $r *= $i--);
return $r;
}

echo f_rek(10)."<br/>\n";
echo f_nerek(10)."<br/>\n";
echo f_opt(10)."<br/>\n";


echo "<hr/>\n";

# koukam je to tu videt ponekud blbe, zkusim jeste priklad s rekurzinvim a nerekurzivnim vypisem adresare, to bude lepe ilustrovat situaci

# preorder rekurzivni
function pruchod1($l=0, $adresar) {
$h = opendir($adresar);
while ( $f = readdir($h) ) {
echo $adresar.'/'.$f;
if ( is_dir($adresar.'/'.$f) ) {
echo "/";
}
echo " --- level:$l<br/>\n";
}
rewinddir($h);
while ( $f = readdir($h) ) {
if ( is_dir($adresar.'/'.$f) && $f != '.' && $f != '..') { # . a ..ne, tobychom se zacyklili
pruchod1($l+1, $adresar.'/'.$f);
}
}
closedir($h);
}

# preodrer nerekurzivni - to bude kapku slozitejsi
function pruchod1_n($l=0, $adresar) {
$dir = array();
array_push($dir, $adresar);
while ( count($dir) > 0 ) {
$h = opendir($adresar = array_pop($dir));
$l = "?";
while ( $f = readdir($h) ) {
echo $adresar.'/'.$f;
if ( is_dir($adresar.'/'.$f) ) {
echo "/";
if ($f != '.' && $f != '..') {
array_push($dir, $adresar.'/'.$f);
}
}
echo " --- level:$l<br/>\n";
}
closedir($h);
}
}

echo pruchod1(0, "f:/tmp");
echo "<hr/>\n";
echo pruchod1_n(0, "f:/tmp");


?>

snad to vrací stejné výsledky, i když je to mírně přeházené... teoreticky je to dobře.

akorát jsem ještě nevymyslel, jak se dá počítat úroveň zanoření. Možná evidovat zvlášť v poli....

Úroveň zanoření uděláš jednoduše pomocí HTML - mrkni na následující schéma:

if(is_dir($dir)){
echo("<div style=\"margin-left: 20px;\">".$dir);
volaniRekurzeProDalsiPrubeh($dir);
echo("</div>");
}

Vždycky se vnořený adresář posune ještě o 20px doleva oproti původnímu a ukončeným divem se vrátí, když se už rekurzivně volaný skript dokončí.

Hm?:) Mně to v mým skriptu, který je též založený na rekurzivním procházení adresářů, funguje báječně...

Mildo, nemyslím, vyjádření úrovně v interpretaci (v html), ale počítání úrovní v nerekurzivním průchodu...