Unsere Datenschutzrichtlinie wird in Kürze aktualisiert. Bitte sehen Sie sich die Vorschau an.

Grundlagen der Programmierung: Datenstrukturen

Baumstrukturen

Testen Sie unsere 2016 Kurse

10 Tage kostenlos!

Jetzt testen Alle Abonnements anzeigen
Bei einer Baumstruktur handelt es sich um eine logische Datenstruktur, bestehend aus Eltern- und Kindknoten, die in ihrer Verteilung einer Baumverästelung nachempfunden sind.

Transkript

Die Idee einer Baumstruktur besteht darin, dass wir eine Sammlung von Objekten haben. Für den Augenblick nennen wir sie Knoten. Sie haben Verbindungen, sie sind untereinander verlinkt. Okay. Wir haben schonmal von einer Datenstruktur gesprochen, die aus verschiedenen Knoten und Verlinkungen aufgebaut ist. Das war damals die verlinkte Liste. Aber in einer verlinkten Liste gehen wir immer von einem Knoten zu einem einzelnen speziellen nächsten Knoten und dort zum nächsten Knoten und zum nächsten Knoten. Selbst, wenn wir die Liste in beide Richtungen durchlaufen können, es bleibt immer eine fixe Abfolge. Wenn wir aber einen Baum haben, liegt der Unterschied darin, dass jeder Knoten mit einem, zwei oder noch mehr anderen Knoten verbunden sein kann. Und während wir das auf alle möglichen unsagbar verwirrenden Arten umsetzen könnten, ist doch die sinnvollste Art der Darstellung die einer Baumstruktur. Und es ist völlig unwichtig, wie dieses Objekt physischen Speicherplatz zugewiesen bekommt. Wir reden hier von einer logischen Datenstruktur und es geht nicht darum, ob sie zusammenhängenden Raum im RAM-Speicher beansprucht. Das ist bedeutungslos. Wenden wir uns also viel lieber diesen speziellen Begrifflichkeiten zu, die gemeinsam mit einer Baumstruktur kommen. Wie beim Verwenden einer verlinkten Liste gibt's einen speziellen Startknoten in der Baumstruktur. Der wird als Wurzelknoten bezeichnet. Und ja, wäre es ein wirklicher Baum, wären die Wurzeln eigentlich im Boden, aber wir stellen das genau andersrum dar. Dieser Wurzelknoten kann also seinerseits einen Wert beinhalten. Also ein beliebiges Objekt, das Sie gerade für sinnvoll erachten. Und was er noch enthält ist ein Link zu anderen Knoten. In C++ und Objective C werden diese Links sogenannte Pointers. In anderen Sprachen sind's Objektreferenzen. Die folgenden Knoten werden aber auf jeden Fall als Kindknoten bezeichnet. Die Wurzel ist das Elternteil der beiden Kindknoten und der Wurzelknoten seinerseits hat keinen Elternknoten. Aber jedes dieser Kindknoten kann selbst wieder Kindknoten haben. Die können auch wieder Kindknoten haben, und so weiter. Diese Idee von Eltern- und Kindknoten wird weitergeführt. Den ganzen Baum hinunter. Ein Knoten kann also ein Eltern- und ein Kindknoten zugleich sein. Dieser Knoten B zum Beispiel ist ein Kind des Wurzelknotens und selbst ein Elternknoten von diesen zwei unterhalb. Den zwei Kindknoten hier. Kindknoten mit denselben Eltern werden Geschwister genannt. Die Bezeichnung ist also nicht besonders ausgefallen. Es ist ziemlich verständlich. Decken wir noch ein paar Worte ab. Beziehen wir die Idee mit ein, dass wir einen Knoten ohne Kinder haben. Dieser wäre ein Blattknoten oder Leaf. Das sind jetzt genug Begriffe für den Baumteil. Nichts seltsames hier. Ich habe also hier eine Baumstruktur gezeichnet, die nicht mehr als zwei Kinder pro Eltern hat. Das wird als binärer Baum bezeichnet. Ein binärer Baum ist nur eine Baumstruktur mit maximal zwei Kindknoten. Für jeden anderen Knoten. Es müssen nicht zwei sein. Es kann auch einer sein, oder gar keiner, aber nie mehr als zwei. Wenn da irgendwo mehr als zwei Kindknoten pro Knoten sind, dann ist es kein binärer Baum mehr. Warum sollte das wichtig sein? Ganz einfach: Weil binäre Bäume oft verwendet werden, um eine ausgesprochen wunderbar durchsuchbare Struktur zu erzeugen, die nicht sehr überraschend binärer Suchbaum genannt wird oder im Englischen die Abkürzung 'BST' bekommt.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!