Hoffe jemand kann mir ein paar Tips geben:binärer Suchbaum

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Hoffe jemand kann mir ein paar Tips geben:binärer Suchbaum

    Hallo,
    ich habe dieses Semester mein Studium begonnen, aber bin in Java noch nicht so fit und habe jetzt ne super schwere Hausaufgabe bekommen bei der ich nicht so recht weiter komme.

    Es soll in Java ein Binärer Suchbaum von über die Tastatur eingegebenen integer-keys angelegt werden, der in der Reihenfolge der Eingaben aufgebaut wird. An diesem Baum soll die Suche nach beliebigen integer-Keys möglich sein, indem über die Tastatur ein solcher key eingegeben wird und der gefunde Wert auf dem Bildschirm ausgegeben wird bzw. die Mitteilung erfolgt, das kein solcher Wert gefunden wurde. Weiterhin soll es möglich sein, jederzeit neue Elemente hinzuzufügen oder zu entfernen.

    Wäre lieb wenn Ihr mir helfen könntet, weil ich im Moment noch nicht so recht weiß wie ich das ganze programmieren soll. Liebe Grüsse, Susanne.

  • Hi,

    bitte konkretisiert die Frage doch etwas.
    Beim Binären Suchbaum brauchst du eine Knoten Klasse mit 2 Zeigern (link/rechts bzw. größer/klekner) und einem Inhalt.

    Zahl1 wird die Wurzel
    Beim Einfügen von Zahl2 wird überprüft ob sie größer oder kleiner Zahl1 ist.
    Je nachdem wird als nächstes die linke oder rechte Seite gegangen.
    Sagen wir mal sie ist kleiner. Also wird ein neuer Knoten erstellt und Zahl1.left wird auf Zahl2 verwiesen.

    Zahl3 wird eingefügt - sagen wir mal es ist die kleinste Zahl.
    Zahl1 wird vergleichen, Zahl3 ist kleiner -> gehe links
    Zahl2 wird vergleichen, Zahl3 ist kleiner -> gehe links
    keine Folgeknoten mehr - erstelle Zahl3 und verlinke

    Das ist natürlich nur der simple Suchbaum, der ziemlich entarten kann. Rot-Schwarz-Bäume, AVL Bäume, ... machen dann sicherlich mehr Spaß.

  • Naja, dein Knoten sieht in etwa so aus

    Quellcode

    1. class Node {
    2. Node left=null, right=null;
    3. int wert;
    5. Node(int wert) {
    6. this.wert = wert;
    8. }
    9. }


    Und Einfügen tust du in etwa so:

    Quellcode

    1. EinfuegenInSuchbaum(Node root, int wert) {
    2. if (root == null)
    3. return new Node(newVal);
    4. else {
    5. if (newVal < root.val)
    6. root.left = insert(root.left, wert);
    7. else if (newVal > root.val)
    8. root.right = insert(root.right, wert);
    9. else //keine doppelten Eintraege
    10. return root;
    11. }
    12. }
    Alles anzeigen