Comment fonctionne la recherche dans l'arbre?

La recherche dans un arbre dépend de sa structure et de l’objectif de la recherche.

Principales méthodes de recherche:

Recherche en profondeur (DFS - Depth-First Search): Elle va aussi profondément que possible dans une branche avant de passer à la suivante. Elle est implémentée à l’aide d’une pile (explicite ou via récursion).
- Parcours pré-ordre : Visiter la racine, puis le sous-arbre gauche, puis le sous-arbre droit.
- Parcours en ordre (In-order) : Visiter le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Utilisé pour obtenir une liste triée d’éléments dans des arbres binaires de recherche.
- Parcours post-ordre : Visiter le sous-arbre gauche, puis le droit, puis la racine.
Recherche en largeur (BFS - Breadth-First Search): Explore tous les voisins du nœud actuel à un niveau avant de passer au niveau suivant. Implémentée avec une file.

Exemple DFS (In-order) pour un arbre binaire:

// TreeNode représente un nœud d’arbre binaire
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal effectue un parcours inorder
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Appel récursif pour le sous-arbre gauche
	result = append(result, InOrderTraversal(root.Left)...)
	// Visiter le nœud actuel
	result = append(result, root.Val)
	// Appel récursif pour le sous-arbre droit
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Exemple BFS:

// TreeNode représente un nœud d’arbre binaire
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal effectue un parcours BFS
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// File pour stocker les nœuds du niveau actuel
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Extraire le premier élément de la file
		node := queue[0]
		queue = queue[1:]

		// Ajouter la valeur du nœud aux résultats
		result = append(result, node.Val)

		// Ajouter le fils gauche à la file si il existe
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Ajouter le fils droit à la file si il existe
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Pour les arbres binaires de recherche (BST), où le sous-arbre gauche est inférieur à la racine et le droit supérieur:

Recherche binaire: Lors de la recherche d’une valeur spécifique, on la compare à la racine. Si elle est inférieure, on cherche dans le sous-arbre gauche; si elle est supérieure, dans le droit. C’est la stratégie la plus efficace pour rechercher dans un BST.

// TreeNode représente un nœud d’arbre binaire de recherche
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST effectue une recherche binaire dans un BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Nœud trouvé ou arbre vide
	}

	if target < root.Val {
		// Chercher dans le sous-arbre gauche
		return SearchBST(root.Left, target)
	}
	// Chercher dans le sous-arbre droit
	return SearchBST(root.Right, target)
}

Le choix de l’algorithme de recherche dépend de la tâche et des caractéristiques de l’arbre. DFS convient pour les tâches où il faut explorer profondément une branche ou trouver un chemin vers un objectif. BFS est utile pour trouver le chemin le plus court ou parcourir par niveaux. La recherche binaire est efficace pour trouver une valeur spécifique dans des structures triées comme le BST.