Suchweg durch Binärbaum speichern

[Gucky]

Hallo liebes JavaForum,
ich programmiere zur Zeit ein Programm für die Schule, für das ich den Suchweg durch einen Binärbaum in Form eines boolean Arrays speichern muss. Das Durchlaufen habe ich Rekursiv implementiert. Den Code findet ihr unten. Für das Speichern des Weges habe ich aber keine Ahnung. Der Baum muss vollständig durchlaufen werden. Wenn ihr also eine kleine Idee hättet, wie ich mein Problem lösen könnte, wäre ich euch sehr dankbar. Es ist dringend, da es für eine Facharbeit ist, für die ich nur noch wenig Zeit habe.
Schon mal danke an alle, die sich mit meinem Problem beschäftigen. 🙂

public ArrayList<ByteContainer> getCodeArrayListRek(Knoten knoten, ArrayList<ByteContainer> codeArrayList){
//	ByteContainer tempByteContainer = new ByteContainer(); Hier drin soll der Wert des Blatts, sowie der Weg gespeichert werden
//	if (knoten instanceof EndKnoten) codeArrayList.add(tempByteContainer);
	if (knoten.getNext(false) != null){
		getCodeArrayListRek(knoten.getNext(false), codeArrayList);
	}
	if (knoten.getNext(true) != null){
		getCodeArrayListRek(knoten.getNext(true), codeArrayList);
	}
	return codeArrayList;
}

 

[DrZoidberg]

Hier ist mal ein Ansatz.

public ArrayList<ByteContainer> getCodeArrayListRek(Knoten knoten, ArrayDeque<Boolean> suchweg, ArrayList<ByteContainer> codeArrayList){
    if (knoten.getNext(false) != null){
        suchweg.push(false);
        getCodeArrayListRek(knoten.getNext(false), suchweg, codeArrayList);
        suchweg.pop();
    }
    if (knoten.getNext(true) != null){
        suchweg.push(true);
        getCodeArrayListRek(knoten.getNext(true), suchweg, codeArrayList);
        suchweg.pop();
    }
    return codeArrayList;
}

 

[Gucky]

Vielen Dank, für deinen Ansatz. Ich habs jetzt dank deinem Ansatz so gelöst. Da ich noch über den Weg iterieren können muss und noch während des Durchlaufs auf diesen zugreifen können muss, habe ich eine ArrayList benutzt. Ich wäre dir sehr dankbar, wenn du einmal drüber gucken könntest:

/**
 * Diese Methode erstellt in einem aufwändigen Verfahren die CodeArrayList
 * @param knoten
 * @param codeArrayList
 * @param schritte
 * @param weg
 */
private void getCodeArrayListRek(Knoten knoten,
		ArrayList<ByteContainer> codeArrayList, int schritte, ArrayList<Boolean> weg){
	weg = ArrayListUtil.trim(weg, schritte);
	
	if (knoten instanceof EndKnoten){
		ByteContainer tempByteContainer = new ByteContainer();
		EndKnoten tempEndKnoten = (EndKnoten) knoten;
		tempByteContainer.setCodierung(toBooleanArray(weg));
		tempByteContainer.setWert(tempEndKnoten.getWert());
		codeArrayList.add(tempByteContainer);
	}
	if (knoten.getNext(false) != null){
		schritte++;
		weg.add(new Boolean(false));
		getCodeArrayListRek(knoten.getNext(false), codeArrayList, schritte, weg);
	}
	if (knoten.getNext(true) != null){
		schritte++;
		weg.add(new Boolean(true));
		getCodeArrayListRek(knoten.getNext(true), codeArrayList, schritte, weg);
	}
}

/**
 * 
 * @param paramList
 * @return Liste als boolean Array
 */
private boolean[] toBooleanArray(ArrayList<Boolean> paramList){
	boolean[] tempArray = new boolean[paramList.size()];
	for (int i=0;i<tempArray.length;i++){
		tempArray[i] = paramList.get(i).booleanValue();
	}
	return tempArray;
}

 

[DrZoidberg]

Das sieht nicht ganz richtig aus.
Wenn sowohl knoten.getNext(false) als auch knoten.getNext(true) ungleich null sind, dann erhöhst du "schritte" insgesamt um 2.
Du brauchst "schritte" im übrigen auch gar nicht, wenn du das letzte Element von "weg" wieder entfernst so wie in meinem Beispiel.

Ich würde es so schreiben.

private void getCodeArrayListRek(Knoten knoten,
        ArrayList<ByteContainer> codeArrayList, ArrayDeque<Boolean> weg){
    
    if (knoten instanceof EndKnoten){
        ByteContainer tempByteContainer = new ByteContainer();
        EndKnoten tempEndKnoten = (EndKnoten) knoten;
        tempByteContainer.setCodierung(toBooleanArray(weg));
        tempByteContainer.setWert(tempEndKnoten.getWert());
        codeArrayList.add(tempByteContainer);
    }
    if (knoten.getNext(false) != null){
        weg.push(false);
        getCodeArrayListRek(knoten.getNext(false), codeArrayList, weg);
        weg.pop();
    }
    if (knoten.getNext(true) != null){
        weg.push(true);
        getCodeArrayListRek(knoten.getNext(true), codeArrayList, weg);
        weg.pop();
    }
}

private void getCodeArrayListRek(Knoten knoten) {
    getCodeArrayListRek(knoten, new ArrayList<ByteContainer>(), new ArrayDeque<Boolean>());
}

private boolean[] toBooleanArray(Collection<Boolean> paramList){
    boolean[] tempArray = new boolean[paramList.size()];
    int i = 0;
    for(boolean elem: paramList) {
        tempArray[i++] = elem;
    }
    return tempArray;
}

 

[Gucky]

Auf die Idee mit der for-each Schleife bin ich nicht gekommen. Stimmt. Die gibt's ja auch noch. 😀
Ich hatte jetzt auch eine Möglichkeit mit der ArrayList aber deine mit dem Stapel ist besser. Die hab ich jetzt noch ein bisschen angepasst und jetzt sieht es so aus, als laufe es. Falls nicht, wirst du hier von mir hören 😀.

Vielen Dank, für deine Mühen. 🙂