Java Rekursion Binärbaum Problem

[TheRepatriate]

Hallo zusammen,

ich bin gerade dabei für eine Programmierung Klausur zu lernen und prinzipiell verstehe ich Rekursion, aber eine Aufgabe bezüglich eines Binärbaums bereitet mir Kopfzerbrechen.
Aufgabe :

4. Schreiben Sie eine Methode, die die Anzahl der Knoten, die höchstens eine
Entfernung von einem übergebenen i zum nächstgelegenen Blatt haben
errechnet.

Die struktur vom baum ist halt typisch binärbaum:
-class Suchbaum {Knoten wurzel; ...}
-class Knoten {Knoten linker; Knoten rechter; int zahl;....}

Wäre nett wenn mir da jemand ein paar Tipps geben kann, wie man an so eine Aufgabe rangeht.
Vielen Dank im Voraus!!!

 

[1668mib]

Naja bei Rekursion immer das Problem so "einfach" halten wie möglich

soll heißen:
Du gehst vom Wurzelknoten aus. Die Zahl der Knoten, die erreichbar sind sind ja die erreichbaren Knoten im linken plus die erreichbaren Knoten im rechten Kind.
Und das schöne ist: Die Zahl der im linken (rechten) Knoten erreichbaren Knoten lässt sich genau gleich ermitteln - mit diesem als Wurzel aber jetzt halt nur noch mit der Entfernung i-1.

 

[Halox]

Hi,

ich denke, du kannst dafür zwei geschachtelte Rekursionen einsetzen. Zumindest ist das eine Möglichkeit - wenn auch bestimmt nicht die performanteste.

Idee:

äußere Rekursion: Tiefensuche (pre-order-Traversierung)

innere Rekursion: für jeden besuchten Knoten startest du wieder eine Rekursion (wieder Tiefensuche) und übergibst dabei die Rekursionstiefe. Wenn du auf ein Blatt triffst, bevor die Rekursionstiefe das vorgegebene i übersteigt, zählt der Knoten zum Ergebnis, sonst nicht.

als Java-Beispielcode (schnell runtergetippt - lauffähig aber nicht hübsch ;-) )

import java.util.ArrayList;

public class BinaerBaum {

	
	static ArrayList<Knoten> gefundeneKnoten = new ArrayList<BinaerBaum.Knoten>();
	
	public static void main(String[] args) {
		Suchbaum b = new Suchbaum();
		
		Knoten k1 = new Knoten("1");
		Knoten k2 = new Knoten("2");
		Knoten k3 = new Knoten("3");
		Knoten k4 = new Knoten("4");
		Knoten k5 = new Knoten("5");
		Knoten k6 = new Knoten("6");
		Knoten k7 = new Knoten("7");
		Knoten k8 = new Knoten("8");
		Knoten k9 = new Knoten("9");
		
		b.wurzel = k1;
		k1.links = k2;
		k2.links = k3;
		k2.rechts = k4;
		k4.links = k5;
		k5.rechts = k6;
		k6.links = k7;
		k1.rechts = k8;
		k8.rechts = k9;

		/*
		 *              +---------1---------+
		 *              |                   |
		 *      +-------2-------+           8---------+
		 *      3               |                     |
		 *                  +---4                     9
		 *                  |
		 *                  5---+
		 *                      |
		 *                    +-6
		 *                    |
		 *                    7
		 */
		
		durchlaufeBaum(b.wurzel);
		
		System.out.println("Gefunden Knoten: "+gefundeneKnoten.size());
		
	}
	
	private static void durchlaufeBaum(Knoten k) {
		// äußere Rekursion (pre-order bzw. depth-first search) 
		
		// der dritte Parameter bei dem folgenden Aufruf ist das vorgegebene "i"!!		
		ermitteleEntfernungZumBlatt(k, 0, 2, k);
		if (k.links != null)
			durchlaufeBaum(k.links);
		if (k.rechts != null)
			durchlaufeBaum(k.rechts);
	}
	
	
	private static void ermitteleEntfernungZumBlatt(Knoten k, int rekursionsTiefe, int maxEntfernung, Knoten aktuellUntersuchterKnoten) {
		// innere Rekursion  wieder pre-order bzw. depth-first search)
		if (gefundeneKnoten.contains(aktuellUntersuchterKnoten))
			// Untersuchung innere (Rekursion) abbrechen, wenn ein Blatt für diesen Knoten gefunden wurde!
			return;
		if (k.links == null && k.rechts == null) {
			// Blatt
			gefundeneKnoten.add(aktuellUntersuchterKnoten);
		} else {
			// Knoten
			if (rekursionsTiefe < maxEntfernung) {		
				if (k.links != null)
					ermitteleEntfernungZumBlatt(k.links, rekursionsTiefe+1, maxEntfernung, aktuellUntersuchterKnoten);
				if (k.rechts != null)
					ermitteleEntfernungZumBlatt(k.rechts, rekursionsTiefe+1, maxEntfernung, aktuellUntersuchterKnoten);
			}			
		}
		
	}
	
	static class Suchbaum {
		Knoten wurzel;
	}
	
	static class Knoten {
		Knoten links;
		Knoten rechts;
		String wert;
		
		public Knoten(String w) {
			wert = w;
		}
	}
	
}

Ich hoffe, ich hab mich verständlich ausgedrückt...

Grüße,
Halox

 

[TheRepatriate]

super, vielen Danke für die Lösung!

 

[daemon777]

Vielleicht hab ich das Problem jetzt irgendwie falsch verstanden? Aber man bekommt einen Binärbaum, einen Knoten von dem man starten soll und eine Variable i die angibt wie tief die Rekursion gehen soll. Oder soll für alle Knoten ein solcher Wert berechnet werden?

Zählen nur Children oder auch Parents oder "Geschwister" mit in das Ergebnis?