Binaerbaum, Ebenen auf Vollstaendigkeit pruefen

[Palme4001]

Hallo,

Dies ist mein erster Beitrag, ich entschuldige mich im Vorraus dafür, wenn ich hier nicht alles richtig verfasst habe.

Ich habe einen binaeren Baum, jeder Knoten speichert einfach einen Integer-Wert, und seine jeweilige Ebene, auf der er sich befindet. Dieser Wert der Ebene wird dem Knoten direkt beim sortierten Einfuegen in den Baum zugewiesen, die Wurzel is 0.

Jetzt möchte ich die einzelnen Ebenen auf ihre Vollstaendigkeit ueberpruefen. Ich fuehre nun aus einer Testklasse den Boolen: isWellStocked(Ast a, int searchedLevel) aus.

public boolean isWellStocked(Ast b, int searchedLevel){
		if(b.ebene == searchedLevel){
			counter++;
			if(counter == Math.pow(2, searchedLevel)) return true;
		}
			
		if(b.links != null){
			isWellStocked(b.links, searchedLevel);
		}
		if(b.rechts != null){
			isWellStocked(b.rechts, searchedLevel);
		}
		
		return false; // Hier kommt er ja oefters lang, da er durch den Baum durchlaeuft, und returnt dann einfach false
	}

Die Varaible counter ist global, und zaehlt um einen hoch, wenn ein Knoten mit der gesuchten Ebene gefunden wurde.
Wenn dieser counter also == 2^(die durchsuchte Ebene) ist, soll er true returnen, da dann die Eben voll waere.
Das ganze klappt auch, allerding nur, wenn wir die Wurzel auf Vollstaendigkeit ueberpruefen, was keinen Sinn ergiebt, aber dann muss er nicht durch den Baum traversieren, und kommt somit auch nicht an return false "vorbei".

Meine Frage: Wie kann ich es vermeiden, dass er immer false returnt ? In einer Methode hatte ich das hinbekommen, weil ich da dann eifach eine globale Variable auf true gesetzt habe. Doch jetzt wollte ich es in einem boolean lösen.

Ich wuerde mich ueber eine Antwort freuen


Hinzuzufuegen waere noch die Klasse Ast:

package Paket;

public class Ast {
	
	int zahl;
	int ebene;
	Ast rechts;
	Ast links;
	
	public Ast(int zahl, int ebene){
		this.zahl = zahl;
		this.ebene = ebene;
	}
	public Ast(){
		
	}

}

Und die Testklasse:

package Paket;

public class Gaertner {
	
	public static void main(String[]i){
		Baum b1 = new Baum();
		b1.sortiertAnhaengen(20, b1.wurzel,0);
		b1.sortiertAnhaengen(200, b1.wurzel,0);
		b1.sortiertAnhaengen(300, b1.wurzel,0);
		b1.sortiertAnhaengen(250, b1.wurzel,0);

		b1.inorder(b1.wurzel);
		System.out.println(b1.getEbenen(b1.wurzel));
		
		System.out.println(b1.isWellStocked(b1.wurzel, 2));
	}

}

 

[sheel]

Hi und Willkommen bei tutorials.de,

in der Methode eine eine weiterreichende Variable (counter) zu verwenden,
die aber nur für die Methode da ist, ist nicht wirklich schön.

Meine Frage: Wie kann ich es vermeiden, dass er immer false returnt ? In einer Methode hatte ich das hinbekommen, weil ich da dann eifach eine globale Variable auf true gesetzt habe. Doch jetzt wollte ich es in einem boolean lösen.

Du meinst, mit einer Methode mit einem int-Returnwert gehts (weil du da die Knotenzahl
returnen kannst), aber jetzt willst bool returnen (damit man sich außen beim Aufrufen
gleich ja/nein abholen kann)?

Wie wäre es dann, eine Methode countChildren oder so zu machen, die ein int zurückgibt
(wieder rekursiv usw.usw), die kann auch protected oder private sein,
damit sie von außen nicht verwendbar ist;
und dazu das isWellStocked, das nur anhand der Zahl von countChildren prüft,
ob der Baum ausreichend voll ist?

PS. Statt

Math.pow(2, searchedLevel)

kann man auch einfach

1<<searchedLevel

verwenden.

 

[Palme4001]

Hallo,


Ich habe jetzt eine Methode in der Klasse Baum :

 protected int countChildren(Ast a, int searchedLevel)

, welche mir die Kinder auf der vorgegebenen Ebene returnt.

protected int countChildren(Ast a, int searchedLevel){	
		if(a.links != null){
			countChildren(a.links, searchedLevel);
		}
		if(a.rechts != null){
			countChildren(a.rechts, searchedLevel);
		}
		if(a.ebene == searchedLevel){
			counter++;
		}
		return counter;
	}

Die Methode: boolean isWellStocked(int searchedLevel, int children){}
sieht jetzt so aus:

protected boolean isWellStocked(int searchedLevel, int children){
		if(children == 1<<searchedLevel) return true; 
		return false;
	}

Aus der Testklasse rufe ich nun

b1.isWellStocked(2, b1.countChildren(b1.wurzel, 2))

auf, und es klappt !

Vielen Dank für diese schnelle Antwort !