C-Programmierung
Traversierung Des Gesamtbaums
← Baumknoten Löschen | ● | Balancierte Bäume →
Wandert man an den Ă„sten des Baums links herunter und rechts wieder herauf, so besucht man alle Knoten in rekursiver Art und Weise.
.
/ \
/ 5 \
/ / \ \
/ / _ \ \
/ / / \ \ \
/ 3 / | 8 \
/ / / / / \ \
/ / / / / _ \ \
/ 1 / / 7 / \ 9 \
\__/ \__/ \__/
Rekursive Traversierung des Gesamtbaums:
void traverse_tree(node_ptr ptr)
{
if (ptr)
{
traverse_tree(ptr->left);
traverse_tree(ptr->right);
}
}
{
if (ptr)
{
traverse_tree(ptr->left);
traverse_tree(ptr->right);
}
}
Gibt man währenddessen jeden Knoten aus, wenn man den linken Teilbaum schon besucht hat, den rechten aber noch nicht, so erhält man eine sortierte Ausgabe des binären Baums (rekursive tree walk).
void output_tree(node_ptr ptr)
{
if (ptr)
{
output_tree(ptr->left);
output(ptr->element);
output_tree(ptr->right);
}
}
output_tree(root);
{
if (ptr)
{
output_tree(ptr->left);
output(ptr->element);
output_tree(ptr->right);
}
}
output_tree(root);
Dies ist auch unter dem Namen Tiefensuche bekannt.
Im Vergleich dazu gibt die Breitensuche zuerst alle Knoten einer Ebene aus.
Binäre Bäume bedürfen keiner expliziten Sortierung, da während der Tiefensuche dies implizit sichergestellt ist.
← Baumknoten Löschen | ● | Balancierte Bäume →