BinärTree, Knoten löschen

[Laren]

Hi,

Ich hab hier einen Binearbaum, der rekursiv läuft, aber ich hänge gerade etwas an der Löschmethode, ich weis einfach nicht, wie ich dies realiesieren könnte???:L
Muss ich den Baum einfach immer wieder neu zeichnen ohne den Knoten?

Viele Grüße

/**
 * Ein sortierter Binaerbaum
 */
package ueb14;

public class BinaerTree {

	private Knoten root;
	private StringComperator comperator = new StringComperator();
	private int anzahlKnoten;

	/**
	 * Hinzuefuegen von Objekten
	 * @param uebergabeObjekt
	 */
	public void add(Object uebergabeObjekt) {
		Knoten knoten = new Knoten(null, null, uebergabeObjekt);
		if (root == null)
		{
			root = knoten;
			anzahlKnoten++;
		}
			else
			addAbBestimmtenKnoten(root, knoten);

	}

	public void addAbBestimmtenKnoten(Knoten ausgewaehlterKnoten,Knoten uebergabeKnoten) {
		
		String ausgewaehlterKnotenString = (ausgewaehlterKnoten.toString());
		String uebergabeKnotenString = (uebergabeKnoten.toString());

		if (comperator.compare(ausgewaehlterKnotenString, uebergabeKnotenString) > 0)

		{
			if (ausgewaehlterKnoten.hatLinkenSohn()) {
				addAbBestimmtenKnoten(ausgewaehlterKnoten.getLinkerSohn(),
						uebergabeKnoten);
			}
			if (!ausgewaehlterKnoten.hatLinkenSohn()) {
				ausgewaehlterKnoten.setLinkerSohn(uebergabeKnoten);
				anzahlKnoten++;

			}
		}
		if (comperator.compare(ausgewaehlterKnotenString, uebergabeKnotenString) < 0)

		{
			if (ausgewaehlterKnoten.hatRechtenSohn()) {
				addAbBestimmtenKnoten(ausgewaehlterKnoten.getRechterSohn(),
						uebergabeKnoten);
			}
			if (!ausgewaehlterKnoten.hatRechtenSohn()) {
				ausgewaehlterKnoten.setRechterSohn(uebergabeKnoten);
				anzahlKnoten++;
			}

		}
		

	}

	public String toString() {
		if (root != null) {
			return toString(root);
		} else {
			return "<leerer Baum>";
		}
	}

	private String toString(Knoten knoten) {
		
		String ausgabe = "";

		if (knoten.getLinkerSohn() != null) {
			ausgabe = ausgabe+ toString(knoten.getLinkerSohn());
		}
		ausgabe += knoten.getInhalt() + "\n";
		if (knoten.getRechterSohn() != null) {
			ausgabe = ausgabe+ toString(knoten.getRechterSohn());
		}

		return ausgabe;
	}

	/**
	 * @return the anzahlKnoten
	 */
	public int getAnzahlKnoten() {
		return anzahlKnoten;
	}

	/**
	 * @return the root
	 */
	public Knoten getRoot() {
		return root;
	}
	
	

}

 

[XHelp]

ich weis einfach nicht, wie ich dies realiesieren könnte?

Was hast du denn bis jetzt?

Muss ich den Baum einfach immer wieder neu zeichnen ohne den Knoten?

In dem Code steht auch nix von Zeichnen :bahnhof: was meinst du damit?

 

[Laren]

Was hast du denn bis jetzt?

Ich kann nur den Baum mit Knoten füllen (und total leer machen), aber ich hänge bei den einzelnen Knoten löschen.

In dem Code steht auch nix von Zeichnen was meinst du damit?

Das ich es irgentwie schaffe, das der Baum neu gezeichnet(so nannten wir es auf der Uni, also neu nochmal neu erstellt wird) , nur ohne den alten Knoten.

Ich weis echt nicht, wie ich es anstellen soll

 

[XHelp]

Willst du einen einzigen Knoten löschen, so dass der dranhängende Teilbaum "nachrutscht" oder soll der Teilbaum mitgelöscht werden?
Beim 2. Fall sollte es wohl reichen den entsprechenden Node auf null zu setzen, im 1. Fall ist es wohl am einfachsten den Node auf null zu setzen und alles was noch dran hängt erneut zum Baum hinzuzufügen.

 

[Laren]

Habe es jetzt so realiesiert, dass ich einfach die Referenzen der Knoten änderer, das klappt aber noch nicht so gut, was mache ich falsch?

private void del(Knoten knoten) {

		// Keine Soehne, also Blatt
		if (!knoten.hatLinkenSohn() && !knoten.hatRechtenSohn()) {
			if (knoten.getVater().getLinkerSohn() == knoten) {
				knoten.getVater().setLinkerSohn(null);
				knoten = null;
			} else if (knoten.getVater().getRechterSohn() == knoten) {
				knoten.getVater().setRechterSohn(null);
				knoten = null;
			}
		}
		// nur linker Sohn
		else if (knoten.hatLinkenSohn() && !knoten.hatRechtenSohn()) {
			if (knoten.getVater().getLinkerSohn() == knoten) {
				knoten.getVater().setLinkerSohn(knoten.getLinkerSohn());
				knoten = null;
			} else if (knoten.getVater().getRechterSohn() == knoten) {
				knoten.getVater().setRechterSohn(knoten.getRechterSohn());
				knoten = null;
			}
		}
		// nur rechter Sohn
		else if (!knoten.hatLinkenSohn() && knoten.hatRechtenSohn()) {
			if (knoten.getVater().getLinkerSohn() == knoten) {
				knoten.getVater().setLinkerSohn(knoten.getLinkerSohn());
				knoten = null;
			}
			if (knoten.getVater().getRechterSohn() == knoten) {
				knoten.getVater().setRechterSohn(knoten.getRechterSohn());
				knoten = null;
			}
		}
		// rechter und linker Sohn
		else if (knoten.hatLinkenSohn() && knoten.hatRechtenSohn()) {
			if (knoten.getVater().getLinkerSohn() == knoten) {
				knoten.getVater().setLinkerSohn(knoten.getLinkerSohn());
				knoten.getVater().getLinkerSohn().setRechterSohn(knoten.getRechterSohn());
				knoten = null;
			}
			if (knoten.getVater().getRechterSohn() == knoten) {
				knoten.getVater().setRechterSohn(knoten.getRechterSohn());
				knoten.getVater().getRechterSohn().setLinkerSohn(knoten.getLinkerSohn());
				knoten = null;
			}
		}
	}

 

[XHelp]

Was heißt denn "nicht so gut"??
Da fehlt aber mindestens eine Schleife, die den gewünschten Knoten in dem Baum sucht und bei dem Vorgänger davon die Referenz ändert.

 

[Laren]

sorry, das hab ich ganz vergessen, oben drüber ist natürlich noch diese Methode:

	public void del(Object uebergabe) {
		Knoten knoten = new Knoten(null, null, null, uebergabe);
		this.del(findKnoten(knoten));
	}

das findKnoten usw funktioniert alles, es geht mir jetzt nur darum, wie ich die Referenzen legen muss, wenn ein Knoten 1 oder 2 Kinder hat. Die Blätter zu löschen funktioniert.