Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
se:algorithmendatenstrukturen [2009-01-14 18:03] stefan |
se:algorithmendatenstrukturen [2009-01-17 14: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 | ||
- | + | * <del>Umwandlung Postfix/Infix</del> | |
+ | * <del>Lineare Rekursion</del> | ||
+ | * <del>Binärbäume</del> | ||
+ | * <del>Traversierung von Binärbäumen implementieren </del> | ||
+ | * Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.) | ||
+ | * Codeoptimierung | ||
+ | * Arrays mit Quicksort sortieren (C: qsort) | ||
+ | * Heapsort, Countingsort, Radixsort | ||
+ | * Backtracking (Was gibt vorgegebenes Programm aus?) |