Recherche en profondeur (BFS) et recherche en profondeur (DFS) pour les arbres binaires en Java
La recherche en profondeur d'abord et la recherche en profondeur d'abord sont deux techniques de parcours de graphes et d'arbres. Dans ce tutoriel, nous nous concentrerons principalement sur les traversées BFS et DFS dans les arbres.
Qu'est-ce que la recherche en profondeur (DFS) ?
L'algorithme commence au nœud racine, puis il explore chaque branche avant de revenir en arrière. Il est implémenté à l'aide de piles. Souvent, lors de l'écriture du code, nous utilisons des piles de récursivité pour revenir en arrière. En utilisant la récursivité, nous pouvons tirer parti du fait que les sous-arbres gauche et droit sont également des arbres et partagent les mêmes propriétés.
Pour les arbres binaires, il existe trois types de traversées DFS.
- En ordre
- Pré-commande
- Post-commande
Qu'est-ce que la recherche en largeur (BFS) ?
Cet algorithme commence également au nœud racine, puis visite tous les nœuds niveau par niveau. Cela signifie qu'après la racine, il traverse tous les enfants directs de la racine. Une fois que tous les enfants directs de la racine ont été parcourus, elle se déplace vers leurs enfants et ainsi de suite. Pour implémenter BFS, nous utilisons une file d'attente.
Pour les arbres binaires, nous avons Level Order Traversal qui suit BFS.
Implémentation de BFS et DFS en Java
Soit l'arbre considéré :
La structure de la classe TreeNode est la suivante :
static class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int key) {
data = key;
left = right = null;
}
}
1. Traversée de pré-commande
Dans le parcours pré-ordonné d'un arbre binaire, nous parcourons d'abord la racine, puis le sous-arbre gauche et enfin le sous-arbre droit. Nous le faisons de manière récursive pour bénéficier du fait que les sous-arbres gauche et droit sont également des arbres.
L'algorithme de parcours de pré-ordre est le suivant :
- Traverser la racine.
- Appelez preorder() dans la sous-arborescence de gauche.
- Appelez preorder() dans la sous-arborescence de droite.
La traversée de pré-commande de l'arbre ci-dessus est :
0 1 3 4 2
Le code java est le suivant :
static void preorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse root
System.out.print(TreeNode.item + "->");
// Traverse left
preorder(TreeNode.left);
// Traverse right
preorder(TreeNode.right);
}
2. Traversée dans l'ordre
Le parcours dans l'ordre d'un arbre binaire traverse d'abord le sous-arbre gauche, puis la racine et enfin le sous-arbre droit.
L'algorithme de parcours dans l'ordre est le suivant :
- Appelez inorder() sur le sous-arbre de gauche.
- Traverser la racine.
- Appelez inorder() sur le sous-arbre de droite.
Le parcours dans l'ordre de l'arbre ci-dessus est :
3 1 4 0 2
Le code java est le suivant :
static void inorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
inorder(TreeNode.left);
// Traverse root
System.out.print(TreeNode.item + "->");
// Traverse right
inorder(TreeNode.right);
}
3. Traversée post-commande
Le parcours post-ordre d'un arbre binaire traverse d'abord le sous-arbre gauche puis le sous-arbre droit et enfin la racine.
L'algorithme de parcours post-ordre est le suivant :
- Appelez postorder() sur le sous-arbre de gauche.
- Appelez postorder() sur le sous-arbre de droite.
- Traverser la racine.
Le parcours post-ordre de l'arbre ci-dessus est :
3 4 1 2 0
Le code java est le suivant :
static void postorder(TreeNode TreeNode) {
if (TreeNode == null)
return;
// Traverse left
postorder(TreeNode.left);
// Traverse right
postorder(TreeNode.right);
// Traverse root
System.out.print(TreeNode.item + "->");
}
4. Traversée d'ordre de niveau
La traversée d'ordre de niveau utilise une file d'attente pour garder une trace des nœuds à visiter. Après avoir visité un nœud, ses enfants sont placés dans la file d'attente. Pour obtenir un nouveau nœud à traverser, nous retirons des éléments de la file d'attente.
L'algorithme est le suivant :
- Initialiser une file d'attente vide
- Commencez par définir temp en tant que racine
- Exécuter une boucle jusqu'à ce que la file d'attente ne soit pas vide
- Imprimer les données de temp.
- Mettre en file d'attente les enfants de temp dans l'ordre de gauche puis de droite.
- Retirer un nœud de la file d'attente et attribuer sa valeur à temp.
Le parcours d'ordre de niveau de l'arbre ci-dessus est :
0 1 2 3 4Le code java est le suivant :
static void printLevelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { TreeNode temp = queue.poll(); System.out.print(temp.data + " "); /*add left child to the queue */ if (temp.left != null) { queue.add(temp.left); } /*add right right child to the queue */ if (temp.right != null) { queue.add(temp.right); } } }Implémentation complète du code de BFS et DFS en Java
Le code Java complet est donné ci-dessous :
package com.JournalDev; import java.util.LinkedList; import java.util.Queue; public class Main { static class TreeNode { int data; TreeNode left, right; public TreeNode(int key) { data = key; left = right = null; } } static void preorder(TreeNode TreeNode) { if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.data + " "); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); } static void inorder(TreeNode TreeNode) { if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.data + " "); // Traverse right inorder(TreeNode.right); } static void postorder(TreeNode TreeNode) { if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.data + " "); } static void printLevelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { TreeNode tempNode = queue.poll(); System.out.print(tempNode.data + " "); /*add left child to the queue */ if (tempNode.left != null) { queue.add(tempNode.left); } /*add right right child to the queue */ if (tempNode.right != null) { queue.add(tempNode.right); } } } public static void main(String args[]) { TreeNode root = new TreeNode(0); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); System.out.println("Inorder traversal"); inorder(root); System.out.println("\nPreorder traversal "); preorder(root); System.out.println("\nPostorder traversal"); postorder(root); System.out.println("\nLevelorder traversal"); printLevelOrder(root); } }Output : Inorder traversal 3 1 4 0 2 Preorder traversal 0 1 3 4 2 Postorder traversal 3 4 1 2 0 Levelorder traversal 0 1 2 3 4
Conclusion
Ce tutoriel concernait les traversées BFS et DFS dans les arbres binaires. Pour obtenir l'implémentation DFS en C++, reportez-vous à ce tutoriel.