Fragen zum Binärbaum

[Palmosun]

Hallo,
ich bearbeite gerade ein paar Aufgaben zum Thema Binärbaume.

Eine Frage laute, dass man die Anzahl der Knoten ermitteln soll.
Zählt unter Knoten auch die Wurzel und die Blätter?
Ist mein Code soweit richtig?

public int bestimmeAnzahlKnoten(Knoten Teilbaum)
    {
        int anz = 1;
        
        if(Teilbaum.getKnotenLinks() != null)
        {
            anz += bestimmeAnzahlKnoten(Teilbaum.getKnotenLinks());
        }
        if(Teilbaum.getKnotenRechts()!= null)
        {
            anz += bestimmeAnzahlKnoten(Teilbaum.getKnotenRechts());
        }
    	
    	return anz;
}

Bei der nächsten Frage soll man die maximale Pfadlänge ermitteln.
Ich würde den Baum jetzt wieder rekursiv durchlaufen nur wie ermittel ich den längsten Pfad?


Und meine letzte Frage ist, wenn ich die Anzahl der Blätter bestimmte und mein Binärbaum besteht nur aus der Wurzel. Ist die Wurzel dann auch ein Blatt?

Schonmal danke für eure Antworten

Palmosun

 

[freak4fun]

Jeder Knoten ist ein Knoen, egal ob Blatt, Knoten, oder Wurzelknoten.

Die max. Tiefe erhälst du wenn du die Tiefe aus dem rechten und dem linken Baum ermittelst und zur größeren eins addierst und das zurückgibst.

Blätter haben keine Unterknoten.

Viel Erfolg!

 

[Palmosun]

Danke für die gute Antwort, hat mir sehr geholfen.

Kann man das ganze noch etwas kürzer/besser schreiben?

    public int bestimmeMaximalePfadlaenge(Knoten Teilbaum)
    {
    	int tiefeLinks = 1;
    	int tiefeRechts = 1;
        int hoehe = 0;
        
        if(Teilbaum.getKnotenLinks() != null)
        {
            tiefeLinks = 1+  bestimmeMaximalePfadlaenge(Teilbaum.getKnotenLinks());
        }
        if(Teilbaum.getKnotenRechts() != null)
        {
            tiefeRechts = 1+ bestimmeMaximalePfadlaenge(Teilbaum.getKnotenRechts());
        }
        
        if(tiefeRechts > tiefeLinks)
        {
            hoehe = tiefeRechts;
        }
        else if( tiefeRechts <= tiefeLinks)
        {
            hoehe = tiefeLinks;
        }
 
    	return hoehe;
    }

 

[SlaterB]

    public int maxPath(Knoten k)
    {
    	int tiefeLinks = 0;
    	int tiefeRechts = 0;
        
        if(k.getLeft() != null)
        {
            tiefeLinks = maxPath(k.getLeft());
        }
        if(k.getRight() != null)
        {
            tiefeRechts = maxPath(k.getRight());
        }
        return Math.max(tiefeLinks,tiefeRechts)+1;
    }

Variablen klein schreiben!

    public int maxPath(Knoten k)
    {
        if (k == null) {
             return 0;
        }

        return Math.max(maxPath(k.getLeft()),maxPath(k.getRight()))+1;
    }