Class CharacterSearchTree


  • public class CharacterSearchTree
    extends java.lang.Object

    Autor

    Dokumentiert von: Mert Can Özdemir
    Modul: DAP1

    Dokumentation der Klasse CharacterSearchTree

    - Die Klasse 'CharacterSearchTree hat viele Gemeinsamkeiten mit der Klasse 'HuffmanTree': Beide Klassen dienen dem Aufbau binärer Bäume
    - Die Klassen enthalten Attribute für die gleichen Aufgaben: 'leftChild' und 'rightChild' für die Konstruktion des Baums, 'content' für den Inhalt eines Knotens
    - Die Konstruktionsregeln des binären Suchbaums drücken sich nicht in seinen Atrributen aus. Die Konstruktionsregeln werden von Methoden sichergestellt, die einen Baum erzeugen und diesen verwalten.
    -> Der 'CharacterSearchTree' wird ganz anders aufgebaut als der 'HuffmanTree'
    => Der 'CharacterSearchTree' wird über Methoden aufgebaut, während der 'HuffmanTree' über seine Konstruktoren aufgebaut wird.

    • Constructor Summary

      Constructors 
      Constructor Description
      CharacterSearchTree()
      Konstruktor - CharacterSearchTree()
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(char t)
      void add( char t )
      java.lang.String getCode​(char t)
      String getCode( char t )
      HuffmanTriple getContent()
      HuffmanTriple getContent()
      boolean isEmpty()
      boolean isEmpty()
      boolean isLeaf()
      boolean isLeaf()
      void iterativeAdd​(char t)
      void iterativeAdd( char t )
      void show()
      void show()
      int size()
      int size()
      HuffmanTriple[] toArray()
      HuffmanTriple[] toArray()
      • Methods inherited from class java.lang.Object

        clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • CharacterSearchTree

        public CharacterSearchTree()

        Konstruktor - CharacterSearchTree()

        Der Konstruktor ohne Parameter, legt einen leeren Baum an

    • Method Detail

      • getContent

        public HuffmanTriple getContent()

        HuffmanTriple getContent()

        getContent liefert den Inhalt des aktuellen Knotens, wenn dieser nicht leer ist.
        Wird versucht auf einen leeren Knoten zuzugreifen, dann wird eine Ausnahme geworfen.

      • isEmpty

        public boolean isEmpty()

        boolean isEmpty()

        isEmpty() gibt true zurück, wenn der aktuelle Knoten leer ist.
        ist er nicht leer, wird false zurück gegeben.

      • isLeaf

        public boolean isLeaf()

        boolean isLeaf()

        Wenn der aktuelle Knoten ein Blatt ist, also nicht leer ist und sein linker & rechter Teilbaum leer sind,
        wird true zurückgegeben.
        Sonst wird false zurückgegeben.

      • add

        public void add​(char t)

        void add( char t )

        Das Einfügen eines Zeichens in den Baum erfordert

        - entweder das Anlegen eines neuen Knotens für dieses Zeichen
        - oder das Erhöhen der Häufigkeit für das schon vorhandene Zeichen:

      • iterativeAdd

        public void iterativeAdd​(char t)

        void iterativeAdd( char t )

        Da die Methode 'add()' immer einem bestimmten, durch die Ergebnisse der Vergleiche vorgegebenen Pfad von Knoten durch einen Teilbaum folgt, kann sie auch iterativ, also durch die Nutzung einer Schleife formuliert werden.

      • getCode

        public java.lang.String getCode​(char t)

        String getCode( char t )

        Sucht nach dem Zeichen im

      • size

        public int size()

        int size()

        Zählt die Anzahl der unterschiedlichen Zeichen ('token's), der 'HuffmanTripple'-Objekte, die sich als 'content' in unserem Baum befinden
        -> Das Feststellen der Anzahl der abgelegten, unterschiedlichen Zeichen lässt sich ebenfalls an die nachfolgenden Teilbäume übertragen und daher rekursiv formulieren:
        => Jeder nicht-leere Teilbaum besteht aus der Anzahl der Zeichen, die in den Teilbäumen Abgelegt sind (leftChild.size() + rightChild.size())
        => und aus dem einen Zeichen in seiner Wurzel (+1)

      • show

        public void show()

        void show()

        Die Ausfgabe der abgelegten, unterschiedlichen Zeicheen und ihrer Häufigkeiten lässt sich ebenfalls an die nachfolgenden Teilbäume übertragen und daher rekursiv formulieren

        Gibt den Baum in einem in-order Tiefendurchlauf aus. (-> InOrder-Durchlauf: Die Wurzel wird zwischen (, also in) den beiden Teilbäumen bearbeitet)
        Da der Tiefendurchlauf in-Order statfindet, ist die Liste anschließend aufsteigend sortiert.

      • toArray

        public HuffmanTriple[] toArray()

        HuffmanTriple[] toArray()

        - Die Übergabe der abgelegten, unterschiedlichen Zeichen und ihrer Häufigkeiten an ein Feld wird als Eingabe für Klasse 'HuffmanCoding' benötigt.
        - Das Erzeugen eines solchen Feldes lässt sich ebenfalls über einen InOrder-Durchlauf rekursiv formulieren.
        - Die Methode 'toArray()' bereitet den InOrder-Durchlauf vor, indem ein passendes Feld für 'HuffmanTriple'-Objekte bereitgestellt wird.
        - Die Anzahl der benötigten Elemente wird durch den Aufruf der Methode 'size()' ermittelt.

        Wie können wir den CharacterSearchTree benutzen, um die Eingaben für unseren Huffman Algorithmus zu schaffen?

        -> Wir möchten ein Feld von 'HuffmanTriple'-Objekten haben
        -> Der Inhalt unserer Knoten sind 'HuffmanTriple'-Objekte
        => Wir müssen unsere Knoten in ein Feld ablegen.