Parcours en “profondeur d’abord”

Le parcours en profondeur (DFS - Depth-First Search) est une méthode d'exploration d'un arbre qui consiste à aller le plus profondément possible dans une branche avant d'explorer les autres branches. C'est comme explorer un labyrinthe en suivant toujours le même mur.

Caractéristiques principales

1. Récursivité : La plupart des implémentations utilisent la récursivité
2. Exploration verticale : On descend d'abord en profondeur avant d'explorer en largeur
3. Backtracking : On remonte quand on atteint une feuille pour explorer d'autres chemins

Analyse des exemples fournis

1. Recherche d'une valeur (contains)

boolean contains(Node n, int val){
    if (n.val==val) return true;
    for (Node fils:n.children){
        boolean rep = contains(fils, val);
        if(rep == true) return true;
    }
    return false;
}

• Vérifie d'abord le nœud actuel
• Explore récursivement chaque enfant
• Retourne true dès qu'une correspondance est trouvée

2. Calcul de la profondeur (treeDepth)

int treeDepth(Node n){
	if (n.children.size() == 0) return 1;
	int maxDepth = 0;
	for (Node Fils: n.children)
		int d = treeDepth(fils);
		if (d > maxDepth) maxDepth = d;
	}
	return maxDepth + 1;
}

int treeDepth(Node n, int level){
    if (n.children.size() == 0) return level;
    int maxDepth = 0;
    for(Node fils: n.children){
        int d = treeDepth(fils, level + 1);
        if (d > maxDepth) maxDepth = d;
    }
    return maxDepth;
}

• Garde trace du niveau actuel
• Explore tous les enfants en incrémentant le niveau
• Retourne la profondeur maximale trouvée

3. Comptage des feuilles (nbleaves)

int nbleaves(Node n){
    if (n.children.size() == 0) return 1;
    int nb = 0;
    for (Node fils: n.children)
        nb += nbleaves(fils);
    return nb;
}