Class CharacterSearchTree
- java.lang.Object
-
- CharacterSearchTree
-
public class CharacterSearchTree extends java.lang.Object
Autor
Dokumentiert von: Mert Can Özdemir
Modul: DAP1Dokumentation 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 voidadd(char t)void add( char t )java.lang.StringgetCode(char t)String getCode( char t )HuffmanTriplegetContent()HuffmanTriple getContent()booleanisEmpty()boolean isEmpty()booleanisLeaf()boolean isLeaf()voiditerativeAdd(char t)void iterativeAdd( char t )voidshow()void show()intsize()int size()HuffmanTriple[]toArray()HuffmanTriple[] toArray()
-
-
-
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.
-
-