Binärbaum Blätter finden und Ausgeben

[dan1996]

Hi, hat jemand eine Idee wie oder mit welchen Algorithmus man in einem Binärbaum die Blätter finden kann und Ausgibt?

 

[httpdigest]

Rekursiv oder iterativ mit Stack.

 

[dan1996]

rekursiv am besten

 

[httpdigest]

Das war nicht als Frage gemeint. Also: "Du kannst es rekursiv oder iterativ mit Stack lösen."
Jetzt darfst du erstmal bitte selber Lösungsvorschläge machen, oder erklären, wo es hakt, bzw. wieso du selber nicht auf eine Lösung kommst.

 

[Xyz1]

iterativ mit Queue ginge aber auch (Dann würde sich ggf die Ausgabereihenfolge ändern)

 

[dan1996]

ich "laufe" mit der Methode jeden Knoten ab, aber mein Problem ist dass ich nicht hinkriege, oder nicht weiß, wie ich alle Blätter zurückbekomme

public void tiefe(Tree r) {

        if (r.root != null) {

            tiefe(r.root.l);

            System.out.println(r.root.v);
            tiefe(r.root.r);

            // System.out.println("Blatt:\t" + r.root.v);

        }
    }

 

[httpdigest]

Erstmal wäre es hilfreich, zu zeigen, wie deine Tree Klasse und alle eventuell weiteren beteiligten Knoten-Klassen genau aussehen.

 

[dan1996]

class TNode {

    public int v;

    public Tree l, r;

    public int t = 0;

    public TNode(int v) {
        this.v = v;
        this.l = new Tree();
        this.r = new Tree();
    }

}

class Tree {
    public TNode root = null;

    public boolean isEmpty() {
        return root == null;
    }

    public void insert(int element) {
        if (isEmpty()) {
            root = new TNode(element);
            root.t = 1 + root.t;
        } else if (element < root.v) {
            root.l.insert(element);
            root.l.root.t = 1 + root.t;
        } else {
            root.r.insert(element);
            root.r.root.t = 1 + root.t;
        }
    }


    public int countNodes(Tree r) {
        if (r.root == null) {
            return 0;
        } else {
            int count = 1;
            count += countNodes(r.root.l);
            count += countNodes(r.root.r);
            return count;
        }
    }

    public void tiefe(Tree r) {

        if (r.root != null) {

            tiefe(r.root.l);

            System.out.println(r.root.v);
            
            tiefe(r.root.r);

            // System.out.println("Blatt:\t" + r.root.v);

        }
    }

 

[httpdigest]

Also diese Klassen solltest du nochmal von Grund auf neu designen. Warum hat denn ein Knoten im Baum zwei Referenzen auf den Baum und nicht auf die Kindknoten? So kannst du eigentlich überhaupt nicht durch die Knoten des Baumes iterieren.
Du solltest vielleicht erstmal die genaue Bedeutung von "was ist bei dir ein Baum/Tree" und "was ist bei dir ein Knoten/TNode" klären.

 

[dan1996]

Die Klasse wurde nicht von mir geschrieben, die Klasse war für die Aufgabe gegeben und die soll halt um die Methode erweitert werden, die die Blätter ausgibt

 

[httpdigest]

Die Klasse wurde nicht von mir geschrieben, die Klasse war für die Aufgabe gegeben

Das will ich mal hart bezweifeln. Niemand würde so einen Quatsch in eine Aufgabenstellung schreiben. Nein wirklich, das ist ganz großer Mist. Zumal die Instanzmethoden der Klasse Tree auch überhaupt kaum mit der eigentlichen `this` Instanz arbeiten sondern immer unnötigerweise den Tree als Parameter bekommen.

 

[httpdigest]

Aber sei's drum. Einen Blattknoten würdest du hier daran erkennen, dass `l.root == null` ist bzw. `r.root == null`.
Aber ehrlich, die Benennung der Felder und auch der Methoden ist einfach unfassbar schlecht.

 

[dan1996]

Das will ich mal hart bezweifeln. Niemand würde so einen Quatsch in eine Aufgabenstellung schreiben. Nein wirklich, das ist ganz großer Mist.

Naja so ist es halt in der Aufgabe, arbeite grade paar Altklausuren durch und es gibt noch paar ähnliche Aufgabe die genau so mit der Tree und Node Klasse aufgebaut sind

Aber ehrlich, die Benennung der Felder und auch der Methoden ist einfach unfassbar schlecht.

Die Benennung hatte ich eben noch geändert, damit es nicht komplett identisch ist

 

[kneitzel]

Das will ich mal hart bezweifeln. Niemand würde so einen Quatsch in eine Aufgabenstellung schreiben. Nein wirklich, das ist ganz großer Mist. Zumal die Instanzmethoden der Klasse Tree auch überhaupt kaum mit der eigentlichen `this` Instanz arbeiten sondern immer unnötigerweise den Tree als Parameter bekommen.

Aber die Methoden stammen ja von ihm so wie ich das verstanden habe. Das da also mit dem Parameter statt mit this gearbeitet wird, könnte er dann ja anpassen.

Aber den Aufbau des Baumes sehe ich so auch zum ersten Mal. Ich kenne es eigentlich auch so, dass es nur einen Tree gibt, der dann Nodes hat. Ob sich da jemand gedacht hat, dass er da dann rechts und links wieder jeweils einen Baum haben will? Und daher jeweils wieder einen Tree genommen hat? Aber den wirklichen Sinn dahinter sehe ich nicht, denn das macht es ja nur unnötig komplexer und damit schwerer zu verstehen....

 

[dan1996]

Aber die Methoden stammen ja von ihm so wie ich das verstanden habe. Das da also mit dem Parameter statt mit this gearbeitet wird, könnte er dann ja anpassen.

Aber den Aufbau des Baumes sehe ich so auch zum ersten Mal. Ich kenne es eigentlich auch so, dass es nur einen Tree gibt, der dann Nodes hat. Ob sich da jemand gedacht hat, dass er da dann rechts und links wieder jeweils einen Baum haben will? Und daher jeweils wieder einen Tree genommen hat? Aber den wirklichen Sinn dahinter sehe ich nicht, denn das macht es ja nur unnötig komplexer und damit schwerer zu verstehen....

Die einzigen Methoden die von mir stammen sind diese beiden, der Rest ist vorgegeben

public int countNodes(Tree r) {
        if (r.root == null) {
            return 0;
        } else {
            int count = 1;
            count += countNodes(r.root.l);
            count += countNodes(r.root.r);
            return count;
        }
    }

    public void tiefe(Tree r) {

        if (r.root != null) {

            tiefe(r.root.l);

            System.out.println(r.root.v);
            
            tiefe(r.root.r);

            // System.out.println("Blatt:\t" + r.root.v);

        }

 

[kneitzel]

Ja genau. Und genau diese beiden Methoden wurden bemängelt.

Du könntest diese so umschreiben, dass kein Parameter übergeben wird. Also kein Parameter Tree r. Statt dem r verwendest Du dann this bzw. lässt es direkt weg. Der Aufruf von z.B. tiefe(r.root.r); wird dann zu root.r.tiefe();

 

[dan1996]

Okay danke werde ich umschreiben aber ich kriege es immer noch nicht hin eine rekursive Methode zu schreiben die mir die Blätter ausgibt

 

[httpdigest]

Die Frage hier ist: Was kennzeichnet denn überhaupt einen Blattknoten hier?
Denn es kann ja auch sowohl nur der linke als auch nur der rechte Teilbaum gefüllt sein. Z.B. beim Einfügen von 1, 2, 3, 4 (in dieser Reihenfolge) so dass sich ein rechtslastiger Baum ergibt. Ist jetzt nur 4 der Blattknoten?

 

[dan1996]

Ist jetzt nur 4 der Blattknoten?

Ja genau

 

[httpdigest]

Na dann prüfe doch in "tiefe" für den aktuellen Tree, ob sein root.l.root == null ist und sein root.r.root == null ist. Dann ist der Knoten vom aktuellen Tree ein Blattknoten.

 

[dan1996]

angenommen der Baum sieht so aus, dann wären die Blätter die mir die Methode ausgeben soll 4;9;10

 

[kneitzel]

Also rekursive Methoden sind unter dem Strich immer gleich aufgebaut:
a) Man hat ein Abbruchkriterium
b) man hat rekursive Aufrufe

Wenn Du jetzt einen Baum durchgehst: Wann musst (kannst) du rekursiv etwas aufrufen? Wann geht es nicht mehr weiter?

 

[dan1996]

Danke hat endlich geklappt

public void tiefe() {
            
        if(this.root != null ) {
            
            root.l.tiefe();
            root.r.tiefe();
            if(root.l.root == null && root.r.root == null ) {
                System.out.println(root.v);
            }
            
        }