Fragen zur Implementierung eines Binärbaums

[SmittyJoe]

Ich habe die Aufgabe gehabt einen Binärbaum zu implementieren, bestehend aus einem Konstruktor sowie einer get- und insert-Methode. Der erste Versuch, obwohl ich im Theorieteil etwas hinke:

Klassendiagramm:

Implementierung:

public class BinaryTree {
	private Node root = null;

	private static class Node {
		private Integer key;
		private String value;
		private Node left = null;
		private Node right = null;

		public Node(Integer key, String value) {
			this.key = key;
			this.value = value;
		}
	}

	public boolean insert(Integer key, String value) {
		if (root == null) {
			root = new Node(key, value);
			return true;
		} else {
			return insert(root, key, value);
		}
	}

	private boolean insert(Node node, Integer key, String value) {
		if (key.equals(node.key)) {
			// falls doppelter Knoten
			return false;
		} else if (key < node.key) {
			if (node.left == null) {
				node.left = new Node(key, value);
				return true;
			} else {
				return insert(node.left, key, value);
			}
		} else if (key > node.key) {
			if (node.right == null) {
				node.right = new Node(key, value);
				return true;
			} else {
				return insert(node.right, key, value);
			}
		}
		return false;
	}

	public String get(Integer key) {
		return get(root, key); // Start der Suche bei der Wurzel
	}

	public String get(Node node, Integer key) {
		String result = null; 
                if (node.key.equals(key)) { 
			return node.value;
		} else {
			if (key < node.key && node.left != null) {
														
				result = get(node.left, key);
			} else if (key > node.key && node.right != null) { 
																

				result = get(node.right, key);
			}
		}

		return result;
	}

Beschreibung der Methoden:

get: Die get-Methode startet in einem bestimmten Knoten innerhalb des Baumes und überprüft ob der Knoten selbst das Kriterium erfüllt. Falls ja, gibt er den Inhalt des Knoten wieder, falls nicht durch die Baumstruktur durch auf der Suche eines passenden Knotens.

insert: Falls keine Wurzel im Baum exisiert, füge eine Wurzel ein. Anderenfalls füge einen Wurzelknoten einen Wert hinzu. Falls man einem Knoten einem Wert hinzufügt, beginnend von der Wurzel, wird geschaut, ob der Schlüsselwert(Key) kleiner,gleich oder größer als dem hinzugefügten Schlüsselwert ist. Bei gleicher Größe wird nicht weiter forgeführt, falls kleiner oder größer werden neue Knoten erzeugt.

1.Sollen die Klassen separiert werden(BinaryTree,Node,Nutzerklasse) oder geht diese Form in Ordnung?
2.Wie könnte eine Nutzerklasse(Main) aussehen, ich stelle mir vor ein Objekt zu erzeugen,dann mit Hilfe der insert-Methode die Elemente einzufügen und dann über die get-Methode wieder auszugeben.

Falls mir noch Fragen einfallen, stelle ich sie hier

Danke schonmal im Vorraus!

 

[DarXun]

Guten Abend SmittyJoe

zu 1.

Eigentlich hätte ich gesagt, dass es voll okay ist Node als innere Klasse zu definieren. Die get- und insert-Methoden, die mit 'Node' als Parameter arbeiten, sind jedoch beide public. Damit müsste Node also von "außen" verfügbar sein. Wenn die angesprochenen Methoden jedoch 'private' wären, dann gäbe es von außen keine Schnittstelle in der die Klasse 'Node' benötigt würde. Eine innere Klasse wäre in diesem Beispiel damit durchaus sinnvoll.

Eine 'main'-Methode (von dir als Nutzerklasse dargestellt) schreibe ich grundsätzlich in eine separate Klasse. Aus meinem Verständnis der Objektorientierung macht das nur Sinn, da jede Klasse nur eine Zuständigkeit haben sollte (mir fehlt hier gerade der Fachbegriff). Die 'BinaryTree'-Klasse sollte nur für die Verwaltung/Behandlung eines Binärbaums zuständig sein. Eine Main-Methode stellt dann ja eher eine Anwendung dieser Klasse dar und würde somit in einen anderen Zuständigkeitsbereich fallen.

zu 2.

Hört sich gut an. Würde ich vermutlich auch so machen.

Mit freundlichen Grüßen

DarXun

 

[SmittyJoe]

Danke für die Rückmeldung. Die Idee für die Main-Funktion wäre ungefähr so:

public class BinaryTreeUser {
	public static void main(String args[]) {
		BinaryTree bt = new BinaryTree();
...
}

Dann sowas wie

bt.insert(new Node(4,"String"));

wobei ich hier an zwei Punkten hänge, a) ob korrekter ein neuer Knoten zu erzeugen ist und b) warum bei Node hier Eclipse rumzickt. Vielleicht wegen der Sichtbarkeit in der BinaryTree-Klasse?!

Dann kommt in meinen Gedanken eine große Lücke, einzig und alleine die get-Methode in Form von

bt.get(1);

kommt mir in den Sinn. Mir kommen in den Sinn for-Schleifen,foreach-Schleife,etc. Aber kein komplettes Konstrukt. Würde sehr gerne meine BinaryTree-Klasse testen können, um zu schauen, ob es richtig arbeiten tut.

 

[DarXun]

b) warum bei Node hier Eclipse rumzickt. Vielleicht wegen der Sichtbarkeit in der BinaryTree-Klasse?!

Jop. Hatte ich auch in meinem Posting schon erwähnt.
Die Node brauchst du nach außen hin ja auch gar nicht.
Mach einfach mal die get- und insert-Methoden die als Parameter unter anderem ein Node-Objekt bekommen private.
Die Zugriffe funktionieren damit von außen komplett ohne Node. Ein Nutzer der BinaryTree-Klasse muss ja auch garnicht wissen wie du intern arbeitest, ihn interessiert nur, dass er einen Binärbaum verwenden kann.

Zum "testen":
Überlege dir mal welche verschiedenen Szenarien es gibt, wie dein Baum aufgebaut werden kann.
Ein Baum könnte z.B. nur aus einem Blatt bestehen.
Ein andere Baum könnte nur ein Zweig mit einem Blatt beinhalten (einmal links, einmal rechts).
Oder was passiert, wenn versuchst ein vorhandenen Key nochmal zu verwenden (es gibt also nicht nur Varianten deren Funktionsweise du über die Nutzung von 'get' überprüfen kannst).

Die korrekte Befüllung der verschiedenen Bäume lässt sich hier, soweit ich das sehe, anhand der get-Methode nur schlecht erkennen. Per 'get' kannst du nur sehen ob ein Element eingefügt wurde, nicht aber an welcher Stelle es eingefügt wurde. Hier würde es sich anbieten, sich erstmal einfach durchzudebuggen.
Wenn du deine get-Methode etwas anpasst, dann könntest du natürlich nicht nur den Wert des gesuchten Elements ausgeben lassen, sondern den gesamten Weg dahin. Damit würde sich sicherlich einiges mehr erkennen lassen.

Ich hoffe ich konnte helfen.

Mit freundlichen Grüßen

DarXun