Kapitel 5: Datenstruktur Baum Flashcards
Definition Baum
Ein Baum ist eine Datenstruktur, die aus einer Menge von Knoten besteht. Jeder Knoten kann auf andere Knoten über Kanten (Referenzen) verweisen.
Was charakterisiert den Wurzel-Knoten ?
Der Erste Knoten im Baum
Was charakterisiert einen Blatt-Knoten ?
Ein Knoten ohne Nachfolger
Was gibt es neben Wurzel- und Blatt-Knoten noch für Knoten in Bäumen ?
Innere Knoten
Definition Niveau eines Knotens
Das Niveau eines Knotens ist die Länge des Pfades von der Wurzel bis zu diesem Knoten.
Definition Höhe eines Knotens
Die Höhe eines Knotens ist die Anzahl der Kanten bis zum tiefsten Blatt.
Formel Höhe eines Knotens
max aus(höhe links, höhe rechts)+1
Welche Höhe haben Blattknoten ?
0
Welche Höhe hat eine nullptr Referenz ?
-1
Definition Pfad
Ein Pfad in einem Baum ist eine Folge von verschiedenen Knoten, in der die aufeinander folgenden Knoten durch Kanten miteinander verbunden sind.
Zwei Grundlegende Eigenschaften eines Baumes
- zyklenfrei
- zusammenhängend
Wie heißt ein Baum mit 3 Knoten zu jedem Knoten ?
Ternärer Baum
BST: Wo steht der größere Vergleichsschlüssel zu einem Knoten, Links oder Rechts ?
Rechts
Eigenschaften BST
- Jeder Knoten hat bis zu 2 Nachfolfger
- Geordneter Baum durch Vergleichsschlüssel
- Zyklenfrei
- Zusammenhängend
Wie bestimmt sich der Linke Nachfolger zu einem gegebenen Index i in einer dynamisch verketteten Datenstruktur ? (BST)
2 * i +1
Wie bestimmt sich der Rechte Nachfolger zu einem gegebenen Index i in einer dynamisch verketteten Datenstruktur ? (BST)
2 * i +2
Welche Algorithmen zur Traversieren eines BST gibt es ?
- Inorder (LWR)
- Preorder (WLR)
- Postorder (LRW)
- Levelorder
Was ist die Inorder Traversierung ?
LWR
Was ist die Preorder Traversierung ?
WLR
Was ist die Postorder Traversierung ?
LRW
Mit welcher Traversierungsmethode wird der BST korrekt ausgegeben ?
Inorder (LWR)
Wo steht das Minimum im BST ?
ganz links (min hat left->nullptr)
Wo steht das Maximum im BST ?
ganz rechts (max hat right->nullptr)
Definition Vollständiger Baum
Beim vollständigen Binärbaum sind alle Knoten pro Niveau gefüllt außer im letzten Niveau. i.d.r gilt auch hier, dass die Knoten im letzten Niveau von links nach rechts gefüllt sind.
