023
31.10.2003, 13:32 Uhr
virtual
Sexiest Bit alive
(Operator)
|
@DerLiebeGast
Auch das geht ganz ohne lokale Variablen. Denn wenn man wirklich sinnvoll iterieren möchte, dann wird man pro knoten einen VErweis auf den Mutterknoten mit speichern, der die erfoderliche Info enthält. Dies würde man unabh. vom rekursiven oder iterativen Ansatz so halten:
| C++: |
struct baum
{
struct baum* mutter;
struct baum* kleiner;
struct baum* groesser;
int wert
};
const struct baum* naechster(
const struct baum* baum)
{
if (baum->groesser)
{
/* Nächster ist als das kleinste Element im
groesser baum... */
baum = baum->groesser;
while (baum->kleiner) baum = baum->kleiner;
return baum;
}else if (baum->mutter)
{
if (baum->mutter->kleiner == baum)
{
/* Nächst größeres Element is also mutter knoten */
return baum->mutter;
}else
{
/* Nächst größeres Element ist der direkte oder indirekte
mutter knoten, der uns als kleiner unterbaum enthält. */
while (baum->mutter && baum->mutter->groesser == baum) baum = baum->mutter;
baum = baum->mutter;
if (!baum) return NULL;
return baum->mutter
}
}
return NULL;
}
/* ungetestet */
|
Spezielle beim kompletten Baumdurchlauf wird man eh auf die Rekursive Variante verzichten, weil sie zu viele Einschränkungen mit sich bringt: Mit der iterativen Variante schreibe ich einmal zwei Routinen, die mir das erste element gbit und eine die mir das jeweils nächste gibt und kann das universell einsetzen:
| C++: |
struct baum* element = erstes_element(wurzel);
while(element)
{
...
element = naechster(element);
}
|
Das geht naturgegebenermassen mit einem rekursiven Ansatz nicht, bzw. macht keinen sonderlichen sinn: man könnte höchstens eine Routine for_each schreiben, die einen Callback enthält zum bearten der einzelnen Elemente:
| C++: |
void f(struct baum* b)
{
...
}
foreach(wurzel, f);
|
Wobei man hier dann mit erheblichen Einschränkungen leben muß, was man für Callbaks formulieren darf (hinsichtlich parametern). Ich würde da sehr stark für die iterative Variante plädieren, weil sie hier vermutlich nicht nur schneller, sondern auch deutlich flexibler ist.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
.
