logo

TechCodeview

Techniques de traversée d'arbres - Tutoriels sur la structure des données et les algorithmes

Techniques de traversée des arbres inclure différentes manières de visiter tous les nœuds de l’arbre. Contrairement aux structures de données linéaires (tableau, liste chaînée, files d'attente, piles, etc.) qui n'ont qu'une seule manière logique de les parcourir, les arbres peuvent être parcourus de différentes manières. Dans cet article, nous discuterons de toutes les techniques de traversée d'arbres ainsi que de leurs utilisations.



Table des matières

Signification de la traversée de l’arbre :

Traversée des arbres fait référence au processus de visite ou d'accès à chaque nœud de l'arborescence exactement une fois dans un certain ordre. Les algorithmes de traversée d'arbre nous aident à visiter et à traiter tous les nœuds de l'arbre. Étant donné que l'arbre n'est pas une structure de données linéaire, il existe plusieurs nœuds que nous pouvons visiter après avoir visité un certain nœud. Il existe plusieurs techniques de traversée d'arbre qui décident de l'ordre dans lequel les nœuds de l'arbre doivent être visités.

Techniques de traversée des arbres :



Une structure de données arborescente peut être parcourue des manières suivantes :

classe de scanner Java
  • Recherche en profondeur d'abord ou DFS
    • Traversée dans l'ordre
    • Traversée de précommande
    • Traversée des commandes postales
  • Traversée d'ordre de niveau ou recherche en largeur en premier ou BFS

Traversée dans l'ordre :

Le parcours dans l'ordre visite le nœud dans l'ordre : Gauche -> Racine -> Droite




Algorithme pour la traversée en ordre :

Dans l'ordre (arbre)

  • Parcourez le sous-arbre de gauche, c'est-à-dire appelez Inorder(left->subtree)
  • Visitez la racine.
  • Parcourez le sous-arbre droit, c'est-à-dire appelez Inorder(right->subtree)

Utilisations de la traversée en ordre :

  • Dans le cas des arbres de recherche binaires (BST), le parcours Inorder donne les nœuds dans un ordre non décroissant.
  • Pour obtenir les nœuds de BST dans un ordre non croissant, une variante du parcours Inorder où le parcours Inorder est inversé peut être utilisée.
  • Le parcours dans l'ordre peut être utilisé pour évaluer les expressions arithmétiques stockées dans les arbres d'expression.

Extrait de code pour la traversée en ordre :

C++ 
// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->gauche);  // Puis imprime les données du nœud cout<< node->données<< ' ';  // Now recur on right child  printInorder(node->droite); }>
C 
// Given a binary tree, print its nodes in inorder void printInorder(struct node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->gauche);  // Imprime ensuite les données du nœud printf('%d ', node->data);  // Répète maintenant sur l'enfant droit printInorder(node->right); }>
Java 
void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  System.out.print(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Python3 
# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>
C# 
// Given a binary tree, print // its nodes in inorder void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  Console.Write(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Javascript 
// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Sortir 
Inorder traversal of binary tree is 4 2 5 1 3>

Complexité temporelle : SUR)
Espace auxiliaire : Si nous ne considérons pas la taille de la pile pour les appels de fonction alors O(1) sinon O(h) où h est la hauteur de l'arbre.

Traversée de précommande :

Le parcours de précommande visite le nœud dans l'ordre : Racine -> Gauche -> Droite

chaîne ajouter

Algorithme pour le parcours des précommandes :

Précommande(arbre)

  • Visitez la racine.
  • Parcourez le sous-arbre de gauche, c'est-à-dire appelez Preorder(left->subtree)
  • Parcourez le sous-arbre de droite, c'est-à-dire appelez Preorder(right->subtree)

Utilisations du parcours de précommande :

  • Le parcours de précommande est utilisé pour créer une copie de l'arborescence.
  • Le parcours de précommande est également utilisé pour obtenir des expressions de préfixe sur un arbre d'expression.

Extrait de code pour le parcours de précommande :

C++ 
// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->données<< ' ';  // Then recur on left subtree  printPreorder(node->gauche);  // Récurrent maintenant sur le sous-arbre droit printPreorder(node->right); }>
C 
// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->données);  // Puis récidive sur le sous-arbre gauche printPreorder(node->left);  // Récurrent maintenant sur le sous-arbre droit printPreorder(node->right); }>
Java 
// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Python3 
# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>
C# 
// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Javascript 
// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Sortir 
Preorder traversal of binary tree is 1 2 4 5 3>

Complexité temporelle : SUR)
Espace auxiliaire : Si nous ne considérons pas la taille de la pile pour les appels de fonction alors O(1) sinon O(h) où h est la hauteur de l'arbre.

Traversée des commandes postales :

Le parcours post-ordre visite le nœud dans l'ordre : Gauche -> Droite -> Racine

Algorithme pour le parcours post-commande :

Algorithme Mandat postal (arbre)

  • Parcourez le sous-arbre de gauche, c'est-à-dire appelez Postorder(left->subtree)
  • Parcourez le sous-arbre droit, c'est-à-dire appelez Postorder(right->subtree)
  • Visitez la racine

Utilisations du parcours de vente par correspondance :

  • Le parcours post-ordre est utilisé pour supprimer l’arborescence. Voir la question de la suppression d'un arbre pour plus de détails.
  • Le parcours post-ordre est également utile pour obtenir l’expression suffixe d’un arbre d’expression.
  • Le parcours post-ordre peut aider dans les algorithmes de garbage collection, en particulier dans les systèmes où la gestion manuelle de la mémoire est utilisée.

Extrait de code pour la traversée de vente par correspondance :

C++ 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->gauche);  // Puis récidive sur le sous-arbre droit printPostorder(node->right);  // Traitez maintenant le nœud cout<< node->données<< ' '; }>
C 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->gauche);  // Puis récidive sur le sous-arbre droit printPostorder(node->right);  // Traitez maintenant le nœud printf('%d ', node->data); }>
Java 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  System.out.print(node.key + ' '); }>
Python3 
# A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # The recur on right child printPostorder(root.right) # Now print the data of node print(root.val, end=' '),>
C# 
// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  Console.Write(node.key + ' '); }>
Javascript 
// Given a binary tree, print its nodes according  // to the 'bottom-up' postorder traversal function printPostorder(node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  console.log(node.key + ' '); }>
Sortir 
Postorder traversal of binary tree is 4 5 2 3 1>

Traversée de l'ordre des niveaux :

Traversée de l'ordre des niveaux visite complètement tous les nœuds présents dans le même niveau avant de visiter le niveau suivant.

Algorithme pour la traversée de l'ordre de niveau :

Ordre de niveau (arbre)

  • Créer une file d'attente vide Q
  • Mettez le nœud racine de l'arborescence en file d'attente sur Q
  • Boucle pendant que Q n'est pas vide
    • Retirez un nœud de la file d'attente de Q et visitez-le
    • Mettre en file d'attente l'enfant gauche du nœud retiré de la file d'attente s'il existe
    • Mettre en file d'attente le bon enfant du nœud retiré de la file d'attente s'il existe

Utilisations de l'ordre de niveau :

  • Level Order Traversal est principalement utilisé comme recherche en largeur pour rechercher ou traiter des nœuds niveau par niveau.
  • Le parcours de l'ordre de niveau est également utilisé pour Sérialisation et désérialisation des arbres .

Extrait de code pour la traversée de l'ordre de niveau :

C++ 
// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queueq;  // Mettre la racine en file d'attente et initialiser la hauteur q.push(root);  while (q.empty() == false) { // Imprimer le début de la file d'attente et le supprimer de la file d'attente Node* node = q.front();  cout<< node->données<< ' ';  q.pop();  // Enqueue left child  if (node->gauche != NULL) q.push(node->left);  // Mettre en file d'attente l'enfant droit if (node->right != NULL) q.push(node->right);  } }>
C 
// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->données);  // Mettre l'enfant gauche en file d'attente if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Mettre en file d'attente l'enfant droit if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Supprimez le nœud de la file d'attente et faites-en temp_node temp_node = deQueue(queue, &front);  } }>
Java 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuefile d'attente = nouvelle LinkedList();  file d'attente.add(racine);  while (!queue.isEmpty()) { // poll() supprime la tête actuelle.  Nœud tempNode = queue.poll();  System.out.print(tempNode.data + '');  // Mettre l'enfant gauche en file d'attente if (tempNode.left != null) { queue.add(tempNode.left);  } // Mettre l'enfant droit en file d'attente if (tempNode.right != null) { queue.add(tempNode.right);  } } }>
Python3 
# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # Imprimer le début de la file d'attente et # le supprimer de la file d'attente print(queue[0].data, end=' ') node = queue.pop(0) # Mettre l'enfant gauche en file d'attente si node.left n'est pas Aucun : queue.append(node.left) # Mettre l'enfant droit en file d'attente si node.right n'est pas Aucun : queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuefile d'attente = nouvelle file d'attente();  queue.Enqueue(racine);  while (queue.Count != 0) { Node tempNode = queue.Dequeue();  Console.Write(tempNode.data + '');  // Mettre en file d'attente l'enfant gauche if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // Mettre l'enfant droit en file d'attente if (tempNode.right != null) { queue.Enqueue(tempNode.right);  } } }>
Javascript 
// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

Autres traversées d'arbres :

  1. Traversée des limites
  2. Traversée diagonale

1. Traversée des limites :

Traversée des limites d'un Arbre comprend :

  • limite gauche (nœuds à gauche à l'exclusion des nœuds feuilles)
  • feuilles (constituées uniquement des nœuds feuilles)
  • limite droite (nœuds à droite à l'exclusion des nœuds feuilles)

Algorithme de traversée des frontières :

BoundaryTraversal (arbre)

découper Java
  • Si root n'est pas nul :
    • Imprimer les données de la racine
    • PrintLeftBoundary(root->left) // Imprimer les nœuds de limite gauche
    • PrintLeafNodes(root->left) // Imprimer les nœuds feuilles du sous-arbre gauche
    • PrintLeafNodes(root->right) // Imprimer les nœuds feuilles du sous-arbre droit
    • PrintRightBoundary(root->right) // Imprimer les nœuds limites droits

Utilisations du franchissement des frontières :

  • La traversée des limites permet de visualiser la structure externe d'un arbre binaire, fournissant ainsi un aperçu de sa forme et de ses limites.
  • La traversée des frontières fournit un moyen d'accéder et de modifier ces nœuds, permettant des opérations telles que l'élagage ou le repositionnement des nœuds frontières.

2. Traversée diagonale

Dans le parcours diagonal d'un arbre, tous les nœuds d'une seule diagonale seront imprimés un par un.

Algorithme de traversée diagonale :

DiagonalTraversal(arbre) :

  • Si root n'est pas nul :
    • Créer une carte vide
    • DiagonalTraversalUtil(root, 0, M) // Appel de la fonction d'assistance avec le niveau diagonal initial 0
    • Pour chaque paire clé-valeur (diagonalLevel, nœuds) dans M :
      • Pour chaque nœud dans les nœuds :
      • Imprimer les données du nœud

DiagonalTraversalUtil (nœud, diagonalLevel, M) :

  • Si le nœud est nul :
  • Retour
  • Si diagonalLevel n’est pas présent dans M :
    • Créer une nouvelle liste en M pour diagonalLevel
  • Ajouter les données du nœud à la liste à M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Traverse l'enfant gauche avec un niveau diagonal augmenté
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Traverse l'enfant droit avec le même niveau diagonal

Utilisations de la traversée diagonale :

  • Le parcours diagonal aide à visualiser la structure hiérarchique des arbres binaires, en particulier dans les structures de données arborescentes telles que les arbres de recherche binaires (BST) et les arbres de tas.
  • Le parcours diagonal peut être utilisé pour calculer les sommes de chemin le long des diagonales dans un arbre binaire.

Foire aux questions (FAQ) sur les techniques de traversée des arbres :

1. Que sont les techniques de traversée d’arbres ?

Les techniques de traversée d'arbre sont des méthodes utilisées pour visiter et traiter tous les nœuds d'une structure de données arborescente. Ils vous permettent d'accéder à chaque nœud exactement une fois de manière systématique.

2. Quels sont les types courants de parcours d’arbres ?

Les types courants de parcours d'arbre sont : parcours dans l'ordre, parcours de pré-ordre, parcours de post-ordre, parcours par ordre de niveau (recherche en largeur d'abord)

3. Qu'est-ce que le parcours Inorder ?

Le parcours dans l'ordre est une méthode de parcours en profondeur d'abord où les nœuds sont visités dans l'ordre : sous-arbre gauche, nœud actuel, sous-arbre droit.

4. Qu'est-ce que le parcours de précommande ?

Le parcours de précommande est une méthode de parcours en profondeur d'abord où les nœuds sont visités dans l'ordre : nœud actuel, sous-arbre gauche, sous-arbre droit.

5. Qu'est-ce que le parcours des mandats postaux ?

Le parcours post-ordre est une méthode de parcours en profondeur d'abord où les nœuds sont visités dans l'ordre : sous-arbre gauche, sous-arbre droit, nœud actuel.

6. Qu'est-ce que le parcours d'ordre de niveau ?

La traversée par ordre de niveau, également connue sous le nom de Breadth-First Search (BFS), visite les nœuds niveau par niveau, en commençant par la racine et en passant au niveau suivant avant de parcourir plus profondément.

octets python dans la chaîne

7. Quand dois-je utiliser chaque technique de traversée ?

Le parcours dans l'ordre est souvent utilisé pour les arbres de recherche binaires afin d'obtenir les nœuds dans un ordre trié.

Le parcours de précommande est utile pour créer une copie de l'arborescence.

Le parcours post-ordre est couramment utilisé dans les arbres d’expression pour évaluer les expressions.

Le parcours par ordre de niveau est utile pour trouver le chemin le plus court entre les nœuds.

8. Comment implémenter des algorithmes de traversée d'arbres ?

Les algorithmes de traversée d'arbres peuvent être implémentés de manière récursive ou itérative, en fonction des exigences spécifiques et du langage de programmation utilisé.

9. Les algorithmes de traversée d'arbres peuvent-ils être appliqués à d'autres structures arborescentes ?

Oui, les algorithmes de traversée d'arbres peuvent être adaptés pour parcourir d'autres structures arborescentes telles que des tas binaires, des arbres n-aires et des graphiques représentés sous forme d'arbres.

10. Y a-t-il des considérations de performances lors du choix d'une technique de traversée ?

Les considérations en matière de performances dépendent de facteurs tels que la taille et la forme de l'arborescence, la mémoire disponible et les opérations spécifiques effectuées pendant le parcours. En général, le choix de la technique de parcours peut affecter l’efficacité de certaines opérations. Il est donc important de choisir la méthode la plus adaptée à votre cas d’utilisation spécifique.

Quelques autres tutoriels importants :

  • Tutoriel DSA
  • Tutoriel de conception de système
  • Feuille de route de développement logiciel
  • Feuille de route pour devenir chef de produit
  • Apprendre SAP
  • Apprendre le référencement