[Aufgabe] Huffman Bäume

[Liquid]

Hi!

Bin ein Java Anfänger und hab hier einige Aufgaben zu lösen, so auch eine Huffman-Aufgabe.

Erstmal die Aufgabe:

Gegeben sei das folgende Interface BinaryNode:


interface BinaryNode

Object getValue();
// Liefert den dem Knoten zugeordneten Wert.

void setValue(Object);
// Setzt den dem Knoten zugeordneten Wert.

BinaryNode getLeftChild();
// Liefert das linke Kind des Knotens oder null, falls es nicht existiert.

void setLeftChild(BinaryNode);
// Setzt das linke Kind des Knotens auf den gegebenen Knoten (Teilbaum). Falls bereits ein linkes Kind eingetragen war, so wird dieses überschrieben. Der Wert „null“ als Parameter entfernt das linke Kind.

BinaryNode getRightChild();
// Liefert das rechte Kind des Knotens oder null, falls es nicht existiert.

void setRightChild(BinaryNode);
// Setzt das rechte Kind des Knotens auf den gegebenen Knoten (Teilbaum). Falls bereits ein rechtes Kind eingetragen war, so wird dieses überschrieben. Der Wert „null“ als Parameter entfernt das rechte Kind.

boolean isLeaf();
// Liefert true, falls der Knoten keine Nachfolger hat, false sonst.



Erstellen Sie eine Klasse BinaryNodeImpl, die die Methoden des Interfaces BinaryNode für Binärbäume implementiert. Die Klasse soll gleichermaßen als innerer Knoten wie als Blatt verwendet werden können und einen Standardkonstruktor besitzen.

Tja, und jetzt sitz ich hier und hab keine Ahnung, wie ich da anfangen muss und wie/wo ich das oben genannte Interpace implementieren muss.

Hoffe, es kann mir jemdand paar Tips/Ansätze für die Aufgabe geben.

 

[Beni]

Eine Klasse die Variablen für "value", "rightChild" und "leftChild" hat.

public class Node implements BinaryNode{
  private Object value;
  private BinaryNode leftChild, rightChild;

   ... // was halt noch so dazu gehört
}

Oder missverstehe ich dich?

 

[ugh_bough]

das "was sonst noch kommt" ist die implementierung jeder der oben geforderten methoden.
alle diese methoden arbeiten dann mit den drei instanzwariablen, die oben stehen

 

[Beni]

ja

Zum Beispiel das setValue:

public void setValue( Object newValue ){
  value = newValue;
}

Ganz einfach 8)

 

[ugh_bough]

kann nicht schlafen :cry:

datei BinaryNode.java

public interface BinaryNode {
    // Liefert den dem Knoten zugeordneten Wert. 
    Object getValue(); 
    
    // Setzt den dem Knoten zugeordneten Wert. 
    void setValue(Object value); 
    
    // Liefert das linke Kind des Knotens oder null, falls es nicht existiert. 
    BinaryNode getLeftChild(); 
    
    /** Setzt das linke Kind des Knotens auf den gegebenen Knoten (Teilbaum).
     * Falls bereits ein linkes Kind eingetragen war, so wird dieses überschrieben.
     * Der Wert „null“ als Parameter entfernt das linke Kind. 
     */
    void setLeftChild(BinaryNode binNode); 
    
    // Liefert das rechte Kind des Knotens oder null, falls es nicht existiert. 
    BinaryNode getRightChild(); 
    
    /** Setzt das rechte Kind des Knotens auf den gegebenen Knoten (Teilbaum).
     * Falls bereits ein rechtes Kind eingetragen war, so wird dieses überschrieben.
     * Der Wert „null“ als Parameter entfernt das rechte Kind. 
     */
    void setRightChild(BinaryNode binNode); 
    
    // Liefert true, falls der Knoten keine Nachfolger hat, false sonst. 
    boolean isLeaf(); 
}

datei Node.java

public class Node implements BinaryNode{ 

    private Object value; 
    private BinaryNode leftChild, rightChild; 
    
    // Konstruktor erstellt ein Blatt ohne Wert
    public Node() {
        this.value      = null;
        this.leftChild  = null;
        this.rightChild = null;
    }
    
    public Object getValue() {
        return this.value;
    }
    
    public void setValue(Object value) {
        this.value = value;
    }    

    public BinaryNode getLeftChild() {
        return this.leftChild;
    }  
    
    public void setLeftChild(BinaryNode binNode) {
        this.leftChild = binNode;
    }    

    public BinaryNode getRightChild() {
        return this.rightChild;
    }

    public void setRightChild(BinaryNode binNode) {
        this.rightChild = binNode;
    }

    public boolean isLeaf() {
        if (this.leftChild == null && this.rightChild == null) return true;
        return false;
    }
}

gruß

 

[bygones]

public interface BinaryNode {
[.....]
    public boolean isLeaf() {
        if (this.leftChild == null && this.rightChild == null) return true;
        return false;
    }
}

oder gleich

public boolean isLeaf() {
         return (this.leftChild == null && this.rightChild == null);
    }

 

[ugh_bough]

stimmt. aber ich behaupte, dass meins für einen anfänger leichter verständlich ist

 

[Liquid]

Hi!

Erstmal Danke für eure ganzen Tips!

@ugh_bough: ist das schon die ganze aufgabe, oder nur ein Ansatz zum vollenden? :?:

 

[ugh_bough]

wenn dein zitat oben die ganze aufgabenstellung war, dann ist das die ganze aufgabe

 

[Liquid]

ne, war nur der erste Teil der Aufgabe, der 2te Teil lautet wie folgt:

Erstellen Sie weiterhin eine Klasse BinaryTree, die folgende Baumalgorithmen auf einem auf BinaryNode aufbauenden Baum ausführt. Sie können dabei davon ausgehen, dass jeder innere Knoten im Baum zwei Nachfolger hat.

class BinaryTree

Implementiert mit Hilfe von BinaryNode einen Binärbaum.

BinaryTree(BinaryNode);
//Erzeugt einen BinaryTree für den durch BinaryNode gegebenen Baum.

BinaryNode getRoot();
//Liefert die Wurzel des Baumes.

int height();
//Bestimmt die Höhe des Baumes.
Die Höhe eines Blattes ist 0. Die Höhe eines Knotens ist das Maximum der Höhe der Teilbäume + 1.
Beispiel: Die Höhe des Baumes aus Abbildung 1 beträgt 2. Betrachtet man den Teilbaum, der „B“ als Wurzel hat, so ist dessen Höhe 1.

void visitPreOrder(Visitor);
//Durchläuft den Baum in pre-order Reihenfolge, d.h. es wird zunächst die Wurzel des aktuellen (Teil-)Baumes besucht, anschließend der linke und rechte Nachfolger. Dabei werden die Methoden arrive(), visit() und leave() wie unten beschrieben aufgerufen.

void visitInOrder(Visitor);
//Durchläuft den Baum in in-order Reihenfolge, d.h. es wird zunächst der linke Nachfolger, dann die Wurzel des aktuellen (Teil-)Baumes und zuletzt der rechte Nachfolger besucht..Dabei werden die Methoden arrive(), visit() und leave() wie unten beschrieben aufgerufen.

void visitPostOrder(Visitor);
//Durchläuft den Baum in post-order Reihenfolge, d.h. es werden zunächst der linke und rechte Nachfolger, und dann die Wurzel des aktuellen (Teil-)Baumes besucht. Dabei werden die Methoden arrive(), visit() und leave() wie unten beschrieben aufgerufen.

String toString();
//Liefert eine String-Repräsentation des Baumes. Der Baum soll so dargestellt werden, dass ein Knoten immer in ein Klammerpaar „()“ gefasst wird. Dieses enthält zunächst die String-Repräsentation des Knoten-Werts (value), gefolgt von eventuellen Nachfolgern, die ebenso repräsentiert werden (Dies entspricht dem Durchlauf mit dem PrintVisitor in pre-order Reihenfolge). Zu beachten ist, dass in den String-Repräsentationen der Werte evtl. auftretende Klammern durch die Zeichenfolge „\(„ bzw. „\)“ ersetzt werden müssen. Ebenso für das Zeichen „\“, das durch „\\“ ersetzt wird. Verwenden Sie keine Formatierungszeichen, wie Leerzeichen oder Zeilenumbrüche (es sei denn diese sind in den Knotenwerten enthalten)!

void setFromString(String);
//Setzt den Baum entsprechend der Definition im angegebenen String. Der String muss der Darstellung wie in toString() angegeben folgen. Falls nicht soll eine IllegalArgumentException geworfen werden. Für die Werte der Knoten sollen String-Objekte verwendet werden.

Hinweis: Verwenden Sie zur Implementierung einen temporären StringBuffer, aus dem sie die bereits verarbeiteten Zeichen (nach der Verarbeitung) entfernen.

 

[bygones]

*unbeliebtmach*

Dieses Forum ist da, um bei Problemen zu helfen (ABER man soll sich selbst Gedanken machen !!), NICHT Aufgaben zu lösen !!!
Ich schließe das Thema !!