PI (Fach) / Bäume: Algorithmen (Lektion)
In dieser Lektion befinden sich 11 Karteikarten
Bäume: Algorithmen
Diese Lektion wurde von blace erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
- Auf welche Arten kann ein Binärbaum traversiert werden? Ein Binärbaum kann mittels Präorder Postorder Inorder Levelorder travesiert werden.
- Erkläre / implementiere die Traversierung eines Binärbaums in Präorder. Bei der Präorder werden in einem Baum erst die Knoten und dann die Kindknoten durchlaufen. public class Tree<T> {...void preorder(final Node<T> n, final NodeAction<T> a) {if (n != null) {a.action(n);preorder(n.left, a);preorder(n.right, a);}}...}
- Erkläre / implementiere die Traversierung eines Binärbaums in Postrder. Bei einer travesierung mittels Postorder werden zuerst die Kindknoten und dann die Knoten durchlaufen. public class Tree<T> {...void postorder(final Node<T> n, final NodeAction<T> a) {if (n != null) {postorder(n.left, a);postorder(n.right, a);a.action(n);}}...}
- Erkläre / implementiere die Traversierung eines Binärbaums in Inorder. Die Inorder fängt bei dem linken Kindknoten an geht dann zum Knoten und dann zum rechten kindknoten. void inorder(final Node<T> n, final NodeAction<T> a) {if (n != null) {inorder(n.left, a);a.action(n);inorder(n.right, a);}}
- Erkläre / implementiere die Traversierung eines Binärbaums in Levelorder Die Levelorder durchläuft den Baum bei jeder Ebene von Links nach rechts mittels einer Warteschlange. void levelorder(Node<T> n, final NodeAction<T> a) {Queue<Node<T>> q = new LinkedList<>();q.add(n);while (!q.isEmpty()) {n = q.poll();if (n != null) {a.action(n);q.add(n.left);q.add(n.right);}}}
- Erkläre / implementiere die Traversierung eines Binärbaums in Präorder ohne Rekursion Die Präorder ohne Rekursion arbeitet mit einem Stack void preorder2(Node<T> n, final NodeAction<T> a) {Stack<Node<T>> s = new Stack<>();s.push(n);while (!s.empty()) {n = s.pop();if (n != null) {a.action(n);s.push(n.right);s.push(n.left);}}}
- Erkläre / implementiere die Berechnung der Höhe eines Binärbaums. Die Höhe eines Binärbaumes rrechnet man durch die Anzahl der Ebenen minus 1
- Erkläre / implementiere die Suche in einem binären Suchbaum. Bei der Suche in einem Binärbaum gibt es zwei Fälle, Fall1 man ist bei einem inneren Knoten -Entweder findet man den gesuchten Wert -Oder der gesuchte Wert ist größer als der gefundene dann geht man rechts weiter -oder kleiner als der gefundene dann geht man nach links weiter Fall2 man ist bei einem Blattknoten, dann ist die Suche erfolglos public class SearchTree<T extends Comparable<T>> extends Tree<T> {public SearchTree(final Node<T> root) {super(root);}public T search(final T value) {return search(root, value);}private T search(final Node<T> node, final T value) {if (node==null) {return null;} else {final int c=value.compareTo(node.data);if (c<0) {return search(node.left,value);} else if (c>0) {return search(node.right,value);} else {return node.data;}}}
- Erkläre / implementiere die Suche in einem binären Blattsuchbaum. Bei einem Blattsuchbaum sind die Werte in den Blättern ud die inneren Knoten sind lediglich wegweiser mit zB. dem größten wert des linken Teilbaums. Auch hier gibt es die zwei Fälle inner Knoten oder Wurzel Fall1 -Wert größer rechts weiter -Wert kleiner oder gleich links weiter Fall2 Wert gefunden oder suche erfolglos
- Wie funktioniert das Einfügen in einen binären Suchbaum? Man wandelt ein Blatt in das einzufügende Element um, welches dann entweder selber ein Blatt ist, oder selber zwei Blätter als Kindknoten hat. man probiert erst dafür zu sorgen, dass ein Knoten mit nur einem Kindknoten hierdurch zwei bekommt.
- Wie funktioniert das Löschen aus einem binären Suchbaum? Beim löschen wird sich jeweils der Vorgänger gemerkt und dann gibt es verschiedene Fälle. Fall1 a der rechte Nachfolger ist leer, dann ersetzt der linke Nachfolger den entfernten Knoten. Fall1 b der linke Nachfolger ist leer, dann ersetzt der rechte Nachfolger den Knoten Fall 2a beide Nachfolger sind nicht leer, aber das linke Kind des rechten Kindes ist leer, dann hängt man den linken Nachfolger um und ersetzt dann den Knoten mit dem rechten Nachfolger fall 2b beide Nachfolger sind nicht leer, aber das rechte Kind vom linken Kind ist leer, dann hängt man den rechten Nachfolger um und ersetzt den Knoten mit dem Linken Nachfolger Fall 3 beide Nachfolger sind nicht leer und 2a und b greifen nicht, dann sucht man den Knoten mit dem nächstgrößerem Wert überschreibt diesen in den zu löschenden Knoten und löscht dann den gefundenen mit Umhängen möglicher Nachfolger