Traversée de l'arbre binaire
- Traversée en arbre binaire
- Illustration de la traversée d’un arbre binaire
- Algorithme de traversée de l’arbre binaire
- Implémentation des traversées d’arbres binaires
- Complexité de l’algorithme de traversée des arbres binaires
![Traversée de l'arbre binaire](/img/Data-Structure/feature-image---binary-tree-traversal.webp)
Un arbre binaire est une structure de données non linéaire. Il est appelé arbre binaire parce que chaque nœud a un maximum de deux enfants. Ces enfants sont appelés enfants de gauche et enfants de droite. Il peut également être interprété comme un graphe non dirigé dans lequel le nœud supérieur est appelé racine. Contrairement aux structures de données linéaires qui ne peuvent être parcourues que d’une seule manière, un arbre peut être parcouru de différentes manières. Nous pouvons traverser un arbre en explorant le long de la profondeur ou de la largeur. La première approche est appelée traversée en profondeur et la seconde traversée en largeur. Dans cet article, nous allons discuter de la traversée en profondeur et de la traversée en largeur.
Il existe trois types de premiers passages en profondeur : dans l’ordre, en préordre et en post-ordre. Nous les examinerons un par un.
Traversée en arbre binaire
Traversée de l’ordre
Dans cette traversée, nous visitons d’abord le sous-arbre gauche, puis la racine, et enfin le sous-arbre droit. Chaque nœud ressemble à un sous-arbre. Pour BST, la traversée dans l’ordre renvoie tous les éléments en ordre croissant
Traversée de la précommande
Dans cette traversée, nous visitons d’abord la racine, puis le sous-arbre gauche, et enfin le sous-arbre droit. Chaque nœud ressemble à un sous-arbre. Il est normalement utilisé pour se répliquer, c’est-à-dire créer une copie de l’arbre. La traversée des préfixes permet également de générer une expression de préfixe à partir d’un arbre d’expression.
Traversée de l’ordre
Dans cette traversée, nous visitons d’abord le sous-arbre gauche, puis le sous-arbre droit, et enfin la racine. Chaque nœud ressemble à un sous-arbre. Il est utilisé pour supprimer efficacement les arbres. Il permet également de générer des expressions postfix à partir d’un arbre d’expression.
Illustration de la traversée d’un arbre binaire
Inorder Traversal: (4, 2, 1, 5, 3, 6, 7, 8, 9)
Nous appelons traversée de l’ordre sur le nœud racine 3
. Nous traversons récursivement à gauche pour atteindre le nœud 4
, qui est le nœud le plus à gauche, et l’inclure dans notre sortie ; comme il s’agit de la racine et qu’il n’a pas de nœud gauche, nous visitons son nœud le plus à droite 2
et l’incluons dans notre traversée. De cette façon, nous parcourons l’arbre entier pour obtenir l’ordre ci-dessus comme notre sortie.
Pré-ordre de traversée : (3, 1, 4, 2, 5, 7, 6, 9, 8)
Nous appelons la traversée de préordre sur le nœud racine 3
et l’incluons dans notre sortie. Ensuite, nous nous déplaçons récursivement vers la gauche pour atteindre le noeud racine suivant 1
puis 4
. Comme 4
n’a pas d’enfant gauche, nous visitons le nœud droit 2
. Nous avons maintenant couvert le sous-arbre sous le nœud racine 4
et nous remontons au nœud 1
et allons vers sa droite jusqu’au nœud 5
. De cette façon, nous traversons l’arbre entier pour obtenir l’ordre ci-dessus comme notre sortie.
Traversée post-ordre: (2, 4, 5, 1, 6, 8, 9, 7, 3)
Nous appelons traversée post-ordre sur le nœud racine 3
. Traversée récursive vers la gauche pour atteindre le nœud 4
. Avant d’inclure 4
dans notre traversée, nous devons visiter son noeud droit 2
. Nous incluons 2
puis 4
dans notre sortie et revenons à 1
.1
a son noeud droit 5
non visité, donc nous incluons d’abord 5
puis 1
dans la sortie. Ensuite, nous revenons au nœud racine 3
et continuons à parcourir le sous-arbre de droite. De cette façon, nous traversons l’arbre entier pour obtenir l’ordre ci-dessus comme notre sortie.
Algorithme de traversée de l’arbre binaire
Traversée de l’ordre
-
Traversez le sous-arbre de gauche en appelant récursivement la fonction de mise en ordre.
-
Visitez le nœud racine.
-
Traversez le sous-arbre de droite en appelant récursivement la fonction d’ordre.
Traversée de pré-ordre
-
Visitez le nœud racine.
-
Traversez le sous-arbre de gauche en appelant récursivement la fonction d’ordre.
-
Traversez le sous-arbre de droite en appelant récursivement la fonction d’ordre.
Traversée de l’après-ordre
-
Traversez le sous-arbre de gauche en appelant récursivement la fonction de mise en ordre.
-
Traversez le sous-arbre de droite en appelant récursivement la fonction de mise en ordre.
-
Visitez le nœud racine.
Implémentation des traversées d’arbres binaires
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
Node(int x) {
this->key = x;
this->left = this->right = NULL;
}
};
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
void preorder(Node* root) {
if (root != NULL) {
cout << root->key << " ";
preorder(root->left);
preorder(root->right);
}
}
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->key << " ";
}
}
int main() {
Node* root = new Node(3);
root->left = new Node(1);
root->right = new Node(7);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->left->left->right = new Node(2);
root->right->left = new Node(6);
root->right->right = new Node(9);
root->right->right->left = new Node(8);
cout << "The inorder traversal of the tree is : ";
inorder(root);
cout << endl;
cout << "The preorder traversal of the tree is : ";
preorder(root);
cout << endl;
cout << "The postorder traversal of the tree is : ";
postorder(root);
cout << endl;
}
Complexité de l’algorithme de traversée des arbres binaires
Complexité du temps
- Cas moyen
Il y a n
nœuds dans un arbre, dans tous les 3
types de traversées, nous devons aller visiter chaque nœud. Puisque nous itérons sur n
nœuds, bien que dans un ordre différent, la complexité temporelle pour les 3 traversées est de l’ordre de O(n)
. La complexité temporelle moyenne des cas est O(n)
.
- Meilleur cas
La complexité temporelle dans le meilleur des cas est O(n)
. C’est la même chose que la complexité temporelle moyenne pour toutes les traversées 3
.
- Pire cas
La complexité temporelle dans le pire des cas est O(n)
. C’est la même chose que la complexité temporelle du cas le plus défavorable pour toutes les traversées 3
.
Complexité spatiale
La complexité spatiale de l’algorithme est O(n)
en raison de l’espace supplémentaire requis par les appels de récursion.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInArticle connexe - Data Structure
- Arbre binaire de recherche
- Convertir l'arbre binaire en arbre binaire de recherche
- Insertion itérative de l'arbre binaire de recherche
- Successeur de l'arbre de recherche binaire
- Suppression de l'arbre binaire de recherche