Binärbaum implementieren - Datenstruktur

[babel22]

Guten Tag liebe Leute und Java-Experten.

Ich habe die Aufgabe einen Binärbaum zu implementieren.

Die Datenstruktur ist selbst zu implementieren und es durfen keine bereits vorhandenen Implementierungen
verwendet werden, welche das Problem lösen. Sie können selbst entscheiden, ob Sie das Interface GenericTree oder das Interface CharacterTree implementieren. CharacterTree spezialisiert lediglich GenericTree und soll als Erleichterung dienen. Die Implementierung von GenericTree bietet Ihnen jedoch die Moglichkeit Ihren Umgang mit Generics zu ¨ üben.

Zu implementierende Methoden
a) Höhe des Baums bestimmen.
b) Anzahl gespeicherte Elemente
c) Einfügen eines Wertes
d) Uberprüfen, ob ein Wert vorhanden ist
e) Loschen eines Wertes
f) Rucksetzen des Baumes
g) Ordnungen exportieren

So die Methoden zu implementieren sollte kein Problem für mich sein. Ich scheitere jedoch ganz am Anfang bei der Erzeugung des Binärbaumes. Die Datenstruktur eines Baumes besteht aus Knoten. Jeder Knoten hat max 2 Kanten die weggehen und eine Kante die ankommt (von oben). Die Wurzel hat keine Vorgänger.

So mein Problem ist folgende Klasse:

public class TreeFactoryImpl implements TreeFactory {

	@Override
	public GenericTree<Character> generateCharacterTree() {
		//Erzeugen (implementieren) Sie hier je nach Wunsch entweder einen GenericTree<Character> oder einen CharacterTree
		//return new GenericTreeImpl<Character>();
		//return new CharacterTreeImpl();
		return null;
	}
}

In dieser Klasse muss ich den Baum implementieren. Also einen leeren Baum. Bei den meisten Implementierungen wurden diese beiden Klassen verwendet. Node und BinTree. BinTree erzeugt mir einen Baum mit einer Wurzel welche null ist. Also einen leeren Baum. Danch würde ich mittels add weiter Knoten anbinden und die Methoden implementieren. Aber ich weiß nicht wie ich den Baum in der obigen Klasse implementieren kann, also die Datenstruktur entwickeln. Wie kann ich das realisieren? Wir können uns für eine Klasse, entweder GenericTree oder CharacterTree entscheiden, und die Methoden darin implementieren. Ich würde gerne CharacterTreeImpl implementieren. Aber ich habe keine Ahnung wie ich den Baum erzeugen kann. Kann ich mir diese beiden Klassen irgendwie zur Hilfe nehmen, um den Baum in der obigen Klasse zu implementieren?

public class Node {
 private Node left;
 private double value;
 private Node right;
 public Node(Node left, double value, Node right) {
 this.left = left;
 this.value = value;
 this.right = right;
 }

public class BinTree {
 private Node root;

 /** Erzeugt den leeren Baum */
 public BinTree() {
 root = null;
 }

Wir haben auch noch ein Sample bekommen wie das aussieht:

public class CharacterTreeSample {
	public static void main(String[] args) {
		doSomethingStrangeWithCharacters();

		howtoUseCompareTo();

		letsUseOurTreeFactory();

	}

	public static void letsUseOurTreeFactory() {	
		TreeFactory factory = new TreeFactoryImpl();	//Hier die eigene Implementierung angeben
		
		GenericTree<Character> tree = factory.generateCharacterTree();	//Wir holen uns unsere Tree-Instanz

		//Baum befüllen
		tree.addValue('a');
		tree.addValue('b');
		tree.addValue('z');
		tree.addValue('p');
		tree.addValue('k');
		tree.addValue('o');

Ich weiß nicht was hier passiert. Aus dem factory hole ich mir den Baum, aber ich weiß nicht wie ich Ihn darin implementieren soll.

Ich hoffe jemand hat einen Ansatz für mich, was ich hier machen kann.

Herzliche Grüße, Babel.

 

[Flown]

Ich versteh ja nicht woran es scheitert, aber:

- Auf jedenfall soll dein BinaryTree das Interface GenericTree/CharacterTree implementieren.
- Die Factory Implementierung sollte oben spezifizierten Tree zurückgeben (return new BinaryTree()
- Node Klasse sollte generisch gehalten werden:

public class Node<T> {
  private Node<T> left, right;
  private T data;
  // TODO: Konstruktor, Methoden zum Setzen/Holen der Daten
}

 

[babel22]

Vielen Dank für die Informationen, Flown. Also in TreeFactory kommt nichts rein, das ist also nur eine Information welches Interface ich implementiere.

Ich weiß aber immer noch nicht wie ich einen leeren Baum erzeugen kann. Wo ich nur einen Node habe (Wurzel), welche leer ist. Mit der Klasse Node kann ich mittels Konstruktor einen Knoten erstellen mit einen linken und rechen Nachfolger. Aber wie kann ich nur den ersten Knoten erzeugen der keine Vorgänger hat, also die Wurzel?

Gruß, Babel

 

[Flown]

Kommt immer darauf an. Entweder arbeitest du mit null oder mit einem leeren dummy node. Prüfen ob root leer(null oder dummy) ist musst du so oder so.

 

[babel22]

public class CharacterTreeImpl implements CharacterTree  {
	
	TreeFactory factory = new TreeFactoryImpl();
	private Knoten root = null;
	private Knoten left;
	private Knoten right;
	private int size;
//	Knoten wurzel = new Knoten(root);
	
	
	public int getHeight() {
		
		int l = 0, r = 0;
		if (left != null) l = left.getHeight() + 1;
		if (right != null) r = right.getHeight() + 1;
		return Math.max(l, r);
        
	}

warum kann ich bei left.getHeight()+1 die Methode nicht rekursiv aufrufen. left ist ein Knoten vom Typ Knoten. getLeft ist dort in dieser Klasse aber nicht drin. Wie kann ich das trotzdem so aufrufen?

Gruß

 

[Flown]

Warum schreibst du dir dann nicht einfach eine rekursive Methode?

Dein Baum ist ja nur die Fassade, die dir Logik auf deine Knoten-Datenstruktur anwendet.

public int getHeight() {
  return getHeight(root);
}
private int getHeight(Node root) {
  if(root  == null) return 0;
  else return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}