Lehrzeit

Schule & Informatik

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.

5 Kommentare

  1. Was für eine fiese kleine Aufgabe. Denke jetzt auch immer wieder darüber nach.

  2. Hallo Ingo, schönes Problem! Ich hab zwar wegen akutem Lehrprobenstress keine Zeit zu gar nichts, aber hab diese Seite hier entdeckt: http://billmill.org/pymag-trees/ Vielleicht inspiriert dich das ja zu weiteren Ansätzen!

    • 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

Deine E-Mail-Adresse wird nicht veröffentlicht.

*

© 2017 Lehrzeit

Theme von Anders NorénHoch ↑