[php] Doorlopen van een boomstructuur

[alienfruit]

Ik ben momenteel bezig met uitlezen van een boomstructuur die is opgeslagen in een MySql tabel. Niks verkeerds tot nu toe, nu ben ik zelf iemand waarbij alles tig keer moeilijker is als er gewerkt moet worden met databases. Waardoor ik nu met een probleem zit, waar ik niet uit kom.

Ik heb simpele code die uit een paar tabellen essentiële informatie haalt die ik graag wil gebruiken.
De werking van de code is als volgt:

1. Een query haalt alle items op in de treeview (zodat je niet elke een query hebt per node e.d.)
2. Een while-loop zorgt ervoor dat er een array wordt opgebouwd

Het probleem wat ik nu heb is dat het doorlopen van een simpele boomstructuur prima gaat, zolang een node niet meer dan één child node heeft. Als het dit wel heeft, blijft het allemaal mooi hangen. Nu vraag ik me af hoe ik dit moet oplossen.

Ik gebruik twee classes om door deze klasse te lopen namelijk een TreeAggregator (maakt de tree e.d.) een TreeIterator (voor het doorlopen). Ik heb het gescheiden zodat als de boomstructuur verandert ik alleen de TreeAggregator hoeft te wijzigen en niet de iterator.

Misschien is een iterator hiervoor toch niet de juiste manier? Iemand enig idee of ga ik ergens de mist in?

De code kun je op de volgende lokatie vinden, namelijk: http://www.dustyfrog.nl/marijn/code.phps.
De resultaat van de array in de TreeAggregator klasse is als volgt:

code:

Array
(
    [0] => Array
        (
            [1] => Array
                (
                    [parent_id] => 0
                    [child_id] => 1
                    [type] => domain
                )

        )

    [1] => Array
        (
            [2] => Array
                (
                    [parent_id] => 1
                    [child_id] => 2
                    [type] => subdomain
                )

        )

    [2] => Array
        (
            [3] => Array
                (
                    [parent_id] => 2
                    [child_id] => 3
                    [type] => page
                )

        )

    [3] => Array
        (
            [4] => Array
                (
                    [parent_id] => 3
                    [child_id] => 4
                    [type] => entry
                )

            [5] => Array
                (
                    [parent_id] => 3
                    [child_id] => 5
                    [type] => entry
                )

        )

[ Voor 52% gewijzigd door alienfruit op 10-07-2005 02:21 . Reden: uitleg+code ]

[dawuss]

Misschien is het handig om jezelf eerst even in te lezen op de verschillende manieren om bomen of grafen te doorlopen

[google=depth breadth first search] zou je daarbij een heel eind de goede richting in moeten kunnen helpen

[curry684]

Hoe sla ik hierarchische data efficient op in MySQL en loop ik hier met PHP overheen

[alienfruit]

Hmm, ik ken de twee termen wel omdat je deze ook prima kan gebruiken bij het maken van iterators. Waarschijnlijk moet ik mijn iterator in iedergeval uitbreiden met twee functies namelijk: getChildren() en hasChildren(). Om zodoende door een bepaalde laag door te gaan. Maar ik zal eens wat artikelen doornemen, misschien heb ik de plank weer eens totaal mis geslagen

Misschien moet ik overigens wel array "output" wat opschonen dat het ook echt als een boom wordt weergegeven. In plaats zoals het nu is dat elke parent_id zijn eigen "hoofd key" krijgt.

PHP:

        $i = 0;
        while ( $iterator->isDone() === FALSE ) {
            $item = $iterator->getCurrentItem();
            
            $ident = "";
            for ( $x=0; $x < $i; $x++ ) {
                $ident .= "&nbsp;&nbsp;>>&nbsp;&nbsp;";
            }
            print $ident . " " . $item[ 'type' ] . "<br />";
            
            // next item
            $iterator->next(); // next item..</>
            $i++;
        }

/*
Resultaat:

 domain
  >>   subdomain
  >>    >>   page
  >>    >>    >>   entry

// oftewel het mist de tweede child die aan page hangt. :(
*/

De code hierboven werkt bijvoorbeeld best aardig zolang er geen meerdere child nodes zijn, liefst gebruik ik niet recursie. Als in het aanroepen van een functie meerdere malen (zoals wordt gesuggereerd in de link van curry), bij mijn weten hoeft dat ook niet.

[ Voor 92% gewijzigd door alienfruit op 10-07-2005 03:59 ]

[alienfruit]

Hmm, ik heb nog eens goed gekeken naar die twee algoritmes. Volgens is een iterator() net zo flexibel als deze twee zoek algoritmes. Misschien moet ik een nieuwe iterator teruggeven als een node meerdere childs heeft?