Hilfe beim Algorithmus finden von Buchstabenbaumtraversierung

[neuesich]

Hallo,

Ich habe Probleme um einen Algorithmus zu finden für folgendes Problem:

Ich habe einenBaum mit dynamischer Anzahl an Kindern . Dabei soll jeder Zweig als Wort interpretiert werden und in einer Liste gespeichert werden.


müsste dann die 3 Worte: hallo, halle, haus als Elemente in einer Liste von char[] ausgeben.

Ganz intuitiv habe ich eine Funktion geschrieben, die die einzelnen Buchstaben ausgibt:

	void test(node n){
		
		for(int index=0; index<n.getChildren().size();index++){
			System.out.println(n.getChildren().get(index).getLetter());
			this.test(n.getChildren().get(index));
			
		}
	}

getChildren() gibt eine Liste (ArrayList<node>) an Knoten zurück und getLetter() gibt den Buchstaben des Knotens zurück.


Aber wie kann ich die Buchstaben geeignet festhalten? Durch das rekursive Aufrufen finde ich das sowieso schwierig, das ließe sich doch nur mit static-Variablen realisieren lösen, oder? Ansonsten wäre meine einzige Idee eine globale Liste und ein globales,temporäres char-Array.

Ich bin für jeden Hinweis dankbar!

Viele Grüße

 

[Akeshihiro]

Gibt vielleicht auch andere Möglichkeiten, aber ich verwende bei sowas immer einen zusätzlichen Parameter akku, der den Fortschritt bis zur jeweiligen Rekursionstiefe festhält, damit man damit arbeiten kann, entweder in der Rekursionstiefe selbst oder er wird entsprechend erweitert und an die nächsten Rekursionstiefen weitergegeben, damit er dort weiter verarbeitet werden kann. Mit folgender Methodensignatur habe ich deine Aufgabe da ziemlich fix lösen können:

public List<char[]> extractWords(Node node, char[] akku)

Ich hoffe, das hilft dir weiter. Auf das Ergebnis brauchst du aber nicht hoffen, wir machen hier keine Hausaufgaben, tut mir leid

 

[neuesich]

	public ArrayList<char[]> getWords(node n, String buffer){
		ArrayList<char[]> res = new ArrayList<char[]>();
		
		ArrayList<node> childs = n.getChildren();
		for(int i=0; i<childs.size(); i++){
			if(childs.get(i)!=EOW){
				getWords(childs.get(i), buffer+childs.get(i).getLetter());
			}
			else
				//System.out.println(buffer.toCharArray());
				res.add(buffer.toCharArray());
			
		}
		
		return res;
	}

Das Problem wie ich die Liste festhalten soll bleibt bestehen (es sei denn die schlepp ich auch als Parameter mit oder deklariere sie global). Gibt es vielleicht eine Möglichkeit das iterativ zu lösen?

Auf jeden Fall schon mal danke für die Hilfe!
vlg

 

[Akeshihiro]

Nein, die Ergebnismenge brauchst du nicht als Parameter mitschleppen, die wird ja als Rückgabe wieder zurück gegeben. Musst du nur zusammenfügen.

 

[neuesich]

Ach stimmt vielen Dank! Manchmal sieht man den Wald vor lauter Bäumen nicht
Zeile 7 ersetzt durch:

res.addAll(getWords(childs.get(i), buffer+childs.get(i).getLetter()));

Ist somit erledigt!