Hallo,
dies ist mein erster Eintrag ins Forum, ich hoffe meine Frage ist hier richtig gestellt worden
Es geht darum, dass ich die PreOrder und die InOrder eines Binärbaumes kenne und einen Algorithmus entwickeln wollte, der daraus die PostOrder konstruieren kann. Dies ist mir auch gelungen (zumindest theoretisch auf dem Papier)
Ich habe meine Idee in einer Implementierung versucht umzusetzen, bekam jedoch folgendes Problem.
Ich möchte, dass sich die Methode PreIntoPost rekursiv aufruft und dabei Integer-Zahlen in das PostOrder-Array reinschreibt. Bei jedem Eintrag eines Integers soll sich die Variable n um 1 erhöhen, denn sie zeigt auf die Position im PostOrder-Array in welche als nächstes geschrieben wird.
Das PreOrder-Array sieht so aus --> (5,3,2,5,7,8)
Das InOrder-Array so --> (2,3,5,5,7,8)
als Ausgabe erhalte ich jedoch das Postorder-Array --> (5,0,0,0,0,0)
Die 5 sollte eigentlich als letztes Element im PostOrder stehen, von daher kann ich mir vorstellen, dass sich die Variable n möglicherweise immer wieder auf 0 zurücksetzt. Anders kann ich mir dieses Ergebnis nicht erklären.
Der Quellcode ist etwas lang und ich möchte nicht unverschämt sein, aber vielleicht hat jemand Lust mal drüberzuschauen und findet vielleicht die Lösung des Problems. Wäre auf jeden Fall sehr dankbar ;-)
Hier ist der Quellcode:
Viele Grüße,
4lpacino
dies ist mein erster Eintrag ins Forum, ich hoffe meine Frage ist hier richtig gestellt worden
Es geht darum, dass ich die PreOrder und die InOrder eines Binärbaumes kenne und einen Algorithmus entwickeln wollte, der daraus die PostOrder konstruieren kann. Dies ist mir auch gelungen (zumindest theoretisch auf dem Papier)
Ich habe meine Idee in einer Implementierung versucht umzusetzen, bekam jedoch folgendes Problem.
Ich möchte, dass sich die Methode PreIntoPost rekursiv aufruft und dabei Integer-Zahlen in das PostOrder-Array reinschreibt. Bei jedem Eintrag eines Integers soll sich die Variable n um 1 erhöhen, denn sie zeigt auf die Position im PostOrder-Array in welche als nächstes geschrieben wird.
Das PreOrder-Array sieht so aus --> (5,3,2,5,7,8)
Das InOrder-Array so --> (2,3,5,5,7,8)
als Ausgabe erhalte ich jedoch das Postorder-Array --> (5,0,0,0,0,0)
Die 5 sollte eigentlich als letztes Element im PostOrder stehen, von daher kann ich mir vorstellen, dass sich die Variable n möglicherweise immer wieder auf 0 zurücksetzt. Anders kann ich mir dieses Ergebnis nicht erklären.
Der Quellcode ist etwas lang und ich möchte nicht unverschämt sein, aber vielleicht hat jemand Lust mal drüberzuschauen und findet vielleicht die Lösung des Problems. Wäre auf jeden Fall sehr dankbar ;-)
Hier ist der Quellcode:
Java:
public class Aufgabe8 {
public static void main(String[] args) throws Exception{
int[] pre = {5,3,2,5,7,8};
int[] in = {2,3,5,5,7,8};
int[] Post = new int[pre.length];
int[] A = preIntoPost(pre, in, Post, 0);
for(int j=0;j<A.length;j++){
System.out.print(A[j]);
}
}
public static int[] preIntoPost(int[] pre, int[] in, int[] Post, int n){
if (pre.length!=0){
if (pre.length==1){
Post[n]=pre[0];
n++;
}
else{
//Wurzel ist erstes Element im PreOrder
int wurzel = pre[0];
//Suche Wurzel im InOrder
int WurzPos=0;
while (in[WurzPos]<=wurzel){
if(WurzPos<in.length) WurzPos++;
}
if(WurzPos<in.length) WurzPos-=1;
if(WurzPos!=0&&WurzPos!=in.length){
//Initialisierung der Arrays für die Teilbäume
int[] pre_lbaum = new int[WurzPos];
int[] in_lbaum = new int[WurzPos];
int[] pre_rbaum = new int[in.length-WurzPos-1];
int[] in_rbaum = new int[in.length-WurzPos-1];
//Befüllen der Arrays
System.arraycopy(pre, 1, pre_lbaum, 0, pre_lbaum.length);
System.arraycopy(in, 0, in_lbaum, 0, in_lbaum.length);
System.arraycopy(pre, WurzPos+1, pre_rbaum, 0, pre_rbaum.length);
System.arraycopy(in, WurzPos+1, in_rbaum, 0, in_rbaum.length);
//rekursiver Aufruf von preIntoPost
preIntoPost(pre_lbaum,in_lbaum,Post,n);
preIntoPost(pre_rbaum,in_rbaum,Post,n);
Post[n]=wurzel;
n++;
}
else if(WurzPos==0){
//Initialisierung der Arrays für die Teilbäume
int[] pre_rbaum = new int[in.length-WurzPos-1];
int[] in_rbaum = new int[in.length-WurzPos-1];
//Befüllen der Arrays
System.arraycopy(pre, 1, pre_rbaum, 0, pre_rbaum.length);
System.arraycopy(in, 1, in_rbaum, 0, in_rbaum.length);
//rekursiver Aufruf von preIntoPost
preIntoPost(pre_rbaum,in_rbaum,Post,n);
Post[n]=wurzel;
n++;
}
else {
//Initialisierung der Arrays für die Teilbäume
int[] pre_lbaum = new int[WurzPos];
int[] in_lbaum = new int[WurzPos];
//Befüllen der Arrays
System.arraycopy(pre, 1, pre_lbaum, 0, pre_lbaum.length);
System.arraycopy(in, 0, in_lbaum, 0, in_lbaum.length);
//rekursiver Aufruf von preIntoPost
preIntoPost(pre_lbaum,in_lbaum,Post,n);
Post[n]=wurzel;
n++;
}
}
}
return Post;
}
}Viele Grüße,
4lpacino
