binärer baum

[polar]

nabend,

ich frage mich gerade wie ich eigentlich einen binären baum in php umsetzen soll?

in C habe ich den zeiger vorteil

struct bnode {
    int key;
    struct bnode *parent;
    struct bnode *left_child;
    struct bnode *right_child;
} 

aber wie kann ich das in php am besten lösen?
als struktur ersatz könnte man eine klasse verwenden, aber für die zeiger?

hat jemand sowas schon in php gemacht?

[polar]

oh da hab ich doch gleich was gefunden

Abstrakte Datentypen
Sterling Hughes hat eine erste Alphaversion seiner Abstract Data Types (ADT)-Erweiterung für PHP freigegeben. Abstrakte Datentypen wie beispielsweise Bäume und Graphen benötigt man bei der Realisierung von verschachtelten HTML-Menüs ebenso wie für die Umsetzung von Algorithmen. Bislang musste man als PHP-Programmierer auf PHP-Implementierungen dieser Datenstrukturen zurückgreifen, was in Bezug auf Speicher- und Zeitaufwand schon mal Probleme bereiten kann. Die ADT-Erweiterung gibt dem PHP-Programmierer nun C-Implementierungen der Datenstrukturen Baum (mit AVL und Binärbaum-Ausprägungen), Graph, Heap, Set, Stack und Queue an die Hand, die eine effektive Umsetzung der genannten Anwendungen erlauben und sowohl prozedural als auch objektorientiert verwendet werden können. Die ADT-Erweiterung wird Bestandteil von PHP 5 sein und wahrscheinlich auch standardmäßig aktiviert sein.

http://www.phpmag.de

tja da muss jetzt wohl noch auf php5 warten

[Troublegum]

Das sollte auch in php gehen. Mit Referenzen, Rekursion etc. sollte das schon klappen.

[Coragon Rivito]

meinst du das: http://php-resource.de/tutorials/read/21/1/ ?
hab auch länger gebraucht um das zu begreifen, aber irgendwann machts 'klick' und du begreifst die aus dem ff

[polar]

ja das ist eine baumstruktur

aber ich möchte nichts über sql in eine db einfügen oder auslesen. ich brauch so eine baumstruktur für php. wird sich wahrscheinlich nur über eine klasse realisieren lassen.

dachte nur, das hier jemand auf dem board sowas schonmal umgesetzt hat, würde mir etwas zeit ersparen

[Troublegum]

Dazu brauchst du nochnichtmal eine Klasse. Das ist eigentlich ein klassisches Beispiel für Rekursion.

Du könntest es so machen:
Du baust den Baum von unten auf, ein Eintrag ist ein Array mit den Feldern "Name", "lParent" und "rParent". lParent und rParent sind Referenzen auf die jeweiligen übergeordneten Punkte.

Das erfordert natürlich auch eine rekursive Eingabe der Daten.
Das kannst du umgehen, wenn du die Datenstruktur wie folgt aufbaust:
datenarray[parentid][id]=Name
Den Datenarray könntest du recht leicht per Hand aufbauen und mit php ausgeben.

[polar]

hmm also irgendwie check ich das doch noch nicht so ganz

ich erklär mal was ich vor habe:

eine root verzeichnis von oben bis unten durchgehen (alle dir's und files in einer baumstruktur ablegen)

ein entsprechende rekursive funktion, die nach dir's und files unterscheidet hab ich schon. allerdings blick ich jetzt nicht so ganz wie ich meine baumstruktur aufbauen soll. elemente für das array währen zb.

- aktueller verzeichnisname
- alle enthaltenen files in dieser form: array(filename => size)
- und dann noch vorgänger und nachfolger??

aber wie füll ich das array dann am besten bzw. woher weiss ich wo ich bin und wo ich was einfügen soll??