Klasse Baum

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

  • Klasse Baum

    Ich hab hier mal wieder eine ganz interessante Aufgabe. WÄr ganz nett wenn wir hier ein paar Ideen zusammenbekommen könnten. Weil so ganz alleine krieg ich das wohl nicht hin...Danke schonmal für die Tipps.

    Implementieren Sie eine Klasse BinaerBaum. In den Knoten sollen Zeichenketten verwaltet
    werden können. Folgende Methoden sollen enthalten sein:
    void fuegeEinSortiert(String neu):
    Einfügen einer neuen Zeichenkette in den Baum nach dem Prinzip:
    Falls Neu < Inhalt des Knotens dann in den linken Unterbaum, sonst in den
    rechten Unterbaum.
    void ausgabeLWR(): Ausgabe des Baumes in der Reihenfolge Links-Wurzel-Rechts:
    das führt zu einer aufsteigend sortierten Folge
    void ausgabeRWL(): Ausgabe des Baumes in der Reihenfolge Rechts-Wurzel-Links:
    das führt zu einer absteigend sortierten Folge
    int anzahl(): Ermittelt die Anzahl der Knoten im Baum (rekursiv)
    Nutzen Sie für die Darstellung eines Baumes die Methode ausgabe() (siehe Datei
    baumausgabe.txt) Wie sind die Methoden ausgabeLWR() bzw. ausgabeRWL() zu ändern,
    damit im Ergebnis eine Folge sortierter Zeichenketten entsteht, die auch weiter verarbeitet
    werden kann? (Hinweis: String-Array oder ArrayList)

    a) Entwickeln Sie für die Klasse BinaerBaum eine Methode, die für den Baum die Tiefe
    bestimmt.
    b) Wenn Bäume sehr ungleich sind, versucht man diese mittels Rotationen auszugleichen.
    Machen Sie sich mit den Rotationsoperationen auf Bäumen vertraut und implementieren Sie
    die Methoden rotiereLinks() sowie rotiereRechts():

  • Ich schließe mich mal der Frage bzw. Aufgabe an....

    Würde persönlich erstmal so anfangen.

    Quellcode

    1. class BinBaum // ------------------------------------------------
    2. { BinBaum links; // linker Teilbaum
    3. BinBaum rechts; // rechter Teilbaum
    4. String inhalt; // Inhalt soll String sein.
    6. // Konstruktor
    7. BinBaum (String neu)
    8. { this.links = null;
    9. this.rechts = null;
    10. this.inhalt = neu;
    11. }
    13. void fuegeEinSortiert (String neu)
    14. { if (inhalt == neu)
    15. { // in linken Teilbaum einfuegen
    16. if (links == null)
    17. links = new BinBaum(inhalt);
    18. else links.fuegeEinSortiert(inhalt);
    19. }
    20. else { // in rechten Teilbaum einfuegen
    21. if (rechts == null)
    22. rechts = new BinBaum(inhalt);
    23. else rechts.fuegeEinSortiert(inhalt);
    24. }
    25. } // fuegeEinSortiert
    27. void ausgabeLWR()
    28. {};
    29. void ausgabeRWL()
    30. {};
    31. int anzahl()
    32. {return 6;}
    34. void ausgabe ()
    35. { if (links != null) links.ausgabe();
    36. System.out.print(inhalt); System.out.println();
    37. if (rechts != null) rechts.ausgabe();
    38. } // laufeDurch
    39. } // class BinBaum
    Alles anzeigen


    Wobei das erstmal das Gerüst wäre... Die Methode fuegeEinSortiert ist aber auch noch nicht richtig... Wäre nun auch für weitere Hilfe dankbar.

  • Ich schließe mich mal der Frage bzw. Aufgabe an....

    Würde persönlich erstmal so anfangen.

    Quellcode

    1. class BinBaum // ------------------------------------------------ { BinBaum links; // linker Teilbaum BinBaum rechts; // rechter Teilbaum String inhalt; // Inhalt soll String sein. // Konstruktor BinBaum (String neu) { this.links = null; this.rechts = null; this.inhalt = neu; } void fuegeEinSortiert (String neu) { if (inhalt == neu) { // in linken Teilbaum einfuegen if (links == null) links = new BinBaum(inhalt); else links.fuegeEinSortiert(inhalt); } else { // in rechten Teilbaum einfuegen if (rechts == null) rechts = new BinBaum(inhalt); else rechts.fuegeEinSortiert(inhalt); } } // fuegeEinSortiert void ausgabeLWR() {}; void ausgabeRWL() {}; int anzahl() {return 6;} void ausgabe () { if (links != null) links.ausgabe(); System.out.print(inhalt); System.out.println(); if (rechts != null) rechts.ausgabe(); } // laufeDurch } // class BinBaum



    Wobei das erstmal das Gerüst wäre... Die Methode fuegeEinSortiert ist aber auch noch nicht richtig... Wäre nun auch für weitere Hilfe dankbar.

  • Hey Blane, ich hab grade folgendes gefunden zu der Aufgabe...
    Schauen Sie doch einmal unter Wikipedia und binärem Suchbaum:
    <img src="https://studip.hs-wismar.de/assets/images/link_extern.gif" border="0" />[url]http://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum[/url]
    Dort wird die Rotation erklärt.
    Bei einer Rotation nach rechts passiert folgendes:
    <code>


    A B

    +---+---+ Rotation rechts: +---+---+

    B baum3 ==================> baum1 A

    +---+---+ +---+---+

    baum1 baum2 baum2 baum3


    </code>
    • Der linke Nachfolger der Wurzel wird zum neuen Wurzelknoten
    • Die alte Wurzel(A) wird zum rechten Nachfolger der neuen Wurzel(B)
    • Der alte rechte Unterbaum (b3) der Wurzel(A) bleibt rechter Unterbaum von A
    • Der alte linke Unterbaum (b1) von B bleibt linker Unterbaum von B
    • Der alte rechte Unterbaum(b2) von B wird linker Unterbaum von A
    Kann uns da mal jemand bitte weiterhelfen?

  • Achja und Hier ist der Bauplan der Klasse StringTree zu sehen, der neben den
    Zugriffsmethoden, die Methoden zum Einfügen und zum Ausgeben enthält.
    Die Anwendung dieser Klasse ist der Klasse TestTree zu entnehmen.

    Quellcode

    1. /**
    2. * Ein binärer Suchbaum für Zeichenketten.
    3. *
    4. * Generell können beliebige Objekte in einem Baum verwaltet werden.
    5. * Ein binärer Suchbaum kann nur Objekte verwalten, die vergleichbar
    6. * sind, d.h. auf denen eine Ordnung existiert.
    7. * Programmtechnisch müssen diese Objekte das Interface Comparable
    8. * implementieren.
    9. *
    10. * @author Uwe Lämmel
    11. * @version 04.12.2007
    12. */
    13. public class StringTree {
    15. //-- Bauplan ----------------------------------------------------
    16. String obj; // Inhalt des Knoten
    17. StringTree left; // linker Teilbaum
    18. StringTree right; // rechter Teilbaum
    20. //-- Konstruktor new --------------------------------------------
    21. public StringTree(String x,StringTree l,StringTree r)
    22. { obj=x; left=l; right=r; }
    23. public StringTree(String x) { obj=x; left= right=null;}
    24. public StringTree() { obj=null; left= right=null;}
    26. //-- getLeft,getRight, getRoot ----------------------------------
    27. public StringTree getLeft () { return left; }
    28. public StringTree getRight () { return right; }
    29. public String getObject () { return obj; }
    31. //-- setLeft, setRight, setRoot ---------------------------------
    32. public void setLeft (StringTree l) { left =l; }
    33. public void setRight (StringTree r) { right=r; }
    34. public void setObject(String x) { obj =x; }
    37. //-- Einfügen eines neuen Elementes
    38. public void insert(String x){
    39. // Vergleich ob in den linken oder rechten Unterbaum
    40. if(getObject().compareTo(x)>0){
    41. // Wenn Unterbaum leer, dann neues Element einfügen
    42. if(getLeft()==null) {
    43. // Erzeugen eines neuen Knotens mit x als Inhalt
    44. StringTree st = new StringTree(x);
    45. setLeft(st);
    46. }/if
    47. // Sonst rekursives Einfügen im Unterbaum:
    48. else getLeft().insert(x);
    49. }
    50. else{ // wie links, siehe oben
    51. if(getRight()==null){
    52. // Erzeugen eines neuen Knotens mit x als Inhalt
    53. StringTree st = new StringTree(x);
    54. setRight(st);
    55. }//if
    56. else getRight().insert(x);
    57. }
    58. }//insert
    60. //-- Ausgabe des Baumes in sortierter Reihenfolge
    61. //-- aufsteigend: Links-Wurzel-Rechts
    62. public String ausgabeLWR(){
    63. String s="";
    64. if(getLeft()!=null) s += getLeft().ausgabeLWR();
    65. s += " "+getObject();
    66. if(getRight()!=null) s += getRight().ausgabeLWR();
    67. return s;
    68. }//LWR
    72. //-- ShowBranches -----------------------------------------------
    73. //-- Hilfsmethode zur formatierten Ausgabe auf der Konsole
    74. private void showBranches(int level) {
    75. IntIO io = new IntIO();
    76. if (getRight()!=null) getRight().showBranches(level+1);
    77. for(int i=0; i<level;i++) io.write(" "); io.writeln("+-> "+getObject());
    78. if (getLeft()!=null) getLeft().showBranches(level+1);
    79. }//showBranches
    81. //-- ausgabe ----------------------------------------------------
    82. public void ausgabe() { this.showBranches(0); }
    84. }//StringTree
    Alles anzeigen

    • Man merke sich die Unterbäume von B (BR,BL) sowie den rechten von A (AR).
    • Setzen Sie einen neuen rechten Unterbaum zur Wurzel A: temp
    • Der Knoten temp erhält den Inhalt von A und als rechten Unterbaum AR.
    • Der linke Unterbaum des Knoten temp wird mit BR belegt.
    • Die Wurzel erhält als Inhalt den Inhalt von B, sowie den linken Unterbaum BL.

    Damit ist eine Methode: public void rotateRight(){...} möglich.

    Wir
    rotieren somit nicht den Wurzelknoten selbst sondern verändern seinen
    Inhalt. Im Ergebnis entsteht dann ein Baum, der dem unten stehenden
    Ergebnis entspricht.