# Java Baumstruktur



## MaXP90 (16. Nov 2016)

Hey, also ich hab ein mega Problem bei einem Praktikum mit Java und zwar hab ich absolut keinen Dunst, wie ich das ganze Problem überhaupt angehen soll bzw was von mir hier überhaupt verlangt wird...ich hoffe, es gibt hier paar schlaue Menschen, die da besser durchsehen als ich  deshalb habe ich mal die Aufgabenstellung drunter gepostet

1 Grundlegende Aufgabenstellung
Im Praktikum wird eine Baumstruktur implementiert, mit deren Hilfe eine eziente
Umsetzung eines Wörterbuches möglich wird. Beginnend mit dem Wurzelknoten des
Baumes kann jeder Knoten eine Zeichenkette als Information enthalten. Die Kanten
des Baumes sind mit Buchstaben beschriftet, die entlang des Pfades zu einem Knoten
gelesen das Schlüsselwort ergeben, unter welchem die Information gespeichert wur-
de. Im Bereich der Zeichenkettenverarbeitung wird eine Baumstruktur dann Tree
genannt, wenn eine Kante unterschiedlich viele Buchstaben als Beschriftung tragen
kann. Die einfachere Form mit nur einem Buchstaben pro Kante wird gemeinhin als
Trie bezeichnet. Betrachten Sie den abgebildeten Baum, welcher aus den Schlüssel-
worten wer, wert, wen, wem, wind, winde, dill und dir erzeugt wurde. Die dunkel
markierten Knoten tragen jeweils eine Information. Die Pfade von der Wurzel des
Baumes zu den jeweiligen dunklen Knoten ergeben die Schlüsselworte: siehe Bild.
2 Knoten des Baumes
Die Speicherung und praktische Logik der Datenstruktur werden auf zwei Klassen
verteilt werden. Beginnen Sie mit der Modellierung der Knoten dieses Baumes. Im-
plementieren Sie dazu die Klasse Node basierend auf den Vorgaben des Interfaces
GeneralNode aus dem Paket vorgaben.praktikum4. Ein Knoten enthält sowohl
eine Information in Form einer Zeichenkette sowie die Verknüpfungen zu den Folge-
knoten. Dabei soll für jeden Buchstaben mit einer Nummer kleiner als 127 (Verein-
fachung) genau ein Folgeknoten möglich sein. Ein leerer Knoten enthält weder eine
Information noch Verknüpfungen. Nutzen Sie die folgende Denition der Informati-
on als String und der Verknüpfungen als Array von GeneralNodes als Hilfestellung
und programmieren Sie die fehlenden Methoden aus:
private String info;
private final GeneralNode[] map = new Node[127];

Neben eigenen Versuchen zur Funktionsfähigkeit Ihrer Implementierung nutzen
Sie bitte den vorbereiteten Test mit den folgenden Anweisungen in der
main-Methode Ihres Projekts:
Testat t = new Testat(Praktika.Praktikum4);
t.addClass(Node::new);
t.check();

3 Baumlogik
Die notwendige Logik zum Einfügen, Löschen und Abfragen von Einträgen in einem
solchen Baum werden über eine weitere Klasse realisiert. Implementieren Sie dazu
die Klasse Trie auf Basis der Vorgaben des Interfaces GeneralTree aus dem Paket
vorgaben.praktikum4. Die Klasse Trie speichert den Wurzelknoten des Baumes
in einem privaten Feld. Zum Suchen und gegebenenfalls auch zum Erzeugen von Knoten wird die Methode getNode verwendet. Sie durchschreitet die Knoten der Baumstruktur entsprechend eines Schlüsselwortes. Wird ein Knoten dieser Reihe nicht gefunden, so wird er nur dann erzeugt, wenn der entsprechende Parameter der Methode gesetzt ist. Ist dies
nicht der Fall, so liefert die Methode eine RuntimeException mit einer entsprechenden Meldung. Wurde keine Fehlermeldung erzeugt, so liefert die Methode den Knoten zurück, der zum eingegebenen Schlüsselwort gehört. Haben Sie diese wichtige Methode implementiert, so ist der Großteil der Arbeit bereits geschafft. Sowohl beim Einfügen, Löschen, Suchen und Prüfen von Schlüsselworten kann die Methode verwendet werden. Unter all diesen Aktionen unterscheidet sich nur die Parametrisierung von getNode und der Umgang mit seinem Ergebnis
beziehungsweise der Fehlermeldung. Die vier Methoden sollen keine Fehlermeldung
weiterreichen! Wenn ein Knoten nicht gefunden wird oder seine Information
null ist, so gilt er als nicht im Baum vorhanden. Entsprechend soll die Methode read ebenfalls einen null-Wert zurückgeben, wenn das Schlüsselwort nicht gefunden wurde. Ist ein Schlüsselwort beim Einfügen bereits vorhanden, so wird die Information überschrieben. Das Löschen gestaltet sich sehr einfach. Auch für diese Klasse gibt es einen vorbereiteten Test, den Sie nutzen können, um schnell herauszunden, ob Ihre Implementierung korrekt arbeitet. Fügen Sie diesen Abschnitt in ihre main-Methode ein:
Testat t = new Testat(Praktika.Praktikum4);
t.addClass(Node::new);
t.addClass(Trie::new);
t.check();

Das hier ist dann übrigens die (noch leere) Klasse:
public class Node implements GeneralNode {

  @Override
  public boolean hasNextNode(char c) {

  }

  @Override
  public GeneralNode getNextNode(char c) {

  }

  @Override
  public void setNextNode(char c, GeneralNode gn) {

  }

  @Override
  public String getInfo() {

  }

  @Override
  public void setInfo(String string) {

  }

} 

bzw das wäre die andere:

public class Trie implements GeneralTree{

  @Override
  public GeneralNode getNode(String string, boolean bln) {

  }

  @Override
  public void insert(String string, String string1) {

  }

  @Override
  public boolean exists(String string) {

  }

  @Override
  public String read(String string) {

  }

  @Override
  public boolean delete(String string) {

  }

}


----------

