Rekursion Stammbaum durchlaufen

[Peter]

Hallo

Ich blicke nicht mehr durch. Seit Stunden versuche ich einen vorgegebenen Stammbaum zu durchlaufen. Gegeben ist eine Klasse EmptyPerson:

class EmptyPerson extends Person {
    public boolean isEmpty() {
        return true;
    }
    public String getName() {
        return "";
    }
    public int getAge() {
        return 0;
    }
    public Person getFather() {
        return empty;
    }
    public Person getMother() {
        return empty;
    }
}

und eine Klasse Person

class Person {
    static Person empty = new EmptyPerson();
    String name;
    int age;
    Person father, mother;

public boolean isEmpty() {
        return false;
    }
    public String getName() {
     String name="name";
        return name;
    }
    public int getAge() {
        return age;
    }
    public Person getFather() {
        return father;
    }
    public Person getMother() {
        return mother;
    }

Mit Hilfe Rekursion oder Iteration soll nun die älteste Person im Stammbaum zurückgegeben werden

public Person eldestPerson() {}

Ich habe das so versucht:

public int maxAge() {
//liest das Alter der ältesten Person aus

if(this.isEmpty()) {
      return empty.getAge();
     }

int i = Math.max(this.getAge(),getFather().maxAge());
     int j = Math.max(this.getAge(),getMother().maxAge());
     return Math.max(i,j);
 }

Aber so kann ich nur das Alter zurückgeben und nicht das Objekt...

also hab ichs so versucht:

public String eldestPerson() {
        if(myEldestFather().getAge()>myEldestMother().getAge()) {
         return myEldestFather();
        }else{
         return myEldestMother();
        }
    }

public Person myEldestFather() {
     if(getAge()==maxAge()) {
      return this;
     }else {
      return getFather().myEldestFather();
     }
    }

public Person myEldestMother() {
     if(getAge()==maxAge()) {
      return this;
     }else {
      return getMother().myEldestMother();
     }
    }

Stimmt aber auch nicht. *Verzeiflung*

Ich habe auch schon versucht alle Personen in einen Vektor zu schreiben um das ganze dann iterativ auszulesen, ist mir aber auch nicht gelungen...

Wäre schön wenn da jemand wäre der mir helfen könnte.

Gruss Peter

[Tim Tepaße]

Hallo Peter,

Ich blicke nicht mehr durch. Seit Stunden versuche ich einen vorgegebenen
Stammbaum zu durchlaufen. Gegeben ist eine Klasse EmptyPerson:

Das hört sich für mich wie eine Übungsaufgabe an. ;-)

Mit Hilfe Rekursion oder Iteration soll nun die älteste Person im
Stammbaum zurückgegeben werden

public Person eldestPerson() {}

Wenn man rekursiv vorgehen soll (was ja auch nahe liegt), dann braucht diese
Funktion doch irgendwo einen Startpunkt. Kriegt sie keine Person als
Vorgabe (Parameter, Argument)und arbeitet sich von dort über deren Eltern
nach oben? Ich würde das für logisch halten.

(Wahrscheinlich soll diese Methode zur Klasse Person gehören, nich?)

Ich kommentiere mal Deinen ersten Ansatz etwas durch:

public int maxAge() {
//liest das Alter der ältesten Person aus

Wieso definierst Du hier eine extra Methode? Du sollst doch letztendlich
die älteste Person im Stammbaum zurückgeben. Wenn Du erst das Alter
bestimmst, dann mußt Du noch irgendwie die zum Alter passende Person
herausfinden und das könnte eklig werden.

if(this.isEmpty()) {
      return empty.getAge();
     }

Hier kommst Du die Abruchbedingung der Rekursion näher. Aber Du gibst das
Alter zurück und eben nicht die Person.

int i = Math.max(this.getAge(),getFather().maxAge());
     int j = Math.max(this.getAge(),getMother().maxAge());

Und hier achtest Du auch nur auf auf das Alter und nicht auf die Person...

Aber so kann ich nur das Alter zurückgeben und nicht das Objekt...

... aber das hast Du schon richtig erkannt.

Du warst aber mit der Rekursion auf der richtigen Spur. Du mußt nur ein
kleines bisschen mehr Code schreiben. Die Funktion muß dieses tun:

1. Die Funktion kriegt eine Person übergeben.
2. Zuerst testet sie, ob diese Person überhaupt existiert, wenn nein, gibt
   sie diese komische EmptyPerson zurück und beendet sich.
3. Ansonsten ruft sie sich selber auf, einmal für den Vater, einmal für
   die Mutter und kriegt somit zwei Personen zurück.
4. Nun vergleicht sie das Alter der drei Personen, der übergebenen und der
   zwei durch die Rekursion zurückbekommenen.
5. Sie gibt die Person zurück, deren Alter das höchste ist.

Wenn man es erst einmal hat, ist der Gedankensprung in Zukunft nicht mehr
so schwer. Um mich in Python etwas einzugewöhnen, habe ich mal eine mehr
schlechte als rechte (aber funktionierende) Version in Python geschrieben.
Deine Frage kam mir also gerade recht. ;-) Vielleicht hilft es Dir ja beim
Verstehen. Ich habe die Klasse aber stark verändert, vor allem durch den
Verzicht auf das in meinen Augen absurde EmptyPerson und die nervigen
get-Methode. http://tepasse.org/2003/01/27/stammbaum.py

Tim

[dimitri rettig]

hallo,

Wenn man rekursiv vorgehen soll (was ja auch nahe liegt), ...

das würde ich nicht sagen. obwohl die rekursive vorgehensweise ziemlich elegant aussieht, ist es doch meistens so, dass die bei größeren datenmängen, in diesem falle einem großen stammbaum, auf grund ihrer trägheit versagt, weil einfach zu viele daten auf dem stack gelagert werden.

mit freundlichen grüßen
   dimitri rettig