Implémenter Inorder Traversal pour l'arbre de recherche binaire en C++
Cet article explique comment implémenter la traversée inorder pour les arbres de recherche binaires en C++.
Utilisez Inorder Traversal pour imprimer le contenu de l’arbre de recherche binaire
Un arbre de recherche binaire est construit de sorte que la clé de chaque nœud doit être supérieure à toutes les clés de son sous-arbre gauche et inférieure à toutes les clés du sous-arbre droit.
Nous ne considérons ici que les arbres déséquilibrés par souci de simplicité, mais dans les scénarios du monde réel, l’efficacité d’un arbre de recherche binaire provient de la nature équilibrée, où chaque sous-arbre de la racine a à peu près la même hauteur.
Les arbres binaires peuvent être parcourus en utilisant trois méthodes différentes nommées : inorder, preorder et postorder. La traversée dans l’ordre de l’arbre de recherche binaire donne les éléments triés par ordre non décroissant. Cette version commence généralement par le nœud le plus à gauche et suit l’ordre dans lequel le sous-arbre gauche sera parcouru en premier, puis le nœud racine et enfin le sous-arbre droit.
Notez la sortie de l’extrait de code suivant et l’ordre des nombres entiers tels qu’ils ont été insérés dans une arborescence.
#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;
Alternativement, nous pourrions avoir besoin d’utiliser une traversée de pré-ordre ou de post-ordre pour accéder au nœud dans l’arbre de recherche binaire. Il suffit de déplacer la ligne cout << n->key << "; " dans les fonctions printTree* pour modifier l’algorithme de parcours.
Le parcours de pré-ordre commence à imprimer à partir du nœud racine, puis va dans les sous-arbres gauche et droit, respectivement, tandis que le parcours de post-ordre visite le nœud racine à la fin.
#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