Implementierung von Inorder Traversal für den Binärer Suchbaum in C++
In diesem Artikel wird erläutert, wie Sie Inorder-Traversal für binäre Suchbäume in C++ implementieren.
Verwenden Sie Inorder Traversal, um den Inhalt des Binärer Suchbaums zu drucken
Ein binärer Suchbaum wird so konstruiert, dass der Schlüssel jedes Knotens größer sein muss als alle Schlüssel in seinem linken Unterbaum und kleiner als alle Schlüssel in dem rechten Unterbaum.
Wir betrachten hier nur der Einfachheit halber unausgeglichene Bäume, aber in realen Szenarien kommt die Effizienz eines Binärer Suchbaums von der ausgeglichenen Natur, bei der jeder Teilbaum der Wurzel ungefähr die gleiche Höhe hat.
Binäre Bäume können mit drei verschiedenen Methoden durchlaufen werden: inorder, preorder und postorder. Die Inorder-Traversierung für den Binärer Suchbaum liefert die Elemente, die in nicht absteigender Reihenfolge sortiert sind. Diese Version beginnt normalerweise am äußersten linken Knoten und folgt der Reihenfolge, in der zuerst der linke Teilbaum, dann der Wurzelknoten und zuletzt der rechte Teilbaum durchlaufen wird.
Beachten Sie die folgende Code-Snippet-Ausgabe und die Reihenfolge der Ganzzahlen, wie sie in eine Baumstruktur eingefügt wurden.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreeInorder(TreeNode *n) {
if (n != nullptr) {
printTreeInorder(n->left);
cout << n->key << "; ";
printTreeInorder(n->right);
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreeInorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 3; 5; 9; 11; 15; 20; 23;
Alternativ müssen wir möglicherweise Preorder- oder Postorder-Traversal verwenden, um auf den Knoten im Binärer Suchbaum zuzugreifen. Wir müssen nur die Zeile cout << n->key << "; " in den Funktionen von printTree* verschieben, um den Traversal-Algorithmus zu ändern.
Die Preorder-Traversierung beginnt mit dem Drucken vom Root-Knoten und geht dann in den linken bzw. rechten Unterbaum, während die Postorder-Traversierung am Ende den Root-Knoten besucht.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreePreorder(TreeNode *n) {
if (n != nullptr) {
cout << n->key << "; ";
printTreePreorder(n->left);
printTreePreorder(n->right);
}
}
void printTreePostorder(TreeNode *n) {
if (n != nullptr) {
printTreePostorder(n->left);
printTreePostorder(n->right);
cout << n->key << "; ";
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreePostorder(root);
cout << endl;
printTreePreorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 9; 5; 3; 20; 15; 23; 11;
11; 3; 2; 5; 9; 23; 15; 20;
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook