Binärbaume. Mit In/Preorder zu Postorder!

B

Behnke

Mitglied
Aufgabe:
Entwickeln Sie einen rekursiven Algorithmus, der aus P und I die Postorder-
Durchmusterungsreihenfolge der Schlüssel in T berechnet und ausgibt.
Zum Vergrößern anklicken....
P = Preorder, I = Inorder
T ist unser Binärer Suchbaum

Was ich noch dazu sagen muss:
Es gibt Online zwar eine Binärbaum.java, aber wenn wir die bräuchten wäre das vermutlich in der Aufgabe angegeben. (So ist es zumindest immer).

Mein Gedankenansatz:
adc29232712b.JPG

(Der Beispielbaum dient zur Erklärung)

Preorder: 7, 1, 0, 3, 2, 5, 12, 9, 8, 10, 13, 15
Inorder: 0, 1, 2, 3, 5, 7, 8, 9, 10, 12, 13, 15

Im Preorder ist die Wurzel immer an erster Stelle (grün markiert).
Wenn ich die Wurzel nun im Inorder suche, sagt mir die Position wie groß die Teilbäume sind:

Preorder: 7, 1, 0, 3, 2, 5, 12, 9, 8, 10, 13, 15

So nun wollte ich beide Teilbäume rekursiv betrachten.
Teilbaum links = 1, 0, 3, 2, 5
Teilbaum links = 12, 9, 8, 10, 13, 15

1 und 12, sind ja die obersten Knoten.
Leider weiß ich absolut nicht wie ich das nun rekursiv anstelle. Ich bastel da nun schon lang rum und hab mich an MergeSort angelehnt, aber ist kommt nur murks raus ;(.
Ich hoffe ihr seht das ich nicht meine Aufgaben ergammeln will.

Lieben Gruß
 
Zuletzt bearbeitet:
S

SlaterB

Gast
es geht alles irgendwie, wenn du ein oder zwei Arrays hast, dann übergib diese an die rekursive Methode zusammen mit Begin/ End-Index
oder erstelle neue kleinere Unter-Arrays,
komplett will ich das eher nicht programmieren, das ist schon überwiegend deine Aufgabe
 
B

Behnke

Mitglied
Java: 
    public static void PretoPostorder(int[] A, int links, int mitte, int rechts){

        int wurzel = A[1];
        Rekursiv(A, links+1, mitte); //linker Teilbaum
        Rekursiv(A, mitte+1, rechts); //rechter Teilbaum
    }
    public static void Rekursiv(int[] A, int links, int rechts){

        if(links<=rechts){
            if(links==rechts) System.out.println(A[links]);
            int knoten = links;

            while(A[links]<=A[knoten]){
                if(links<A.length) links++;
            }

            Rekursiv(A, knoten+1, links-1);
            Rekursiv(A, links, rechts);
            if(knoten+1!=links) System.out.println(A[knoten]);
        }
    }

Hey ich habs fast! Brauche nur noch ein bisschen hilfe.
Er spuckt mir folgendes aus:

Code: 
0
2
5
3
1
8
10
9
15
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 13
        at aufgabe36.Main.Rekursiv(Main.java:83)
        at aufgabe36.Main.Rekursiv(Main.java:88)
        at aufgabe36.Main.Rekursiv(Main.java:88)
        at aufgabe36.Main.PretoPostorder(Main.java:75)
        at aufgabe36.Main.main(Main.java:125)
Java Result: 1
BUILD SUCCESSFUL (total time: 0 seconds)

Ich hab irgendwie ein Index problem. Und es ist fast die richtige Ausgabe.

Postorder wäre ja: 0, 2, 5, 3, 1, 8, 10, 9, 15, 13, 12, 7
Es fehlen nur noch zwei Zahlen und ich hab ein paar doppelt aufgrund der Knoten ausgabe unten.
Hm.. und wie ich die Variablen nun genau speicher weiß ich auch noch nicht!
Wie ihr seht, bin ich schon sehr wirr im Kopf von diesem Rekursiven kram :lol:

Edit:
es wäre ja noch interessant wie ich PretoPostorder aufrufe, daher mein Nachtrag:
Java: 
    public static int Teilbaeumebestimmen(int[] Inorder, int wurzel){

        int i=1;
        while(Inorder[i] < wurzel){
            i++;
        }

        return i;
    }
        
in der Main methode:
int k = Teilbaeumebestimmen(B, A[1]);
PretoPostorder(A, 1, k, 12);

Edit Edit: So jetzt gibt er nicht doppelt aus. Aber immernoch mein Array-fehler. Vielleicht krieg ich den ja auch noch raus
 
Zuletzt bearbeitet:
S

SlaterB

Gast
man muss schon die Zeilennummern im StackTrace geschickt interpretieren um herauszufinden, dass die Exception in der Zeile
> while(A[links]<=A[knoten]){
stattfindet, das hättest du auch ruhig verraten können,

anderseits ist es wiederum am Code sichtbar, links wird dort so oft erhöht, bis es eben kracht,
> if(links<A.length)
ist dabei leicht ärgerlich, soll extra aufpassen, verhindert aber genau die Exception nicht

schau dir doch den Ablauf einer solchen Schleife an, wann wird getestet, wann der Index erhöht, wann mit diesem Index auf das Array zugegriffen,
versuche das ein wenig umzustellen
 
B

Behnke

Mitglied
Hups ja die Stelle hätte ich noch angeben können :oops:

Der Code ist nun:
Java: 
public static void Rekursiv(int[] A, int links, int rechts){

        if(links<=rechts){
            if(links==rechts) System.out.println(A[links]);
            int knoten = links;

            while(links<A.length && A[links]<=A[knoten]){
                links++;
            }

            Rekursiv(A, knoten+1, links-1);
            Rekursiv(A, links, rechts);
            if(knoten+1!=links) System.out.println(A[knoten]);
        }
    }

Ausgabe
Code: 
0
2
5
3
1
8
10
9
15
12

Es läuft, es fehlen aber noch 2 Zahlen und meine 7 als Wurzel muss ich noch dranfügen.
Der Fehler dürfte denk ich bei der
7, 1, 0, 3, 2, 5, 12, 9, 8, 10, 13, 15
stattfinden.

Werd ich mir nach der Arbeit noch zur gemüte führen. Danke übrigens SlaterB für deine Mühen :toll:
Falls du natürlich ein Tipp hast immer her damit.

Gruß
 

Aktuelle Jobs

Neue Themen


Oben