Fragen zu Binärbaum

[PaulG]

Guten Tag und frohe Weihnachten.

public class Baum
{
Knoten wurzel;

Baum (int tiefe) 
{
		Knoten wurzel = new Knoten(tiefe);
		wurzel.erstelleBaum(tiefe);
}

public static void main(String[] args)
{

Baum bBaum = new Baum(5);

}

}

class Knoten
{
Knoten links;
Knoten rechts;
int tiefe;

Knoten(int tiefe)
{
this.tiefe = tiefe;
}

Baum erstelleBaum(int tiefe)
{
//
//
// Hier ist mein Problem
//
//
return null; 
}

}

Mein Problem ist nun die Funktion erstelleBaum. Ich soll nun rekursiv einen Baum mit der übergebenen Tiefe erstellen. Mein Problem ist, dass die Wurzel nicht an die Funktion übergeben wird/werden darf. Ich muss doch nun irgendwie auf den linken und den rechten Knoten der Wurzel zugreifen, oder? Denn die Wurzel ist die Spitze des Baumes.
Also was meint ihr?
Muss ich den Knoten Wurzel als public..static oder so ähnlich deklarieren damit ich in der Funktion erstelleBaum root.links schreiben kann?
Und meine zweite Frage ist wie soll ich in der Funktion erstelleBaum einen Baum zurückgeben?
Ich habe alles gemacht, wie es vorgegeben ist und die Funktion war auch so vorgegeben, aber wie gebe ich einen Baum zurück? Einen neuen in der Funktion erstellen wäre doch auch unsinnig, da ich es schon in der main-Methode gemacht habe, was so vorgegeben war.

 

[Marcinek]

Muss ich den Knoten Wurzel als public..static oder so ähnlich deklarieren damit ich in der Funktion erstelleBaum root.links schreiben kann?

Angenommen du würdest das machen. Wie erstellst du dann zwei Bäume in einem Programm?

Ich habe alles gemacht, wie es vorgegeben ist und die Funktion war auch so vorgegeben, aber wie gebe ich einen Baum zurück? Einen neuen in der Funktion erstellen wäre doch auch unsinnig, da ich es schon in der main-Methode gemacht habe, was so vorgegeben war.

Bist du sicher, dass die Methode erzeuge Baum, die einen Baum erzeugen soll in einem KNOTEN implementiert werden soll? - Das macht nämlich nicht so viel sinn.

Dies würde eher der Baum selber machen, denn nur er soll wissen, welche Tiefe er hat und wie die Wurzel heißt.

Und als Baum würde er dann einfach sich selber zurückgegeben.

Grruß,

Martin

 

[PaulG]

Vielen Dank, dass du mir hilfst Marcinek 🙂

Angenommen du würdest das machen. Wie erstellst du dann zwei Bäume in einem Programm?

Sehr gute Gegenfrage Marcinek, das ist also keine Lösung.

Bist du sicher, dass die Methode erzeuge Baum, die einen Baum erzeugen soll in einem KNOTEN implementiert werden soll? - Das macht nämlich nicht so viel sinn.

Ich habe eben noch einmal nachgesehen, es soll wirklich in der Klasse Knoten implementiert werden.
Aber hier geht es ja anscheinend nicht.
Demnach werde ich jetzt am besten die Funktion in die Klasse Baum implementieren, oder?

Aber angenommen die Funktion ist in der Klasse Baum, die Eingabeparameter sind vorgegeben ( also nur int tiefe) muss ich dann nicht trotzdem wurzel.links etc. schreiben?

Vielen Dank nochmal Marcinek, da ich gerade etwas verzweifle.

 

[deetee]

Schau dir das Composite Pattern an, es ist für allgemeine Baumstrukturen geeinget.

Kompositum (Entwurfsmuster) ? Wikipedia

Das Kompositum ist die konkrete BinärBaum Klasse.
Die Komponente ist die abstrakte Baum Klasse.
Das Blatt ist natürlich dann ein Knoten Objekttyp.

Die Methode erstelleBaum() in der Klasse Knoten verstehe ich als eine Fabrikmethode. Das bedeutet für deinen vorhanden Code folgendes:

• erstelleBaum() muss den Objekttyp BinärBaum zurückgeben. Deshalb auch am besten umbenennen.
• die Klasse Knoten ist ein KonkreterErzeuger
• die Klasse BinärBaum ist ein KonkretesProdukt
• die Klasse Baum ist ein Produkt
• eine Erzeuger Klasse gibt es bei dir momentan nicht

 

[Marcinek]

Nach nähreren Nachdenken, müsstest du für die komplette Methode neben der Tiefe auch der Aktuelle Knoten übergeben werden.

 

[PaulG]

@deeteee

Aber von einem Kompositum habe ich noch nichts in der Vorlesung gehört und das ganze hilft mir leider nicht weiter. :/

@Marcinek

Baum erstelleBaum(Knoten k, int tiefe)
{

while ( tiefe != 0)
{
Knoten blattLinks = new Knoten(tiefe);
Knoten blattRechts = new Knoten(tiefe);
k.links = blattLinks;
k.rechts = blattRechts;
tiefe--;
erstelleBaum(blattLinks, tiefe);
erstelleBaum(blattRechts, tiefe);
}

return null; 
}

1.Frage:
Ist das so richtig?

2.Frage:
Wie soll ich das jetzt mit dem return lösen?
Muss ich überhaupt etwas zurückgeben?
Der Baum ist doch jetzt so oder so erstellt?

Dankeschön euch beiden.

 

[Marcinek]

Du kannst "return this;" machen.

Ansonsten mal laufen lassen und schauen, ob die Knoten angelegt werden ;D

Achso. Die whileschleife ist unnötig.

 

[PaulG]

In der Aufgabe steht:
Die Methode generiert solange neue linke und rechte Nachfolgerknoten bis die Tiefe des Baumes auf 0 dekrementiert wurde.

Ich muss doch irgendwann abbrechen, sonst ist es doch eine Endlosschleife.

Uns wurde noch eine Klasse "xBaum" bereitgestellt mit einigen Funktionen.
Zum Beispiel eine um den ganzen Baum auszugeben.

Wenn ich sie in der main-Funktion aufrufe mit:

xBaum.printSVG(bBaum, "bBaum.html");

Erhalte ich die Fehlermeldung:
Exception in thread "main" java.lang.NullPointerException

Und in der Klasse xBaum, wird diese Zeile angezeigt:
int tiefe = bBaum.wurzel.tiefe;

Das heißt die tiefe von der Wurzel ist null, oder?
Was habe ich falsch gemacht?

 

[Timothy Truckle]

Ich würde die Sache anders angehen:

Die Klasse

Baum

wird gestrichen. Die Methode

erstelleBaum

auch.
Jeder Knoten erzeugt in seinem Konstruktor direkt seine 2 Subknoten, und reduziert dabei die (Rest-)Tiefe:

public Knoten(int tiefe){
  int restTiefe = tiefe-1;
  if(0<restTiefe){
    links= new Knoten(restTiefe);
    rechts = new Knoten(restTiefe);
  }
}

Das wäre alles.

passt dass noch zur Aufgabe?

bye
TT

 

[Timothy Truckle]

In der Aufgabe steht:
Die Methode generiert solange neue linke und rechte Nachfolgerknoten bis die Tiefe des Baumes auf 0 dekrementiert wurde.

Ich muss doch irgendwann abbrechen, sonst ist es doch eine Endlosschleife.

Gut erkannt!
BTW: dekrementieren heist: um eins verringern...

Uns wurde noch eine Klasse "xBaum" bereitgestellt mit einigen Funktionen.
Zum Beispiel eine um den ganzen Baum auszugeben.

Wenn ich sie in der main-Funktion aufrufe mit:

xBaum.printSVG(bBaum, "bBaum.html");

Erhalte ich die Fehlermeldung:
Exception in thread "main" java.lang.NullPointerException

Und in der Klasse xBaum, wird diese Zeile angezeigt:
int tiefe = bBaum.wurzel.tiefe;

Das heißt die tiefe von der Wurzel ist null, oder?
Was habe ich falsch gemacht?

Nein.
Das heist, dass entweder

bBaum

auf

null

verweist oder

wurzel

.

bye
TT

 

[PaulG]

Vielen lieben Dank Timothy Truckle 🙂

Leider würde das schon zu sehr von der Aufgabenstellung abweichen.

Ich habe alle Aufgabe befolgt bis zu der Aufgabe mit der Funktion erstelleBaum.
Und dann sieht das ganze so aus, wie in meinem ersten Post.

Das heist, dass entweder bBaum auf null verweist oder wurzel .

Aber wie kann das sein?

Wir haben den Baum doch ganz einfach erzeugt mit der Tiefe 5 und dann die einzelnen Knoten, anfangend mit der Wurzel miteinander verknüpft?

Was ist falsch? 🙁

 

[Timothy Truckle]

Was ist falsch? 🙁

Was mir so spontan auffällt ist, dass die Signatur von

erstelleBaum

, die im konstruktor von

Knoten

aufgerufen wird nicht mit der übereistimmt, in der Du die Subknoten erzeugst. Schau da noch mal genau drauf.

Und dem Hinweis mit den

while

solltest Du auch noch mal Beachtung schenken: wie viele Knoten werden beim ersten Aufruf erzeugt?

bye
TT

 

[PaulG]

Also momentan sieht es so aus:

public class Baum
{
Knoten wurzel;
 
Baum (int tiefe) 
{
        Knoten wurzel = new Knoten(tiefe);
        erstelleBaum(wurzel, tiefe);
}
 
public static void main(String[] args)
{
 
Baum bBaum = new Baum(5);
 
}
 
}
 
class Knoten
{
Knoten links;
Knoten rechts;
int tiefe;
 
Knoten(int tiefe)
{
this.tiefe = tiefe;
}
 
Baum erstelleBaum(Knoten k, int tiefe)
{
 
while ( tiefe != 0)
{
Knoten blattLinks = new Knoten(tiefe);
Knoten blattRechts = new Knoten(tiefe);
k.links = blattLinks;
k.rechts = blattRechts;
tiefe--;
erstelleBaum(blattLinks, tiefe);
erstelleBaum(blattRechts, tiefe);
}
 
return null; 
}
 
}

Und dem Hinweis mit den while solltest Du auch noch mal Beachtung schenken: wie viele Knoten werden beim ersten Aufruf erzeugt?

Es werden zwei Knoten erzeugt..?
Oder hätte ich die Tiefe vor dem erzeugen der Knoten um 1 verringern sollen?

Edit:
Ich habe bBaum.wurzel ausgeben lassen und es kommt null bei raus.
Warum?

 

[deetee]

Edit:
Ich habe bBaum.wurzel ausgeben lassen und es kommt null bei raus.
Warum?

Der Grund liegt im Konstruktor von Baum.

Für welches Semester ist diese Aufgabe?

 

[Timothy Truckle]

Es werden zwei Knoten erzeugt..?

Nein, es bleiben 2 der

tiefe*2

erzeugten Knoten über.

Oder hätte ich die Tiefe vor dem erzeugen der Knoten um 1 verringern sollen?

Ja, aber dass reicht nicht.

while

ist hier einfach das falsche Schlüsselwort, weil Du eine Entscheidung brauchts, keine Schleife. Schau noch mal in meinen Vorschlag.

Ich habe bBaum.wurzel ausgeben lassen und es kommt null bei raus.
Warum?

Du hast 2 Variablen mit dem Namen

knoten

: einmal eine Klassenvariable und eine im lokalen Bereich des Konstruktors, welche die Klassenvariable überdeckt.

Obwohl Oracle in den offiziellen Namenskonventionen davon ab rät solltest Du Dir angewöhnen Klassenvariablen einen besonderen Präfix zu geben. Ich kennzeichne sie mit einem Unterstrich

Object _myMember;

. Dann fallen solche Sachen ehr auf.

Außerdem solltest Du Klassenvariablen nach Möglichkeit

final

deklarieren. In diesem Fall wäre der Code so nicht kompilierbar, weil der Klassenvariablen kein Wert zugewiesen wurde (was Dich auf den Fehler aufmerksam gemacht hätte). Allerdings kann man der Klassenvariablen dann auch keinen neuen Wert zuweisen, was in diesem Fall aber gewünscht wäre.

bye
TT

 

[PaulG]

@deetee

Der Grund liegt im Konstruktor von Baum.

Wenn ich im Konstruktor die Wurzel ausgebe, ist sie nicht null.

	Baum(int tiefe) {
		Knoten wurzel = new Knoten(tiefe);
		System.out.println(wurzel);
		wurzel.erstelleBaum(wurzel, tiefe);
		System.out.println(wurzel.left);
	}

Beide Male wird nicht null ausgeben.

Warum ist sie null, wenn ich in der main-Funktion schreibe:

Baum bBaum = new Baum(5);
System.out.println(bBaum.wurzel);

Das ganze ist für das erste Semester.

Kannst du mir bitte einen Tipp geben, was im Konstruktor falsch ist?

Vielen Dank 🙂

 

[PaulG]

@Timothy Truckle

Nein, es bleiben 2 der tiefe*2 erzeugten Knoten über.

Das verstehe ich nicht.
Ich übergebe der Funktion die Tiefe mit dem Wert 5.
Dann werden zwei Knoten mit der Tiefe 5 erstellt ( was ja eigentlich falsch ist, die Wurzel soll die Tiefe 5 haben).
Aber dann wurden doch im ersten Aufruf nur zwei Knoten erzeugt.
Wie kommt man auf tiefe*2?

Du hast 2 Variablen mit dem Namen knoten : einmal eine Klassenvariable und eine im lokalen Bereich des Konstruktors, welche die Klassenvariable überdeckt.

Meinst du zwei Variablen mit dem Namen Knoten, oder zwei Variablen vom Typ Knoten?
Weil ich weiß nicht welche Variable du meinst, die Knoten heißt?

Danke euch beiden 🙂

 

[Timothy Truckle]

Ich übergebe der Funktion die Tiefe mit dem Wert 5.

Ja.

Dann werden zwei Knoten mit der Tiefe 5 erstellt ( was ja eigentlich falsch ist, die Wurzel soll die Tiefe 5 haben).

Nein.
Wenn du in die Methode ein tritts prüft

while

erst mal den aktuellen Wert von

tiefe

. Da dieser größer 0 ist wird die Schleife betreten und 2 Subknoten erstellt. an der zum

while

-Block gehörenden schließenden

}

springt das Program zurück zu Zeile 34 und prüft erneut den aktuellen Wert von

tiefe

. der ist wieder größer 0...

Aber dann wurden doch im ersten Aufruf nur zwei Knoten erzeugt.
Wie kommt man auf tiefe*2?

Da habe ich mich verschätzt. Es sind viel mehr. Das muss man mit binomischen Formeln ausrechnen. Es blebt aber nur die gewünscht Anzahl über, weil alle anderen Knotenobjekte vom Garbagecollector wieder abgeräumt werden.

Meinst du zwei Variablen mit dem Namen Knoten, oder zwei Variablen vom Typ Knoten?

Wir beide meinen Zeile 7 aus Deinem letzten Listing.

Weil ich weiß nicht welche Variable du meinst, die Knoten heißt?

[EDIT] Die Variable heißt [STRIKE]

knoten

[/STRIKE]

wurzel

[STRIKE], nicht

Knoten

. Groß-/Kleinschreibung ist in Java wichtig![/STRIKE].[/EDIT]

bye
TT

 

[deetee]

Kannst du mir bitte einen Tipp geben, was im Konstruktor falsch ist?

Mach aus

Knoten wurzel = new Knoten(tiefe);

das

wurzel = new Knoten(tiefe);

und es funktioniert wie du es möchtest.

Das ganze Thema nennt sich "Scope von Variablen". Einfach mal googlen oder dem Prof besser zuhören 😉

 

[PaulG]

Vielen Dank erstmal allen.

Eigentlich ist die Funkton erstelleBaum in der Aufgabe vorgegeben, und der einzige Eingabeparameter ist "int tiefe", aber Marcinek hat mich ja daraufhingewiesen, dass ich keinen zweiten Baum erstellen kann, wenn ich wurzel public deklariere und es in der Funktion verwende(mit wurzel.links). Aber in der Aufgabe steht nur das wir einen Binärbaum erstellen sollen. Also kann ich es so machen, dass ich root public mache oder gibt es einen anderen Ausweg?


Ich habe das ganze etwas überarbeitet, wie sieht es jetzt aus?

public class Baum
{
Knoten wurzel;
 
Baum (int tiefe) 
{
        wurzel = new Knoten(tiefe);
        wurzel.erstelleBaum(wurzel, tiefe);
}
 
public static void main(String[] args)
{
 
Baum bBaum = new Baum(5);
 
}
 
}
 
class Knoten
{
Knoten links;
Knoten rechts;
int tiefe;
 
Knoten(int tiefe)
{
this.tiefe = tiefe;
}
 
Baum erstelleBaum(Knoten k, int tiefe)
{

tiefe = tiefe - 1; 
 
if ( tiefe > 0)
{
Knoten blattLinks = new Knoten(tiefe);
Knoten blattRechts = new Knoten(tiefe);
k.links = blattLinks;
k.rechts = blattRechts;
erstelleBaum(blattLinks, tiefe);
erstelleBaum(blattRechts, tiefe);
}
 
return null; 
}
 
}

 

[Timothy Truckle]

Eigentlich ist die Funkton erstelleBaum in der Aufgabe vorgegeben, und der einzige Eingabeparameter ist "int tiefe",

Aus meiner sicht ist das Hauptproblem der aufgabe, dass

erstelleBaum

im Konstruktor von

Baum

aufgerufen wird. Im besonderen Sört mich, dass

erstelleBaum

ein

Baum

-Objekt zurückliefern soll. Das ist irgentwie nicht konsistent...

aber Marcinek hat mich ja daraufhingewiesen, dass ich keinen zweiten Baum erstellen kann, wenn ich wurzel public deklariere und es in der Funktion verwende(mit wurzel.links). Aber in der Aufgabe steht nur das wir einen Binärbaum erstellen sollen. Also kann ich es so machen, dass ich root public mache oder gibt es einen anderen Ausweg?

Wenn die Aufgabe wirklich so lautet sehe ich keinen.

Ich habe das ganze etwas überarbeitet, wie sieht es jetzt aus?

Sieht aus, als könnte es so funktionieren. Es stört nur noch, dass

erstelleBaum

der Rückgabetyp

Baum

hat aber

null

zurück gibt, aber wenn dass Vorgabe ist...

bye
TT

 

[hüteüberhüte]

Rekursiv erstellen, rekursiv drucken:

import java.util.Arrays;
import java.util.List;

public class BinTree {

    private Object content;
    private BinTree left, right;

    public BinTree(Object content, BinTree left, BinTree right) {
        this.content = content;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return content.toString();
    }

    public static void build(BinTree current, List<Integer> index, int row) {
        if (row <= 0) {
            return;
        }
        current.left = new BinTree(index.get(0), null, null);
        index.set(0, index.get(0) + 1);
        build(current.left, index, row - 1);

        current.right = new BinTree(index.get(0), null, null);
        index.set(0, index.get(0) + 1);
        build(current.right, index, row - 1);
    }

    public static void print(BinTree current) {
        if (current == null) {
            return;
        }
        System.out.println(current);
        print(current.left);
        print(current.right);
    }

    public static void main(String[] args) {
        BinTree root = new BinTree(1, null, null);
        build(root, Arrays.asList(2), 3);
        print(root);
    }
}

Mit

List<Integer> index

musste ich irgendwie ein bisschen tricksen. int/Integer ist kein veränderbares Objekt. Die Höhe/Tiefe von Binärbäumen heißt auch nicht Reihe, aber naja, jeder weiß jawas gemeint ist.

😀