Benutzer-Werkzeuge
se:algorithmendatenstrukturen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:algorithmendatenstrukturen [2009-01-14 18:03] stefan |
se:algorithmendatenstrukturen [2009-01-15 17:33] stefan |
||
|---|---|---|---|
| Zeile 43: | Zeile 43: | ||
| * bei schließender Klammer den obersten Operator ausgeben | * bei schließender Klammer den obersten Operator ausgeben | ||
| - | ===== Binärbäume ===== | + | ===== Bäume ===== |
| * Ein Baum ist eine nicht-leere Menge von Knoten und Kanten, die gewisse Bedingungen erfüllen. | * Ein Baum ist eine nicht-leere Menge von Knoten und Kanten, die gewisse Bedingungen erfüllen. | ||
| * Ein Knoten ist ein Objekt, das einen Namen haben und weitere Informationen beinhalten kann. | * Ein Knoten ist ein Objekt, das einen Namen haben und weitere Informationen beinhalten kann. | ||
| Zeile 58: | Zeile 58: | ||
| * Geordnete Bäume sind Bäume, bei denen die Reihenfolge der direkten Nachfolger bei jedem Knoten festgelegt ist. Ist diese Reihenfolge nicht fest vorgeschrieben, spricht man von ungeordneten Bäumen. | * Geordnete Bäume sind Bäume, bei denen die Reihenfolge der direkten Nachfolger bei jedem Knoten festgelegt ist. Ist diese Reihenfolge nicht fest vorgeschrieben, spricht man von ungeordneten Bäumen. | ||
| * Falls jeder Knoten nur eine bestimmte Anzahl n von direkten Nachfolgern haben darf, die in einer bestimmten Reihenfolge vorliegen müssen, spricht man von einem n-ären Baum. | * Falls jeder Knoten nur eine bestimmte Anzahl n von direkten Nachfolgern haben darf, die in einer bestimmten Reihenfolge vorliegen müssen, spricht man von einem n-ären Baum. | ||
| + | |||
| + | ==== Binärbäume ==== | ||
| * Der einfachste Typ eines n-ären Baums ist der binäre Baum, für den Folgendes gilt: | * Der einfachste Typ eines n-ären Baums ist der binäre Baum, für den Folgendes gilt: | ||
| * Es ist ein geordneter Baum mit zwei Typen von Knoten: inneren und äußeren Knoten. Innere Knoten haben immer maximal zwei direkte geordnete Nachfolger, die man auch als linker und rechter Nachfolger bezeichnet. Äußere Knoten sind Knoten ohne Nachfolger. | * Es ist ein geordneter Baum mit zwei Typen von Knoten: inneren und äußeren Knoten. Innere Knoten haben immer maximal zwei direkte geordnete Nachfolger, die man auch als linker und rechter Nachfolger bezeichnet. Äußere Knoten sind Knoten ohne Nachfolger. | ||
| Zeile 70: | Zeile 72: | ||
| * Binärbäume vereinen die Vorteile von Arrays (schneller Zugriff auf ein Element) mit den Vorteilen von Listen (leichtes Einfügen/Löschen eines Elements). | * Binärbäume vereinen die Vorteile von Arrays (schneller Zugriff auf ein Element) mit den Vorteilen von Listen (leichtes Einfügen/Löschen eines Elements). | ||
| * Sie lassen sich am Besten mittels Rekursion verwalten. | * Sie lassen sich am Besten mittels Rekursion verwalten. | ||
| + | * nicht-binäre Bäume können einfach als binäre Bäume implementiert werden, indem jeder Knoten zwei Zeiger bekommt: einen auf sein erstes Kind (verkettete Liste aller Kinder) und einen auf seinen nächsten Geschwisterknoten | ||
| + | * in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log<sub>2</sub>(n+1) | ||
| + | * bei einem balancierten Binärbaum sind somit maximal log<sub>2</sub>(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu finden | ||
| + | |||
| + | ==== Traversierung ==== | ||
| + | * Preorder: Bearbeite zuerst die Wurzel, dann bearbeite den vollständigen linken Unterbaum und anschließend den vollständigen rechten Unterbaum zu dieser Wurzel. | ||
| + | * Inorder: Bearbeite zuerst den vollständigen linken Unterbaum, dann die Wurzel und anschließend den vollständigen rechten Unterbaum zu dieser Wurzel. | ||
| + | * Postorder: Bearbeite zuerst den vollständigen linken Unterbaum, dann den vollständigen rechten Unterbaum und schließlich zuletzt die Wurzel zu diesen Unterbäumen. | ||
| + | * Levelorder: Bei dieser Art der Traversierung wird von oben nach unten jede einzelne Ebene des binären Baums durchlaufen, wobei die einzelnen Ebenen von links nach rechts traversiert werden. | ||
| ===== Lineare Rekursion ===== | ===== Lineare Rekursion ===== | ||
| Zeile 87: | Zeile 98: | ||
| ===== ToDo ===== | ===== ToDo ===== | ||
| * Wichtige Bereiche im Skript mit Klebi kennzeichnen | * Wichtige Bereiche im Skript mit Klebi kennzeichnen | ||
| - | + | * Traversierung von Binärbäumen implementieren | |
se/algorithmendatenstrukturen.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
