Binärer Suchbaum Knoten Zählen

[Aralgut]

public int nodesAtLevel(int n)
    {
        if(n <0 || isEmpty())
        {
            return 0;
        }
        else
        {
            if( n== 0)
            {
                if(!(leftChild.isEmpty()) && !(rightChild.isEmpty()))
                {
                    return 2;
                }
                if(!(leftChild.isEmpty()) || !(rightChild.isEmpty()))
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return leftChild.nodesAtLevel(n-1) +1 + rightChild.nodesAtLevel(n-1)+1;
            }
        }
    }

Kann da jmd kurz drüberschauen?

 

[httpdigest]

Das ist leider falsch. Du sollst nicht rekursiv alle Knoten oberhalb von Ebene `n` zählen, sondern nur die Knoten auf Ebene `n`.
Außerdem ist es wohl unnötig, das Vorhandensein des linken und rechten Kindknotens zu testen, wenn man auf Ebene 0 angelangt ist. Dann ist der Knoten, den man zählen soll, ja "this".

 

[httpdigest]

Ich hätt's so gelöst:

Spoiler

if (n < 0 || isEmpty())
  return 0;
return n == 0 ? 1 : leftChild.nodesAtLevel(n - 1) + rightChild.nodesAtLevel(n - 1);

 

[Aralgut]

Das ist leider falsch. Du sollst nicht rekursiv alle Knoten oberhalb von Ebene `n` zählen, sondern nur die Knoten auf Ebene `n`.
Außerdem ist es wohl unnötig, das Vorhandensein des linken und rechten Kindknotens zu testen, wenn man auf Ebene 0 angelangt ist. Dann ist der Knoten, den man zählen soll, ja "this".

 

[mihe7]

Wenn n == 0, dann befindest Du Dich in einem Wurzelknoten in der gesuchten Ebene. Dem entsprechend ist die Anzahl 1.

Wenn n > 0, dann befindest Du Dich nicht in der gesuchten Ebene. Die Anzahl ist somit zunächst 0. Hinzu kommen die Knoten auf Ebene n-1 des linken Teilbaums (sofern dieser existiert) als auch die Knoten auf Ebene n-1 des rechten Teilbaums (sofern dieser existiert).