# Binärbaum (PreOrder, InOrder, PostOrder)



## Gratwanderer (15. Jun 2010)

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:


```
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


----------



## SlaterB (15. Jun 2010)

http://www.java-forum.org/hausaufgaben/101805-binaerbaume-preorder-postorder.html

(edit: zur ersten Ansicht von Alternativen, dort ist ein weiterer Thread verlinkt, 
ich schaue später noch deinen Code an, falls vorher nicht wer anders kommt)


----------



## SlaterB (15. Jun 2010)

also zum n, das wird tatsächlich nicht von den rekursiven Aufrufen zurück in die ursprüngliche Methode erhöht,
was ganz einfach zu testen ist und eigentlich Wochen bis Jahre vor so eine komplizierten Methode zum eingemeißelten Grundwissen gehören sollte,

statt n könntest du als Parameter ein int[1] übergeben, dessen erhöhte Werte sieht auch der Aufrufer
(zum Vergleich: nicht aber das neue Array, falls eine Untermethode der Parameter-Variablen ein neues Array zuweist)


----------



## Gratwanderer (15. Jun 2010)

Hallo SlaterB,

vielen Dank für deine schnelle Antowrt. Du hast völlig recht, ich habe teilweise noch große Lücken. Aber ich bin dabei sie zu füllen ;-)

Habe das jetzt versucht mit einem int[1] zu lösen anstatt dem n, bekomme jedoch folgende Fehlermeldung:

Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	The method preIntoPost(int[], int[], int, int, int) in the type Aufgabe8 is not applicable for the arguments (int[], int[], int[], int)

	at PreInToPost.Aufgabe8.main(alt.java:23)

Ich kann mir die Fehlermeldung nciht erklären, denn ich habe der Methode doch als Argumente 4 Arrays gegeben?!

Hier nochmal der Code:


```
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[] A = {0};
	        int[] Post = new int[pre.length];

	        int[] C = preIntoPost(pre, in, Post, A);

	        for(int j=0;j<C.length;j++){
	            System.out.print(C[j]);
	        }
	    }

	    
	    public static int[] preIntoPost(int[] pre, int[] in, int[] Post, int[] A){

	    if (pre.length!=0){

	        if (pre.length==1){
	            Post[A[0]]=pre[0];
	            A[0]++;
	        }
	        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,A);
	                preIntoPost(pre_rbaum,in_rbaum,Post,A);

	                Post[A[0]]=wurzel;
	                A[0]++;
	            }
	            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,A);

	                Post[A[0]]=wurzel;
	                A[0]++;
	            }
	            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,A);

	                Post[A[0]]=wurzel;
	                A[0]++;
	            }
	        }
	    }
	    return Post;
	    }
	}
```

Gruß,

4lpacino


----------



## Eldorado (15. Jun 2010)

Also bei mir führt er es ohne Meldung aus. Ausgabe: 253875
mfg
Eldorado


----------



## Gratwanderer (15. Jun 2010)

Ok, habe es jetzt mal über die Eingabeaufforderung laufen lassen, da lief es auch! 

Super, vielen Dank an euch!! :toll:

Gruß,

4lpacino


----------



## Smagjus (15. Jun 2010)

Das Internet ist vielleicht klein 

@Gratwanderer
Du bist nicht rein zufällig aus dem Kurs Informatik I der Uni Köln?

Hab bis eben verzweifelt an dieser Aufgabe gesessen und im Internet nach Hilfe gesucht. Konnte wie du meinen Algorithmus nicht in ein Programm umsetzen (hab's mit Rekursion versucht).

Gruß Justin


----------

