Stammbaum durchlaufen (Iteration etc)

[kellogz1302]

Hallo zusammen,

ich stehe vor folgender Aufgabe:

Es soll eine Klasse Person erstellt werden, diese Person hat eine ArrayList an Nachfolgern. Von diesen Personen gibt es logischerweise jetzt ein paar Stück, so dass hinterher eine Art Könige-Abstammungs-Baum entsteht. Sprich: Teilweise gibt es nur einen Nachfolger, manchmal jedoch auch 3 oder 4 oder eben gar keinen.

Soweit, so gut.

Klasse Person sieht derzeit folgendermaßen aus:

 import java.util.ArrayList;
public class Person{

	private String name;
	private ArrayList<Person> nachfolger = new ArrayList<Person>();

	public Person(String name){
		this.name = name;
	}

	public String getName(){
		return name;
	}
	
	public void setName(){
		this.name = name;
	}

	}

	public void addNachfolger(Person nachfolgender){
		nachfolger.add(nachfolgender);
	}	

	public String toString(){
		return name + " (" +  nachfolger.size() + " 	Nachfolger)\n";
	}
}

Zusaetzlich gibt es eine Klasse Karolingerreich, die dieses tolle Reich erstellt. Diese hab ich wie folgt erstellt:

public class Karolingerreich{
	public static void main(String[] args){
		Person karl = new Person("Karl der Große");
		Person ludwig = new Person("Ludwig der Fromme");
		Person lothar = new Person("Lothar");
		Person pippin = new Person("Pippin");
		Person ludwigd = new Person("Ludwig der Deutsche");
		Person karlk = new Person("Karl der Kahle");
		Person ludwig2 = new Person("Ludwig II.");
		Person karlmann = new Person("Karlmann");
		Person ludwig3 = new Person("Ludwig III.");
		Person karld = new Person("Karl der Dicke");
		Person arnulf = new Person("Arnulf von Kaernten");
		Person ludwigk = new Person("Ludwig das Kind");
		//Nachfolger
		karl.addNachfolger(ludwig);
		ludwig.addNachfolger(lothar);
		ludwig.addNachfolger(pippin);
		ludwig.addNachfolger(ludwigd);
		ludwig.addNachfolger(karlk);
		lothar.addNachfolger(ludwig2);
		ludwigd.addNachfolger(karlmann);
		ludwigd.addNachfolger(ludwig3);
		ludwigd.addNachfolger(karld);
		karlmann.addNachfolger(arnulf);
		arnulf.addNachfolger(ludwigk);
}
}

und jetzt geht es ans Eingemachte:

Durch jeweils eine iterative Suchmethode soll per Breitensuche und Tiefensuche folgendes ausgegeben werden:

Ausgabe Breitensuche:

Karl der Grosse (1 Nachfolger)
Ludwig der Fromme (4 Nachfolger)
Lothar (1 Nachfolger)
Pippin (0 Nachfolger)
Ludwig der Deutsche (3 Nachfolger)
Karl der Kahle (0 Nachfolger)
Ludwig II. (0 Nachfolger)
Karlmann (1 Nachfolger)
Ludwig III. (0 Nachfolger)
Karl der Dicke (0 Nachfolger)
Arnulf von Kaernten (1 Nachfolger)
Ludwig das Kind (0 Nachfolger)

Ausgabe Tiefensuche:
Karl der Grosse (1 Nachfolger)
Ludwig der Fromme (4 Nachfolger)
Karl der Kahle (0 Nachfolger)
Ludwig der Deutsche (3 Nachfolger)
Karl der Dicke (0 Nachfolger)
Ludwig III. (0 Nachfolger)
Karlmann (1 Nachfolger)
Arnulf von Kaernten (1 Nachfolger)
Ludwig das Kind (0 Nachfolger)
Pippin (0 Nachfolger)
Lothar (1 Nachfolger)
Ludwig II. (0 Nachfolger)

Trotz Google, lesen in Foren, lesen in Vorlesungsunterlagen bekomm ich nicht den richtigen Ansatz hin, geschweige denn eine Lösung. Ich hoffe, ihr könnt mir bei meinem Problem helfen!

Danke im Voraus

 

[Gucky]

Dafür wäre ein Baum wohl eher geeignet. In diesem Baum hat jeder Knoten eine ArrayList an Knoten, die nach ihm kommen. Jeder Knoten hat Eigenschaften, wie Name, Todesdatum etc.
Der Klasse Stammbaum, die die ganzen Personen verwaltet übergibst du dann etwas, um die Person zu identifizieren und die Nachfolger fügst du hinzu mit einer add...() Methode. Also so: addPerson("Ludwig der erste", "Ludwig der zweite") der erste String identifiziert die Person und mit dem zweiten String wird eine neue Person gemacht. Dann machst du noch getter und setter Methoden und du hast einen wunderschönen Baum.
Da du von Vorlesungsunterlagen sprachst, denke ich, dass ist eine Aufgabe um einen Baum zu erstellen.

 

[kellogz1302]

Hi,
zunächst danke für die rasche Antwort. Hier stellen sich nun folgende Probleme. Es gibt lediglich Namen, d.h. keine sonstigen Eigenschaften, lediglich die Beziehung zum "Vater". Hier mal der Aufgabentext dazu:

"Die Aufgabe dieser Übung wird es sein, eine Baumstruktur zu implementieren, die einen
kleinen Teil des Karolingerreichs nach Karldem Großen repräsentiert.
Hierfür wird zuerst ein Objekt Personbenötigt, die den jeweiligen Herrscher repräsentiert.
Jede dieser Personen bekommt eine Liste an Nachfolgern, unter denen ihr Reich aufgeteilt wurde.

a) Erstellen Sie eine Klasse Person, die einen String name
sowie eine ArrayList<Person> nachfolger beinhaltet.
Implementieren Sie die nötigen Getter und Setter sowie einen Konstruktor. Implementieren Sie zusätzlich eine Methode addNachfolger(...), die einer Person einenzusätzlichen Nachfolger
zuordnet sowie eine Methode toString(), die den Namen der Person und dieAnzahl der Nachfolger zurückgibt.

b)
Implementieren Sie eine Klasse Karolingerreich,die in der main-Methode einen Baum der folgenden Struktur mit Hilfe der Personen konstruiert:

Karl d.G. - Ludwig der Fromme - hier stünden jetzt 4 Nachfolger - Nun wieder Nachfolger etc."

Das Problem ist jetzt Aufgabe b) Hier haben wir auch keinerlei Anhaltspunkte, wie man vorgehen soll. Auch Bäume etc wurden nur kurz angerissen, vielleicht kann hier noch genauer geholfen werden? Vielen Dank!

 

[Gucky]

Guck dir mal BinärBäume in der Wikipedia an. Das ist praktisch dasselbe nur das du in deinem Fall beliebig viele Nachfolger hast.

EDIT: ich sehe grade, dass da steht "in der main Methode". Streng genommen ist deine Version richtig. Aber didaktisch ist dann die Aufgabenstellung schlecht. Mach mal lieber eine Klasse StammBaum.

Dann benutzt du halt als ID den Namen.

 

[kellogz1302]

Ja aber genau das ist es ja eben nicht, ein BinärBaum :rtfm::noe:

 

[Gucky]

Es ist aber fast dasselbe. Der Unterschied ist aber, dass du mehrere Referenzen haben KANNST. Der Unterschied ist nicht groß.

 

[kellogz1302]

Hm okay, also kann ich quasi den Binärbaum als "Ausgang" nutzen.

Nun zum Coden...nachdem ich mich nun Tag und Nacht damit beschäftigt habe, habe ich mittlerweile das Gefühl, gar nichts mehr zu wissen ... :autsch: Ich erzeuge also ein TreeSet?

PS: Danke für deien Mühe

 

[Gucky]

Da nicht für. Deshalb bin ich hier.
Du erzeugst kein TreeSet. Du implementierst es.

Du musst konkrete Fragen stellen, damit ich dir helfen kann.

 

[kellogz1302]

Okay, hab mich jetzt mal schlaugemacht, was es mit dem TreeSet auf sich hat. Diesen implementiere ich jetzt in der "Start/Main" Klasse Karolingerreich? In etwa so?

public static void main(String[] args){
    Set<Person> karolingerreich = new TreeSet<Person>();
    set.add(new Person("Karl"));
    System.out.println(karolingerreich);
}

Konkrete Frage jetzt hierzu:

Die Nachfolger habe ich ja über die jeweilige Person als ArrayList angehangen. Muss ich trotzdem nun alle Personen adden oder sind diese durch die "Verkettung" der Nachfolger automatisch im TreeSet? Sprich, wie definiere ich diese Knoten? So könnte ich das TreeSet ja noch nicht durchlaufen...

Vielen Dank für die Hilfe

 

[Gucky]

Kann man ein Set mit einem Sysout ausgeben?

Jetzt hast du einen Baum als ein Element in einen Baum eingefügt. Damit, dass du kein TreesSet erzeugst sondern implementierst, meinte ich, dass du eines selber schreibst.