binaerbaum implementieren

[measure]

Hallo zusammen,
ich hoffe ihr könnt mir helfen, denn ich bin langsam am verzweifeln,
bin Mathematikerin mit Nebenfach Informatik, und wir besprechen in den Übungen nie unsere Aufgaben, müssen das Programm als Datei abgeben und können dann nur nachschauen, wie viel Punkte wir insgesamt von wie vielen haben, aber nicht was wir falsch gemacht haben, und deshalb schließen sich die lücken, die sich seit beginn entwickelt haben auch kaum. Ich habe mir schon etliche Bücher ausgeliehen und auch 2 gekauft, die waren zwar fürs grobe ganz gut, aber wenn ich n programm schreiben soll, helfen mir die nicht weiter.

Wir sollen folgendes Interface implementieren, und ich scheiter wie bei den meisten Programmen ganz am Anfang.
Also der erste Konstruktor ist klar, und bis zu "public BinaerbaumInterface<Type> right()" weiß ich einfach nicht weiter.
Mit dem, was danach kommt, kann ich dann schon klar, wenn ich mal die Objekte geschaffen hab, mit denen ich dann was machen muss!
(Bin auch dankbar für jeden Tip, wie ich das lernen kann, was ich am Anfang zu tun hab)

public interface BinaerbaumInterface<Type> {

/**
* Konstruktor, zum Erzeugen eines leeren Binaerbaumes
*/
/*public BinaerbaumInterface();*/

/**
* Konstruktor, zum Erzeugen eines Binaerbaumes
* @param left linker Ast des neuen Baumes
* @param value zugeordneter Wert neuen Knotens
* @param right rechter Ast des neuen Baumes
*/
/*public BinaerbaumInterface(BinaerbaumInterface<Type> left,
* Type value, BinaerbaumInterface<Type> right);*/

/**
* @return den linken Ast des Baumes
*/
public BinaerbaumInterface<Type> left();
/**
* @return den rechten Ast des Baumes
*/
public BinaerbaumInterface<Type> right();
/**
* @return den der Wurzel zugeordneten Wert
*/
public Type value();
/**
* @return <code>true</code>, wenn der Baum leer ist
*/
public boolean empty();

/**
* Diese Methode soll rekursiv jeden Knoten des Binaerbaums besuchen, und dabei
* die Tiefe und das zugeordnete Objekt mittels System.out.println() ausgegeben.
*
* @param tiefe die bisher erreichte Tiefe im Baum. Bei der Wurzel wird dies also
* mit travers(0) aufgerufen
*
*/
public void traverse(int tiefe);

}

 

[burgfried]

könntest du bitte konkrete fragen stellen, damit ich dir besser weiterhelfen kann?

ich weiß ungefähr, was du bei dieser übung machen musst, allerdings weiß ich nicht, wo ich dir jetzt genau weiterhelfen muss.

 

[measure]

wie krieg ich den zweiten konstruktor? also wie erzeuge ich jetzt einen linken bzw.rechten Ast?

 

[MrChance]

linker und/oder rechter "Ast" ist ein Teilbaum - und ein Teilbaum ist auch ein Baum. D.h. es ist der gleiche Konstruktor.

 

[MrChance]

----
...aber soweit ich weiss hat ein Interface gar keinen Konstruktor.

 

[burgfried]

ja du musst halt einmal eine klasse schreiben, die dieses interface implementiert und die beiden konstruktoren realisiert.

zb.

public class BinaryTree<Type> implements BinaerbaumInterface<Type> {

//member variables
BinaryTree<Type> m_pLeft, m_pRight;
Type m_pValue; 

public BinaryTree() {
m_pLeft = null;
m_pRight = null;
m_pValue = null;

} 


public BinaryTree(BinaryTree<Type> left, Type value, BinaryTree<Type> right) {
m_pLeft = left;
m_pRight = right;
m_pValue = value;


}


 public boolean empty() {
  return ((m_pLeft == null) && (m_pRight == null) && (m_pValue == null));
}

...
}

die konstruktoren setzen lediglich die drei member variablen.

die anderen methoden geben zurück, welche settings der binärbaumknoten hat.

ich hab das jetzt nur mal schematisch aufgeschrieben. du musst dich noch mit der generezität spielen, weil das habe ich nicht so intus, wie es da verlangt wird.

 

[measure]

Oh vielen Dank, Burgfried. Du weißt gar nicht wie gut das tut, wenn einem mal jemand weiterhilft.
Denn es ist ja nicht so, dass ich mich nicht damit auseinandersetzen würde, aber ich komme oft nicht alleine weiter.

Also ich habe jetzt folgendes:

import java.io.*;

public class Binaerbaum<Type> implements BinaerbaumInterface<Type> {
    
    Binaerbaum<Type> bin_left;
    Binaerbaum<Type> bin_right;
    Type bin_value;
    

    public Binaerbaum<Type>() {                                         // Fehlermeldung identifier expected
        Binaerbaum<Type> bin = new Binaerbaum<Type>();
    }

    public Binaerbaum<Type>(final Binaerbaum<Type> left, final Type value, final Binaerbaum<Type> right) {
        Binaerbaum<Type> bin_left = new Binaerbaum<Type>();
        Binaerbaum<Type> bin_right = new Binaerbaum<Type>();
        bin_value = null;
    }

    public Binaerbaum<Type> left() {

    }

    public Binaerbaum<Type> right() {

    }

    public Type value() {
      
    }

    public boolean empty() {
        if(bin_left == null && bin_right == null && bin_value == null )   return true;
        else   return true;
    }

    public void traverse(int tiefe) {
        System.out.println("");
    }
    ;
}

Warum krieg ich in Zeile 10 die Fehlermeldung identifier expected?

Und warum musste ich in der vorletzten Zeile ein ";" machen? Das ergibt für mich gar keinen Sinn, aber der Compiler hat erst aufgehört zu meckern, bis ichs gemacht hab.

Wie numeriere ich jetzt die Elemente?
Also ich hab mir überlegt:

Wurzel(Element #1, also 2^0+0) tiefe = 0

#2 : 2^1+0 #3: 2^1+1 tiefe = 1

#4 : 2^2+0 #5 : 2^2+1 #6 : 2^2+2 #7 : 2^2+3 tiefe = 2


also pro "Zeile" immer: (2^tiefe)+0, ...., (2^tiefe)+((2^tiefe)-1)

Aber wie schreibe ich das als Code???

Wie schreibe ich die values in die Elemente?

 

[burgfried]

ich habe folgende fragen an dich:
-) musst du nur eine klasse implementieren, die das interface erfüllt? (weil das interface an und für sich macht gar keinen sinn, wenn du nicht unterschiedliche arten von binärbäumen implementierst.)

-) sagt dir der begriff generizität etwas? (wenn nein, dann solltest du vielleicht bei deiner aufgabe nur eine art von binärbaum der einen spezifischen Typ wie beispielsweise String übernimmt.) Wenn du aber wirklich eine generische klasse schreiben sollst, dann suche dir bitte auch ein tutorial über generizität aus dem internet.


ich habe hier einmal eine generische lösung implementiert.

import java.io.*;

public class Binaerbaum<E> {

    Binaerbaum<E> bin_left;
    Binaerbaum<E> bin_right;
    E bin_value;


    public Binaerbaum() {                                         // Fehlermeldung identifier expected
        bin_left = null;
        bin_right = null;
        bin_value = null;
    }

    public Binaerbaum(Binaerbaum<E> left, E element, Binaerbaum<E> right) {
        bin_left = left;
        bin_right = right;
        bin_value = element;
    }

    public Binaerbaum<E> left() {
      return bin_left;
    }

    public Binaerbaum<E> right() {
      return bin_right;
    }

    public E value() {
      return bin_value;
    }

    public boolean empty() {
        return ((bin_left == null) && (bin_right == null) && (bin_value == null));
    }

    public void traverse(int tiefe) {
        System.out.println("");
    }

}

ein paar dinge zur erklärung.

-) die fehlermeldung kam, weil ich beim constructor <Type> dazugeschrieben habe. das war falsch.
-) E ist ein stellvertreter für ein beliebiges Objekt. Zum Beispiel String. Dh überall wo jetzt ein E steht könntest Du ein String objekt verwenden. Das ist das konzept von generezität. du brauchst die klasse nur einmal implementieren, kannst aber jederzeit verschiedene objekte verwenden. natürlich auch selbst definierte.
-) bei return ((bin_left == null) && (bin_right == null) && (bin_value == null)); brauchst du keine if abfrage verwenden. der gesamte ausdruck ergibt entweder wahr oder falsch. das zusätzlich noch für eine if abfrage zu verwenden, verkompliziert es nur.
-) die konstruktoren sind nur da um die member variablen zu setzen. du darfst da drinnen nicht nochmal einen konstruktor aufrufen.
-) wenn du member variablen setzen willst, darfst du die variablen nicht nochmals definieren:
wenn du schreibst
Binaerbaum bin_left = left;
definierst du in der methode selbst eine lokale variable namens bin_left. d.h. du setzt nicht die member variable bin_left. bitte pass auf so etwas auf.

 

[burgfried]

ein tutorial für generizität findest du unter
http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf

wenn du die tiefe mit ganzzahligen werten versiehst solltest die variable bin_value vom typ int sein und keinen generischen klassentyp haben.

zusätzlich solltest du pro knoten die tiefe speichern, in der er sich befindet.

aber irgendwie ist das für mich ziemlich konfus und ich verstehe die aufgabenstellung immer noch nicht ganz. gibt es da keine offizielle angabe, die man sich im netz anschauen kann?