[php] Passender Allgorithmus zum Baumkinder berechnen?

[Marc Linke]

Hi Juri,

----- Original Message -----
From: "Juri.Smarschevski" <smj_(at)_intratools.de>
To: <php_(at)_phpcenter.de>
Sent: Monday, May 14, 2001 1:21 PM
Subject: RE: [php] Passender Allgorithmus zum Baumkinder berechnen?


> > 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)
>
> Mit diesem Baum-Struktur geht's wohl nicht besser.
> Du koenntest rein theoretisch versuchen von "unten" anzufangen,
> ebene pro ebene, und schon fertige Child-Ergebnisse sollen
> beim Erfassen eines Nodes beruecksichtigt werden.

Danke, genau das ist die loesung.
Ich habe ja bei jedem array die tiefe im baum.

Nun brauche ich 2 durchlaeufe durch das komplette array $arr:

1. - Ermitteln der maximalen tiefe $maxtiefe
   - Anlegen des hilfsarrays $h das einfach nur von
     "id" auf "n" referenziert.
   - Anlegen eines weiteren hilfsarrays $d das nach der
     tiefe sortiert wiederum auf "n" referenziert.

 for ($n=0; $n<count($arr); $n++) {
   $h[$arr[$n]["id"]]=$r;
   $d[$arr[$n]["tiefe"]][]=$n;
   if ($arr[$n]["tiefe"]>$maxtiefe) $maxtiefe=$arr[$n]["tiefe"];
 }

2. (Die krankeste zeile code, die ich je programmiert habe;)
   - Von der tiefsten ebene angefangen jeweils die "id"
     des kindes und die der eigenen kinder an den vater
     uebergeben.

 for ($r=$maxtiefe; $r>=0; $r--) {
   for ($i=0; $i<count($d[$r]); $i++) {
    $arr[$h[$arr[$d[$r][$i]]["topid"]]]["childs"].=
       $arr[$d[$r][$i]]["id"].",".$arr[$d[$r][$i]]["childs"];
   }
 }

Es funktioniert (in dem fall nur als string mit kommatas
separiert weil ichs so leichter debuggen kann) in 2*count($arr)
schleifendurchlaeufen.
Der spaghetticode laesst sich sicher noch was optimieren
aber das ergebnis ist so doch schon ok. Damit kann ich leben.

> Die gesamte Loesung bleibt IMHO trotzdem ineffizient.

Ich glaub das ist schon recht effizient so. Es sollte bestenfalls
auch mit count($arr) schleifendurchlaeufen machbar sein aber
davon war bei dem vorliegenden array eh nicht auszugehen
und der code in den schleifen sollte vertretbar sein.

danke



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