Erste Schritte BinarySearchTree - Wo kommen die Werte her?

[grueneneune]

Hallo zusammen,

ich habe ein paar grundsätzliche Verständnisprobleme zum BinarySearchTree. Die unten angefügten Klassen sind mir dabei vorgegeben. Es geht mir lediglich darum, die gegebenen Methoden isEqual, isLess und isGreater zu überschreiben. Angedacht habe ich eine einfache Unterscheidung zwischen Zahlen, die - sofern sie größer als ihre Wurzel sind - rechts eingeordnet bzw. andernfalls links eingeordnet werden sollen. Dazu sollte eine einfache if-Abfrage reichen, die die Zahlen vergleicht (das Ganze natürlich auch nochmal für isLess und isEqual):

public boolean isGreater (Item pItem) {
     if (zahl1 > zahl2) {
           return true;
     } else {
           return false;
     }
}

Allerdings leuchtet mir nicht ein, wie ich diese Werte überhaupt in den Baum einschleuse und sie dann mit pItem vergleichen kann.

 

[SlaterB]

fürs Einfügen ist BinarySearchTree, insert(Item pItem) zuständig,
da steht doch schon bisschen Code der vergleicht (mit anderen items!) und den Baum entlang wandert,
so in der Art gehts, was ist dazu die Frage?

edit:
ok, im Detail hapert es noch, die Unterscheidung zwischen weiter suchen und tatsächlich einfügen,
das findet man doch allgemein bei derartigen Implementationen im Netz,
oder bevor das jemand hier im Forum fertig codet oder beschreibt, erzähle du doch in Worten,
was da passieren soll, wie du das durch den Code auszudrücken gedenkst,
wie sieht ein Ablauf in einem Beispiel-Baum mit Einfügen von Beispiel-Wert X aus?


-----

bedenklich erscheint mir, dass BinarySearchTree eine Methode getLeftTree() genau wie BinaryTree,
das scheint mir bisschen doppelt gemoppelt, darüber schon nachgedacht und ist das nötig?

vielleicht das nur BinaryTree überlassen, der SearchTree nutzt diesen zum Durchlauf,
kann den BinaryTree zurückgeben, aber tut nicht selber so als hätte er auch Nachfolger

 

[grueneneune]

Was mir einfach nicht einleuchten will, ist die Funktionsweise der abstrakten Klasse Item. Welchen Typ hat ein Objekt dieser Klasse und wie erzeuge ich solch ein Objekt? Wenn ich bspw. eine einfache int-Zahl in einen erstellten Baum einfügen will - geht das problemlos?

Dass die vorgegebenen Klassen verbesserungswürdig sind, ist gut möglich - jedoch soll ich anhand derer arbeiten.

 

[SlaterB]

Item ist abstrakt, quasi ein Interface, es muss erst Klassen geben die das implementieren, wenn dann werden sie es hoffentlich richtig machen, ob Integer, Bananen oder Deutschland-Flaggen, das kann dir komplett egal sein,
erzeugen musst du hier auch nicht, zum Test bietet sich aber natürlich eine Test-Klasse dafür dann,
mit Instanzattribut, z.B. Integer, und passenden Methoden, dann ganz normal Objekte davon erzeugen,


> if (zahl1 > zahl2) {
aus deinem Posting ist natürlich nicht so doll, eher
if (this.wert > pItem.wert) {

--------

für deinen Algorithmus ist das egal,
da musst du dich nur darauf verlassen/ hoffen, dass die Methoden im Fall der Fälle schon korrekt sein werden,
den Rest macht der Tree selber, fertig

 

[grueneneune]

Entschuldigt die lange Abstinenz, mittlerweile habe ich es hinbekommen, dass Werte in den Baum eingefügt werden und mit inorder ausgegeben werden (funktioniert natürlich auch äquivalent mit preorder und postorder). Allerdings sind dabei zwei Teile drin, die ich so eher zusammenkopiert, als wirklich verstanden habe. Einmal Ausdrücke wie diesen hier:

((MeinIntegerItem)t.getItem()).getBetrag()

und generell die Nummer mit dem betrag. Es gibt z.B. eine Methode getBetrag, die nichts anderes macht als den betrag zurückzugeben. Wieso brauche ich dafür eine Methode und kann nicht direkt auf den Betrag zugreifen?

Wie dem aber auch sei, für meine mündliche Abiturprüfung (dafür war der Spaß gut) habe ich gewisse Teile einfach auswendig gelernt. Wollte aber niemand wissen - sind auch ohne Binärbaum 14 Punkte geworden (wenn man so eine Note seit der dritten Klasse nicht mehr gesehen hat, darf man das ruhig mal hinausposaunen!) 🙂

public class Test extends BinarySearchTree {
BinarySearchTree baum;
public Test() {
baum = new BinarySearchTree();
baum.insert(new MeinIntegerItem(5));
inorder(baum);
}

public void inorder(BinarySearchTree t) {
if(!t.isEmpty()) {
inorder(t.getLeftTree());
System.out.print(((MeinIntegerItem)t.getItem()).getBetrag() + " ");
inorder(t.getRightTree());
}
}

public class MeinIntegerItem extends Item {
int betrag;

public MeinIntegerItem(int pBetrag) {
betrag = pBetrag;
}

public boolean isEqual(Item item) {
if(betrag == ((MeinIntegerItem)item).getBetrag()) {
return true; 
} else {
return false;
}
}

public boolean isGreater(Item item) {
if(betrag > ((MeinIntegerItem)item).getBetrag()) {
return true; 
} else {
return false;
}
}

public boolean isLess(Item item) {
if(betrag < ((MeinIntegerItem)item).getBetrag()) {
return true; 
} else {
return false;
}
}

public int getBetrag() {
return betrag;
}
}
}

(Können noch Fehler drin sein, hab's jetzt nicht getestet.)

 

[SlaterB]

Kapslung ist ein riesiges Thema für sich
Datenkapselung (Programmierung) ? Wikipedia

zwei Punkte kurz angesprochen:
- Interface gehen eh nicht mit direkten Zugriff auf Attribute
- Vererbung oder auch nur interne Berechnung/ Umkonfiguration, lazy loading,
ein getter kann statt eines Attributs je nach Zustand auch erst aus der DB laden und noch viel verrückteres,

oft gibt es wirklich nur das Attribut, dann kann man es sich auch vorerst sparen, falls man nicht auf Symmerie achtet