En quoi le parcours en largeur d'abord est-il similaire au parcours d'un arbre binaire ?

Le parcours en largeur d'abord est similaire au parcours de niveau d'un arbre binaire. La recherche en largeur commence à partir du nœud racine et recherche et parcourt le long de la largeur de l'arborescence, c'est-à-dire qu'elle parcourt hiérarchiquement ; elle visite chaque couche séquentiellement de haut en bas, et dans chaque couche, de gauche à droite (ou de droite). à gauche) pour accéder aux nœuds, et après avoir accédé à un niveau, entrez dans le niveau suivant jusqu'à ce qu'aucun nœud ne soit accessible.

La recherche en largeur d'abord (en fait un parcours hiérarchique d'un arbre binaire), également appelée recherche en largeur d'abord ou recherche horizontale en premier, commence à partir du nœud racine. une traversée de recherche le long de la largeur de l’arbre.

Accédez à chaque couche dans l'ordre de haut en bas. Dans chaque couche, visitez les nœuds de gauche à droite (ou de droite à gauche). Après avoir visité une couche, entrez dans la couche suivante jusqu'à ce qu'aucun nœud ne soit accessible. .

L'ordre de parcours de l'arbre binaire ci-dessus est : ABCDEFG Les files d'attente peuvent être utilisées pour implémenter une recherche en largeur.

Algorithme de recherche en largeur :

Conserve tous les nœuds et prend beaucoup de place ; pas d'opérations de retour en arrière (c'est-à-dire pas d'opérations push ou pop), vitesse d'exécution rapide .

L'algorithme de recherche en largeur doit généralement stocker tous les nœuds générés, et l'espace de stockage occupé est beaucoup plus grand que celui de la recherche en profondeur. Par conséquent, lors de la conception du programme, le débordement et l'économie d'espace mémoire doivent être réduits. considéré. Cependant, la méthode de recherche en largeur d'abord ne comporte généralement pas d'opérations de retour en arrière, c'est-à-dire d'opérations push et pop, de sorte que la vitesse d'exécution est plus rapide que la recherche en profondeur d'abord.

Exemple :

L'inspection du processus consiste à visiter chaque couche de nœuds dans l'ordre et à visiter la première couche Passez au niveau suivant et chaque nœud ne peut être visité qu'une seule fois. Pour l'exemple ci-dessus, les résultats du parcours en largeur d'abord sont : A, B, C, D, E, F, G, H, I (en supposant que les nœuds de chaque couche sont accessibles de gauche à droite).

Le parcours en largeur de chaque nœud nécessite l'utilisation d'une structure de données de file d'attente (Queue). La caractéristique de la file d'attente est le premier entré, premier sorti. En fait, une file d'attente à double extrémité peut également être utilisée. La différence est que la première position d'une file d'attente à double extrémité peut être insérée et faire apparaître le nœud. L'ensemble du processus de parcours est le suivant :

Insérez d'abord le nœud A dans la file d'attente, queue(A);

Faites apparaître le nœud A et insérez les nœuds enfants de A B et C dans la file d'attente. , à ce moment-là, B est en tête de la file d'attente, C est à la fin de la file d'attente, file d'attente (B, C);

Fait apparaître le nœud B et insère les nœuds enfants de B. D et E dans la file d'attente, à ce moment C est en tête de la file d'attente, E est à la fin de la file d'attente, file d'attente (C, D, E)

Fait apparaître le nœud C et insère ; les nœuds enfants F, G et H de C dans la file d'attente. À ce moment, D est au début de la file d'attente et H est à la fin de la file d'attente, file d'attente (D, E, F,). G, H);

Affichez le nœud D. À ce moment, E est en tête de la file d'attente et H est en fin de file d'attente. , G, H);

... descendez dans l'ordre, et enfin le parcours est terminé

Le code Java est à peu près le suivant :

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ArrayList<Integer> wide(TreeNode root) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(root==null)
            return lists;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            lists.add(node.val);
		}
        return lists;
    }
}

Pour plus de connaissances connexes, veuillez visiter : Site Web PHP chinois !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!