Traversée de l'arbre binaire

1. Traversée en arbre binaire
2. Illustration de la traversée d’un arbre binaire
3. Algorithme de traversée de l’arbre binaire
4. Implémentation des traversées d’arbres binaires
5. Complexité de l’algorithme de traversée des arbres binaires

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

Traversée de pré-ordre

Traversée de l’après-ordre

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.