Breitensuche

[BK117]

Hallo,
wir sollen im Rahmen der Hausaufgaben die Methoden zur Breitensuche, Pre- , In- und Postorder für die Traversierung von Binärbäumen schreiben. (Ich kürze jetzt einfach mal Breitensuche mit BS ab )

Ich wollte das ganze Rekursiv, und nicht iterativ lösen, daher hier meine Post/Pre und Inorder Methoden:

	void preOrder(BinaryTree binTree){
		System.out.println(binTree.getObject());
		if(binTree.getLeftTree().getObject() != null){
			preOrder(binTree.getLeftTree());
		}
		if(binTree.getRightTree().getObject() != null){
			preOrder(binTree.getRightTree());
		}
	}
	
	void inOrder(BinaryTree binTree){
		if(binTree.getLeftTree().getObject() != null){
			inOrder(binTree.getLeftTree());
		}
		System.out.println(binTree.getObject());
		if(binTree.getRightTree().getObject() != null){
			inOrder(binTree.getRightTree());
		}
	}
	
	void postOrder(BinaryTree binTree){
		if(binTree.getLeftTree().getObject() != null){
			postOrder(binTree.getLeftTree());
		}
		if(binTree.getRightTree().getObject() != null){
			postOrder(binTree.getRightTree());
		}
		System.out.println(binTree.getObject());
	}

	void breitenSuch(BinaryTree binTree){
		System.out.println(binTree.getObject());
		//TODO	
	}

Die drei ersten waren rekursiv recht einfach, nur bei der BS stoße ich auf Probleme.
Wenn ich zuerst den Knoten ausgeben lasse (was bei der BS zwingend logisch ist), muss ich mit dem linken Teilbaum weiter machen. Also rufe ich erst den rekursiv auf, und dann den rechten. Das Problem ist ja, dass sich dann, bevor ich den rechte Baum aufrufe, der linke Teilbaum des linken Teilbaums wieder aufruft, und dann hätte ich ja wieder die PreOrder variante.
Wie bekomme ich das hin.
Ich weiß wie das eigentlich sein muss, und zwar Ebenenweise, aber ich bekomme die Implementierung in Java nicht auf die Reihe
Geht das rekursiv überhaupt so einfach? Wenn ja, womit fange ich am besten an? Ich habe ja nur die drei Methoden zum Suchen. (getObject, getLeftTree und getRightTree). Die anderen Methoden in der Klasse BinarySearch sind ja nur Konstruktroren, und die Setter der Variablen, die ich gerade als Getter genannt habe.

Danke,
Gruß Nico

 

[Flown]

Also auf jedenfall brauchst du für die Breitensuche eine Queue. Wenn du BFS (Breadth-first-search) eingibst, bekommst du genug Konzepte wie das auch rekursiv zu lösen ist.

 

[BK117]

Ok, danke. Das schaue ich mir mal an.

Gruß BK

 

[BK117]

Danke für den Tipp. Ich habe das jetzt so gelöst:

	void breitenSuch(BinaryTree binTree){
		System.out.println(binTree.getObject());
		if(binTree.getLeftTree().getObject() != null){
			queue.add(binTree.getLeftTree());
		}
		if(binTree.getRightTree().getObject() != null){
			queue.add(binTree.getRightTree());
		}
		if(!queue.isEmpty()){
			breitenSuch(queue.poll());
		}
	}