Recherche en largeur d'abord (BFS) et recherche en profondeur d'abord (DFS) pour les arbres binaires en Java
Recherche en largeur d'abord et Recherche en profondeur d'abord sont deux techniques pour parcourir des graphes et des arbres. Dans ce tutoriel, nous nous concentrerons principalement sur les parcours BFS et DFS dans les arbres.
Qu'est-ce que la recherche en profondeur (DFS) ?
L'algorithme commence au nœud racine puis explore chaque branche avant de revenir en arrière. Il est implémenté en utilisant des piles. Souvent, lors de l'écriture du code, nous utilisons des piles de récursion pour revenir en arrière. En utilisant la récursion, nous sommes capables de 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 parcours DFS.
- En ordre
- Pré-commande
- Après-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 parcourt tous les enfants directs de la racine. Après que tous les enfants directs de la racine ont été parcourus, il passe à leurs enfants, et ainsi de suite. Pour implémenter le BFS, nous utilisons une file d'attente.
Pour les arbres binaires, nous avons le parcours en largeur (Level Order Traversal) qui suit le BFS.
Implémentation de BFS et DFS en Java
Que l'arbre considéré soit :
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. Parcours en préordre
Dans le parcours en pré-ordre d'un arbre binaire, nous parcourons d'abord la racine, puis le sous-arbre gauche et enfin le sous-arbre droit. Nous faisons cela de manière récursive pour profiter du fait que les sous-arbres gauche et droit sont également des arbres.
L'algorithme pour le parcours en pré-ordre est le suivant :
- Traversez la racine.
- Appelez preorder() sur le sous-arbre gauche.
- Appelez preorder() sur le sous-arbre droit.
Le parcours en pré-ordre 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. Parcours en ordre
Le parcours en ordre d'un arbre binaire traverse d'abord le sous-arbre gauche, puis la racine et enfin le sous-arbre droit.
L'algorithme pour le parcours en ordre est le suivant :
- Appelez inorder() sur le sous-arbre gauche.
- Traversez la racine.
- Appelez inorder() sur le sous-arbre droit.
Le parcours en 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. Parcours post-ordre
Le parcours post-ordre d'un arbre binaire parcourt d'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin la racine.
L'algorithme pour le parcours en post-ordre est le suivant :
- Appelez postorder() sur le sous-arbre gauche.
- Appelez postorder() sur le sous-arbre droit.
- Traversez 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. Parcours en largeur
Le parcours en ordre de niveau utilise une file d'attente pour garder la trace des nœuds à visiter. Après avoir visité un nœud, ses enfants sont mis dans la file d'attente. Pour obtenir un nouveau nœud à parcourir, 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 comme racine
Exécuter une boucle tant que la file n'est pas vide
- Imprimer les données depuis temp.
- Mettre en file d'attente les enfants de temp dans l'ordre gauche puis droite.
- Retirez un nœud de la file d'attente et assignez sa valeur à temp.
Le parcours en largeur 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 portait sur les parcours BFS et DFS dans les arbres binaires. Pour obtenir l'implémentation DFS en C++, référez-vous à ce tutoriel. Pour l'implémentation en C++ du parcours par niveau, référez-vous à ce tutoriel.