[php] Passender Allgorithmus zum Baumkinder berechnen?

[Marc Linke]

Hallo,

(Quizfrage fuer tueftler;)

ich moechte in einem baum gerne jedem knoten mitteilen, welche
kinder unter ihm sind.

Der baum sieht, vergleichbar mit einem directory,
etwa wie folgt aus:

n     name              id     tiefe   topid

1  -+ Vater1            (1)     (0)     (0)
    |
2   +-+ Kind1          (12)     (1)     (1)
    |
3   +-+ Kind2          (13)     (1)     (1)
    | |
4   | +-+ Enkel1       (54)     (2)    (13)
    | | |
5   | | +-+ Urenkel1   (80)     (3)    (54)
    | |
6   | +-+ Enkel2       (55)     (2)    (13)
    |
7   +-+ Kind3          (16)     (1)     (1)

8  -+ Vater2            (7)     (0)     (0)

usw.

Dabei liegt er auch genau so sortiert als array vor:

$arr[1]["name"]="Vater1"         Der name des knotens
$arr[1]["id"]=1                  Eine eindeutige id
$arr[1]["topid"]=0               Die id des vaterknotens
$arr[1]["tiefe"]=0               Die tiefe des knotens im baum

Hierbei bezieht sich $arr[1] auf den obersten eintrag in einer
visuellen darstellung, hat also nichts mit der "id" zu tun!
(Darum hab ich im beispiel die id's mal etwas durcheinander
 angegeben)
Topid referenziert den Vater. Ein objekt kann viele Kinder
aber nur einen Vater haben.

Diese daten sind vorgegeben.

Nun möchte ich gerne eine weitere spalte in dem
array aufnehmen:

$arr[n]["childs"]=array(alle kinder)

Diese soll also ein array mit allen kindern dieses knotens
enthalten.
Im beispiel also etwa:

$arr[1]["childs"]=array(12,13,54,80,55,16)
$arr[2]["childs"]=array()
$arr[3]["childs"]=array(54,80,55)

Da diese Baeume bei mir leicht 500 eintraege lang werden
koennen ist nun die frage, was ist ein effizienter allgorithmus
um mit moeglichst wenig iterationen/rekursionen das
array mit den gesuchten ergebnissen zu fuellen?

Bisher sehe ich nur den offensichtlichen ansatz iterativ
durch das gesamte array zu gehen und dann rekursiv zu
jedem die kinder suchen und zurueck geben/eintragen.
Sehr ineffizient, da ich viele zweige des baumes unnoetiger
weise(?) mehrfach durchlaufe.

Jemand ein Tipp wie es besser ginge?





_________________________________________________________
Do You Yahoo!?
Get your free _(at)_yahoo.com address at http://mail.yahoo.com