Binärbaum aus LWR und WLR Ordnung rekonstruieren

[Luki1512]

Hallo Leute.
Ich studiere angewandte Informatik im zweiten Semester und hatte davor noch nichts damit am Hut, deshalb bitte die Antworten lieber etwas zu einfach formulieren.
Wie schon gesagt muss ich ein Programm schreiben um einen Binärbaum zu rekonstruieren. Mein Hauptproblem ist hierbei eine ArrayIndexOutOfBoundsexception weil anscheinend meine statische Variable index zu stark anwächst. Ich weiß klingt viel zu banal um eine Frage zu posten aber ich finde den Fehler leider nicht mehr alleine. Würde mich sowohl über einen kleinen Schubs in die richtige Richtung als auch über den Tipp komplett neu anzufangen freuen. Bei letzterem bitte aber auch noch anmerken auf was ich dann achten soll.

Hier ist mein Code:

public static int index=0;

public Tree reconstructTree(int[] inorder, int[] preorder) {
   Tree tree=new Tree();
   Node n=new Node();
   n.key=preorder[index];
   tree.size= inorder.length; //initializing Tree, define Root

   int pos=0;
   for(;inorder[pos]==preorder[index];pos++); //position of the Root in the inorder Array

   n.left=reconstruct(inorder,preorder,0,pos);
   n.right=reconstruct(inorder,preorder,pos,inorder.length); //finding the childnodes of Root
   return tree;
}
public Node reconstruct(int[] inorder,int[] preorder,int start,int stop){
   index++;
   if(stop-start==0) return null; //return nothing if there is nothing left in my defined area
   Node n=new Node();
   n.key=preorder[index];
   if(stop-start==1) return n; //return the child node if it is the last in the defined area (leaf)

   int pos=0;
   for(;inorder[pos]==preorder[index];pos++);

   n.left=reconstruct(inorder,preorder,start,pos);
   n.right=reconstruct(inorder,preorder,pos,stop); //find trhe child nodes
   return n;
}

LG, Lukas

 

[mihe7]

Mein Hauptproblem ist hierbei eine ArrayIndexOutOfBoundsexception

Die Exception tritt auf, wenn versucht wurde, auf ein Array außerhalb seiner Grenzen (0 - (Länge-1)) zuzugreifen. Oft findet sich der Fehler in Schleifenzählern. Mit der Exception wird ein Stacktrace ausgegeben, dem man genau die Stelle im Code entnehmen kann, an der der Fehler aufgetreten ist. Schau da mal nach (vermutlich Zeile 10 bzw. 24).

 

[Barista]

Du solltest noch Beispieldaten und die erwarteten Ergebnisse (Testfall) posten.

 

[Luki1512]

Die Exception tritt auf, wenn versucht wurde, auf ein Array außerhalb seiner Grenzen (0 - (Länge-1)) zuzugreifen. Oft findet sich der Fehler in Schleifenzählern. Mit der Exception wird ein Stacktrace ausgegeben, dem man genau die Stelle im Code entnehmen kann, an der der Fehler aufgetreten ist. Schau da mal nach (vermutlich Zeile 10 bzw. 24).

Der Fehler wird in der Zeile 20 ausgegeben. Ich hab mir das Programm jetzt mehrmals nur durchgesehen und auch durchgedacht (bins auch am Papier durchgegangen) aber es ist mir immer noch ein Rätsel wie es über die Grenzen hinausschießen kann.
Das index++ gehört übrigens unter die if Verzweigung und nicht darunter; das hab ich in einem Anfall von Wahnsinn umgeändert.

 

[fhoffmann]

Hier noch eine Vermutung, wie die ursprüngliche Aufgabe lautete:

Gegeben sei ein Baum

 1
 /\
2  3

Ich kann diesen Baum in inorder-Reihenfolge durchgehen, das heißt, ich betrachte zuerst den linken Teilbaum, dann die Wurzel und dann den rechten Teilbaum. Damit gehe ich die Knoten in folgender Reihenfolge durch:
[2, 1, 3]

Ich kann den Baum auch in preorder-Reihenfolge durchgehen, das heißt, ich betrachte zuerst die Wurzel, dann den linken Teilbaum und dann den rechten Teilbaum. Damit gehe ich die Knoten in folgender Reihenfolge durch:
[1, 2, 3]

Nun habe ich die Gestalt des Baumes vergessen, weiß aber noch, dass ich bei inorder [2, 1, 3] und bei preorder [1, 2, 3] erhalten habe.
Kann ich aus diesen Informationen den ursprünglichen Baum rekonstruieren?

Allein aus der inorder-Reihenfolge [2, 1, 3] kann ich den Baum nicht rekonstruieren; es könnte sich auch um folgenden Baum handeln:

    3
   /
  1
 /
2

Allein aus der preorder-Reihenfolge [1, 2, 3] kann ich den Baum nicht rekonstruieren; es könnte sich auch um folgenden Baum handeln:

    1
   /
  2
 /
3

Wenn mir aber beide Reihenfolgen vorliegen, sollte es möglich sein, den Baum zu rekonstruieren:

Die preorder-Reihenfolge sagt mir, dass 1 die Wurzel sein muss;
Alles, was in der inorder-Reihenfolge links von der 1 steht, gehört zum linken Teillbaum,
und was rechts von der 1 steht, gehört zum rechten Teilbaum.

Bei größeren Bäumen wird es dann komplizierter.

 

[fhoffmann]

for(;inorder[pos]==preorder[index];pos++);

Diese for-Schleife ist nicht wirklich sinnvoll!
Sie läuft solange, wie die Beingung wahr ist; wenn also nicht gilt inorder[0]==preorder[0], bricht die Schleife sofort ab!

 

[mihe7]

aber es ist mir immer noch ein Rätsel wie es über die Grenzen hinausschießen kann.

Die Schleifen in den genannten Zeilen vergleichen inorder[pos] mit preorder[index], wobei pos erhöht wird, so lange Gleichheit besteht.

Beispiel: Seien inorder und preorder einelementige Arrays, weiter index und pos jeweils gleich 0. Die Schleifenbedingung wird geprüft, es gelte inorder[pos] == preorder[index]. Dann wird pos um 1 erhöht und die Schleifenbedingung erneut geprüft, womit auf inorder[1] zugegriffen wird. Da inorder aber nur ein Element besitzt, wird eine Ausnahme ausgelöst.

 

[fhoffmann]

Die Schleifen in den genannten Zeilen vergleichen inorder[pos] mit preorder[index], wobei pos erhöht wird, so lange Gleichheit besteht.

Schlimmer ist aber doch, dass die Schleife nicht tut, was sie tun soll.
Es soll die Positin des Wertes in inorder[] gesucht werden, der in preorder[] an der Stelle index steht.