Höhe eines B-Baums

[roflolo77]

Hallo zusammen gibt es hier vll. einen Programmiergott der nen bisschen Zeit hat mir zu helfen? Es geht um einen B-Baum (nicht um einen Binärbaum)

Es gibt zwei Aufgabenteile:

Gibt die Höhe des Baums zurück, wenn sich alle Blätter auf demselben Niveau befinden, ansonsten -1.
Das Kriterium eines B-Baums, dass alle Blätter denselben Abstand zur Wurzel haben sollen ist also
erfüllt, wenn ein Wert >= 0 zurückgegeben wird.

public static int levelsOK(BNode node)
	{ 
		
	}

Hätte irgendjemand vielleicht einen Ansatz mit dem ich irgendwie weiterarbeiten könnte? Mir fällt leider momentan nichts ein. Wir sollen das ganze rekursiv umsetzen falls es hilfreich ist. Pseudocode würde mir auch schon völlig reichen hauptsache ich habe irgendwie einen Ansatz mit dem ich arbeiten kann :S

Vielen Dank schomma

 

[faetzminator]

Du rufst für alle Kinder diese Methode auf. Wenn alle den gleichen Wert zurückgeben, gibst du diesen + 1 zurück. Ansonsten -1. Wenn der Knoten keine Kinder hat, gibst du aber 1 (oder 0?) zurück.

 

[s4ke]

EDIT: Beitrag wegen Sinnlosigkeit gelöscht.

Aber sollte das nicht ähnlich zum BinBaum funktionieren? Einfach einmal die Höhe errechnen und dann rekursiv testen lassen, ob die Blätter genau diese Tiefe besitzen und wenn ja die Höhe zurückzugeben und wenn nicht dann einfach -1?

[Java]
//normale Kinder
public int hoehe(int hoehe)
{
return Math.max(rechterNachfolger.hoehe(hoehe + 1),linkerNachfolger.hoehe(hoehe + 1));
}

public boolean hoeheTesten(int hoeheSoll, int aktHoehe)
{
return (rechterNachfolger.hoeheTesten(hoeheSoll, aktHoehe+1)&&linkerNachfolger.hoeheTesten(hoeheSoll,aktHoehe+1));
}

//Abschluss
public int hoehe(int hoehe)
{
return hoehe - 1;
}

public boolean hoeheTesten(int hoeheSoll, int aktHoehe)
{
return hoeheSoll == (aktHoehe-1);
}

//Startmethode
public int hoeheTesten()
{
int hoehe = root.hoehe();
if(hoehe < 0)
{
return -1;
}
if(root.HoeheTesten(hoehe,0))
{
return hoehe;
}
else
{
return -1;
}
}
[/Java]

Das ist das ganze für den Binbaum was ich vorhin geschrieben hatte (und auch für einen selbst geschriebenen Aufbau eines Baums, den wir im Unterricht hatten und auch alles selbst umgesetzt haben) aber das kann ja im Grunde als Vorlage dienen.

 

[roflolo77]

WoW das ging ja echt superschnell mit den Antworten! Vielen Dank euch zweien! Somit hab ich eine gute Grundlage mit der ich versuchen kann etwas anständiges auf die Beine zu stellen, vielen Dank!