Typische Fehler — was oft schiefgeht

So wird es oft gemacht: l.getItem(l.getLength())

Richtig ist: l.getItem(l.getLength() - 1) — die Zählung beginnt bei 0.

Letzter Index = Länge minus 1.

So wird es oft gemacht: Vorwärts-for mit delete(i) auf [1, 1, 5] ergibt [1, 5].

Richtig ist: Rückwärts laufen: aus [1, 1, 5] wird [5].

Löschen in der Schleife: von hinten nach vorn.

So wird es oft gemacht: Zweimal top() liefert nacheinander die beiden obersten Elemente.

Richtig ist: top() liefert zweimal dasselbe; erst pop() entnimmt.

pop entnimmt, top schaut nur.

So wird es oft gemacht: Für die Warteschlange an der Hotline wird ein Stapel gewählt.

Richtig ist: Wer zuerst anruft, wird zuerst bedient: FIFO, also eine Schlange.

Stapel = neuestes zuerst, Schlange = ältestes zuerst.

So wird es oft gemacht: if (x == b.getItem()) … als erste Zeile einer rekursiven Suche.

Richtig ist: Zuerst if (b.isEmpty()) return false; — erst danach getItem().

Erst isEmpty(), dann getItem().

So wird es oft gemacht: if (b.isLeaf()) return; als einziger Abbruch einer Traversierung.

Richtig ist: Abbruch beim leeren Baum: if (b.isEmpty()) return; — sonst fehlen Blätter oder es entsteht ein Laufzeitfehler bei Knoten mit nur einem Kind.

Rekursion endet am leeren Baum, nicht am Blatt.

So wird es oft gemacht: Ein Baum aus Wurzel und zwei Blättern hat die Höhe 1.

Richtig ist: Hier zählt die Höhe Ebenen: Höhe 2. Die Blätter haben die Tiefe 1.

Höhe = Ebenen, Tiefe = Kanten ab der Wurzel.

So wird es oft gemacht: Für 1(2(4, 5), 3) wird die Preorder 1 2 3 4 5 notiert.

Richtig ist: Nach der Wurzel erst ganz in den linken Teilbaum: 1 2 4 5 3.

Preorder: W, dann der ganze linke Teilbaum.

So wird es oft gemacht: 8(3(1, 9), 12) gilt als Suchbaum, weil 9 > 3 rechts von 3 steht.

Richtig ist: Die 9 liegt im linken Teilbaum von 8 und müsste kleiner als 8 sein — kein Suchbaum.

Die Ordnung gilt für ganze Teilbäume.

So wird es oft gemacht: In 40(20, 60) wird 30 „zwischen 40 und 20“ eingefügt.

Richtig ist: 30 wandert den Suchpfad hinab und wird Blatt: rechtes Kind von 20.

Eingefügt wird immer als Blatt.

So wird es oft gemacht: if (x < b.getItem()) enthaelt(b.getLeft(), x);

Richtig ist: if (x < b.getItem()) return enthaelt(b.getLeft(), x); — sonst geht das Ergebnis verloren.

Rekursiver Aufruf mit return weiterreichen.

So wird es oft gemacht: if (b.isEmpty()) b = new BinTree<Integer>(x);

Richtig ist: b.setItem(x); — die Zuweisung ändert nur die lokale Variable, der leere Teilbaum im Baum bleibt leer.

Leeren Teilbaum mit setItem füllen.