Binärbaum 2

In den Ferien habe ich die Zeit gefunden, meine Implementierung eines binären Suchbaums mi grafischer Ausgabe mal ein bisschen zu optimieren. In meiner ersten Lösung gefiel mir nicht, dass der Baum, auch wenn er sehr leer ist, teilweise recht breit wurde.

Um das nun in den Griff zu bekommen, habe ich unterschiedliche Ansätze überdacht.

  1. IDEE: Der Baum wird von den Blättern aus aufgebaut und zwar beginnend bei den “tiefsten”. Dabei muss man wissen, wie viele Blätter es gibt, entsprechend habe ich die maximale Breite des Baums. Dann beginnt man mit den tiefsten, also den Blättern, die am Weitesten von der Wurzel entfernt sind und geht dann ebenenweise nach oben durch.
    KRITIK: Dieses ebenenweise Durchlaufen – entspricht einer Breitensuche – von unten machte mir aber am meisten Probleme. Auch, weil ich keine weiteren Detailinformationen über die Knoten, wie Ebenentiefe, speichern wollte.
  2. IDEE: Ich betrachte die Knoten als elektrische Ladung, die sich abstoßen. Jeder Knoten würde sich dann “selbstständig” eine energetisch günstige Position suchen.
    KRITIK: Ich müsste die Knoten in Threads packen, die sich wie die Partikel in einer Physik-Engine slebstständig und permanent anpassen. Das war mir dann doch zu viele des guten.
  3. und realisierte IDEE: Nur echte, innere Blätter mit zwei Kindern benötigen Platz. Alle Anderen hängen senkrecht untereinander. Ich schaue also, ob ich beim Zeichnen in einem inneren Knoten bin. Wenn ja, dann schau ich, wie viele weitere innere Knoten in den beiden Teilbäumen noch kommen. Kommt keiner, so brauchen die beiden Kinder nicht besonders weit auseinanderhängen. Andernfalls hängt die Weite der aktuellen Kinder von der Anzahl der in den beiden Teilbäumen vorkommenden inneren Knoten ab.
    KRITIK: Das Ganze funktioniert zu 95% gut. Nur bei sehr merkwürdigen Bäumen kann es mal zu Problemen kommen und die Knoten stehen über- und durcheinander (Knoten 37 beachten!).

Wer sonst noch eine schöne Implementierung oder Idee hat. Immer her damit. Es sollte allerdings so sein, dass ich das im Rahmen des Schulunterrichts von und mit den Schülern umsetzen lassen kann.

Nachträgliche Ergänzung: Quellcode: binarbaum7_grafik2.

Beteilige dich an der Unterhaltung

5 Kommentare

    1. Das sieht doch mal gut aus. Ich habe es zwar noch nicht gelesen, aber wenn es schon mit

      In the beginning, there was Knuth

      anfängt, kann es eigentlich nur gut werden.

Schreibe einen Kommentar

Schreibe einen Kommentar zu Ingo Antworten abbrechen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Durch die weitere Nutzung der Seite (Scrollen, Navigieren) stimmen Sie der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen