Binärbaum-Traversierungen
Einen binären Suchbaum erzeugen und Preorder-, Inorder- oder Postorder-Traversierungen mit einer rekursiven C++-Funktion Schritt für Schritt durchgehen.
Alles wird in diesem Browser simuliert; nichts wird an einen Server gesendet.
Besucht den Knoten, dann den linken Teilbaum und danach den rechten.
Die Funktion wird mit Knoten 60 aufgerufen
Die Funktion wird mit Knoten 60 aufgerufen
Binärbaum
Ausgabe
Noch kein Knoten besucht
- Nicht besucht
- Läuft
- Auf dem Stapel
- Besucht
Schritt 1 / 44
Code
#include <iostream>
using namespace std;
class Node { // Ein Knoten enthält seinen Wert und Zeiger auf seine beiden Kinder
private: // Private Attribute: nur die Methoden greifen darauf zu
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
void preorder(Node* node) { // Durchläuft den Teilbaum mit Wurzel node
if (node == nullptr) return; // Basisfall: ein leerer Teilbaum hat nichts zu besuchen
cout << node->getValue() << " "; // Besucht den Knoten: verarbeitet seinen Wert
preorder(node->getLeft()); // Durchläuft den linken Teilbaum
preorder(node->getRight()); // Durchläuft den rechten Teilbaum
} // Kehrt zum Aufrufer zurück
Node* insert(Node* root, int v) { // Fügt v in den Suchbaum ein und gibt die Wurzel zurück
if (root == nullptr) return new Node(v); // Freie Stelle: hier kommt der neue Knoten hin
if (v < root->getValue()) // Kleinere Werte gehen nach links, größere nach rechts
root->setLeft(insert(root->getLeft(), v));
else
root->setRight(insert(root->getRight(), v));
return root;
}
Node* buildTree() { // Baut den Baum auf, indem die Werte nacheinander eingefügt werden
int values[] = {60, 45, 85, 68, 21, 55, 32}; // Die Werte des angezeigten Baums in Einfügereihenfolge
Node* root = nullptr;
for (int v : values) root = insert(root, v);
return root;
}
int main() {
Node* root = buildTree(); // Der Baum aus der Animation, bereits aufgebaut
preorder(root); // Erster Aufruf, aus main
cout << endl; // Ende der Traversierung
return 0;
}