Binärbaum Blätter

[Valke001]

Stecke gerade etwas fest. Bis jetzt habe ich folgendes:

public int gibAnzahlBlaetter(BinaryTree<Integer> b){
        if(b.getContent()!=null){
            gibAnzahlBlaetter(b.getLeftTree());
            gibAnzahlBlaetter(b.getRightTree());
            if(b.getLeftTree()==null&&b.getRightTree()==null){
                q++;
            }
        }
        return q;
    }

q ist ein zuvor als null festgelegter Integer.

Die Klasse Baum sieht wie folgt aus:

public class BinaryTree<ContentType> {

  
    private class BTNode {

        private ContentType content;
        private BinaryTree<ContentType> left, right;

        private BTNode(ContentType pContent) {
            this.content = pContent;
            left = new BinaryTree<ContentType>();
            right = new BinaryTree<ContentType>();
        }

    }

    private BTNode node;

    public BinaryTree() {
        this.node = null;
    }

    public BinaryTree(ContentType pContent) {
        if (pContent != null) {
            this.node = new BTNode(pContent);
        } else {
            this.node = null;
        }
    }

    public BinaryTree(ContentType pContent, BinaryTree<ContentType> pLeftTree, BinaryTree<ContentType> pRightTree) {
        if (pContent != null) {
            this.node = new BTNode(pContent);
            if (pLeftTree != null) {
                this.node.left = pLeftTree;
            } else {
                this.node.left = new BinaryTree<ContentType>();
            }
            if (pRightTree != null) {
                this.node.right = pRightTree;
            } else {
                this.node.right = new BinaryTree<ContentType>();
            }
        } else {
            this.node = null;
        }
    }

    public boolean isEmpty() {
        return this.node == null;
    }
 
    public void setContent(ContentType pContent) {
        if (pContent != null) {
            if (this.isEmpty()) {
                node = new BTNode(pContent);
                this.node.left = new BinaryTree<ContentType>();
                this.node.right = new BinaryTree<ContentType>();
            }
            this.node.content = pContent;
        }
    }
 
    public ContentType getContent() {
        if (this.isEmpty()) {
            return null;
        } else {
            return this.node.content;
        }
    }
    
    public void setLeftTree(BinaryTree<ContentType> pTree) {
        if (!this.isEmpty() && pTree != null) {
            this.node.left = pTree;
        }
    }
  
    public void setRightTree(BinaryTree<ContentType> pTree) {
        if (!this.isEmpty() && pTree != null) {
            this.node.right = pTree;
        }
    }

    public BinaryTree<ContentType> getLeftTree() {
        if (!this.isEmpty()) {
            return this.node.left;
        } else {
            return null;
        }
    }
    
    public BinaryTree<ContentType> getRightTree() {
        if (!this.isEmpty()) {
            return this.node.right;
        } else {
            return null;
        }
    }

}

Nun würde ich mich freuen, wenn mir jemand helfen könnte, die Anzahl der Blätter ermitteln zu können.

 

[KonradN]

Wie wäre es, wenn du es erst einmal in Worten beschreibst. Wie ermittelt du die Anzahl der Blätter eines Nodes?

 

[Valke001]

Ich schaue mir bei meinen Nodes den linken und rechten Teilbaum an, bis ich eine Node finde, die weder einen linken noch rechten Teilbaum hat. Jedes Mal, wenn ich so eine Node finde, erhöhe ich meinen Zähler um 1. Das mache ich, bis ich den Baum einmal ganz durchgegangen bin.

 

[KonradN]

Also das reicht mir so nicht. Wenn ich nur einen Baum und so eine Anleitung habe, dann kann ich zu keinem Ergebnis kommen.

Und wo ist der Zähler? Das ist doch kein Attribut des Baumes. Woher nimmst du ihn also?

Wenn du zählen willst, dann musst du den weg beschreiben, wie du genau durch den Baum gehen willst (durch den Baum iterieren kann man auch sagen ... deutet an, dass man eine iterative Lösung hat. Willst du vermutlich nicht).

Oder du gibst an, wie man die Lösung rekursiv findet. Das ist dann die Angabe wie bei den Maghematikern, wo ein oder mehrere Startpunkte gegeben sind und eine Formel.
Was ist die Anzahl der Blätter des Baumes?
Eine Unterscheidung hattest du schon genannt:
A) rechter und linker Teilbaum sind null
B) mindestens einer der Teilbäume ist nicht null

 

[Valke001]

Hier ist erstmal die „Verwaltungsklasse":
[CODE lang="java" title="H"]public class Zahlenbaumverwaltung{
private BinaryTree<Integer> baum;
int z,q;
public Zahlenbaumverwaltung(){
BinaryTree<Integer> b7 = new BinaryTree(7);
BinaryTree<Integer> b10 = new BinaryTree(10);
BinaryTree<Integer> b6 = new BinaryTree(6,null,b7);
BinaryTree<Integer> b11 = new BinaryTree(11,b10,null);
BinaryTree<Integer> b9 = new BinaryTree(9,b6,b11);
BinaryTree<Integer> b3 = new BinaryTree(3);
BinaryTree<Integer> b5 = new BinaryTree(5,b3,b9);
baum = b5;

z = 0;
q = 0;

ausgabeAllgemein();

}

public int gibSumme(){
return gibSummeRek(baum);
}

private int gibSummeRek(BinaryTree<Integer> pBaum){
int a = 0;
if(pBaum.getContent() != null){
a = pBaum.getContent() + gibSummeRek(pBaum.getLeftTree()) + gibSummeRek(pBaum.getRightTree());
}
return a;
}

public int gibAnzahlKnoten(BinaryTree<Integer> b){
z++;
if(b.getLeftTree().getContent()!=null){
gibAnzahlKnoten(b.getLeftTree());
}
if(b.getRightTree().getContent()!=null){
gibAnzahlKnoten(b.getRightTree());
}
return z;
}

/**
* Liefert die Anzahl aller Blätter des Baumes.
*/
public int gibAnzahlBlaetter(BinaryTree<Integer> b){
//Hier Quellcode einfuegen.
if(b.getContent()!=null){
gibAnzahlBlaetter(b.getLeftTree());
gibAnzahlBlaetter(b.getRightTree());
if(b.getLeftTree()==null&&b.getRightTree()==null){
q++;
}
}
return q;
}

public int gibTiefe(){
return 0;
}

public void preorderAusgabe(){
besuchePreorder(baum);
}

public void inorderAusgabe(){
besucheInorder(baum);
}

public void postorderAusgabe(){
besuchePostorder(baum);
}

private void besuchePreorder(BinaryTree<Integer> b){
System.out.println(b.getContent());
if(b.getLeftTree().getContent()!=null){
besuchePreorder(b.getLeftTree());
}
if(b.getRightTree().getContent()!=null){
besuchePreorder(b.getRightTree());
}
}

private void besucheInorder(BinaryTree<Integer> b){
if(b.getLeftTree().getContent()!=null){
besucheInorder(b.getLeftTree());
}
System.out.println(b.getContent());
if(b.getRightTree().getContent()!=null){
besucheInorder(b.getRightTree());
}
}

private void besuchePostorder(BinaryTree<Integer> b){
if(b.getLeftTree().getContent()!=null){
besuchePostorder(b.getLeftTree());
}
if(b.getRightTree().getContent()!=null){
besuchePostorder(b.getRightTree());
}
System.out.println(b.getContent());
}

public void ausgabeAllgemein(){
System.out.println("Zahlenbaumverwaltung"+"\n"+"================================");
System.out.println("Preorder Traversierungsmethode:");
preorderAusgabe();
System.out.println("--------------------------------"+"\n"+"Inorder Traversierungsmethode:");
inorderAusgabe();
System.out.println("--------------------------------"+"\n"+"Postorder Traversierungsmethode:");
postorderAusgabe();
System.out.println("================================");
System.out.println("Anzahl der Knoten: "+ gibAnzahlKnoten(baum));
System.out.println("--------------------------------");
System.out.println("\n"+"\n"+"\n"+gibAnzahlBlaetter(baum));
}
}[/CODE]

Den Zähler „q" erstelle ich im Konstruktor.

Also bei der rekursiven Suche überprüfe ich, ob der linke Teilbaum meiner Node vorhanden ist. Wenn ja, dann rufe ich meine Suchmethode rekursiv mit dem linken Teilbaum als Node auf. Als nächstes überprüfe ich, ob der rechte Teilbaum meiner ursprünglichen Node vorhanden ist. Ist das der Fall, rufe ich meine Suchmethode rekursiv mit dem rechten Teilbaum als Node auf.
Im folgenden überprüfe ich, ob die aktuelle Node weder einen linken, noch rechten Teilbaum hat. Wenn das der Fall ist, erhöhe ich meinen Zähler um 1.

 

[KonradN]

Wenn ja, dann rufe ich meine Suchmethode rekursiv mit dem linken Teilbaum als Node auf.

Was gibt die Methode denn zurück? Und so ein Zähler ist, wie schon gesagt, schlicht falsch und unnötig.

Es sollte Dir immer zu denken geben, wenn du eine Methode aufrufen, ohne deren Rückgabe auszuwerten. Das ist ein Zeichen, dass etwas falsch ist.

 

[Valke001]

Momentan gibt sie nur den Wert von dem erstellten Zähler wieder. Aber wie kann ich sonst die Anzahl meiner Blätter ermitteln?

 

[KonradN]

Wie viele Blätter hat ein Teilbaum, wenn es rechts und/oder links Teilbäume gibt?
Kannst du das irgendwie ausdrücken?

Du schreibst ja gerade eine Methode, die die Anzahl der Blätter eines Teilbaums ermitteln soll.

Und Rekursion ist, wenn du etwas hast wie f(x) = f(x-1) + f(x2) für x>2 (als Teil eines Ausdruckes, der für x=1 und x=2 andere Dinge vorgibt.)

 

[mihe7]

Momentan gibt sie nur den Wert von dem erstellten Zähler wieder. Aber wie kann ich sonst die Anzahl meiner Blätter ermitteln?

Vergiss mal einen Moment, dass am Ende Code rauskommen soll. Es gibt keinen Zähler, die Sache ist sehr viel einfacher.

• Ein Baum, der nur aus der Wurzel X besteht, hat wie viele Blätter?
• Jetzt hängen wir an X einen linken und/oder einen rechten Teilbaum an. Wie viele Blätter hat dann der Baum mit der Wurzel X?

Mal es Dir ggf. auf, das hilft.

 

[fhoffmann]

die Sache ist sehr viel einfacher.

Ich interpretiere die Äußerung von @mihe7 so:
Ein Baum, der eine Wurzel hat, hat zunächst einmal (mindestens) ein Blatt.
(Ein Baum ohne Wurzel - wenn es so etwas überhapt geben darf - hat natürlich kein Blatt.)
Jeder Knoten - inclusive der Wurzel - mit zwei Nachfolgern fügt dem Baum ein weiteres Blatt zu.

 

[mihe7]

Das steckt noch zu viel Hirnschmalz drin. Das geht viel einfacher, ohne sich großartig Gedanken machen zu müssen.