Parcours en largeur d'un arbre binaire de recherche

Le parcours en largeur d'un arbre binaire de recherche, c'est-à-dire parcourir niveau par niveau, en stockant les nœuds de chaque niveau dans une file, puis en effectuant des opérations de défilement (retirer des nœuds) et d'enfilement (stocker les nœuds du niveau suivant) pour atteindre l'objectif du parcours.

En introduisant une file pour prendre en charge le parcours en largeur :

  • Si le nœud racine est vide, il n'y a rien à parcourir ;

  • Si le nœud racine n'est pas vide :

    • D'abord, enfiler le nœud racine ;

    • Tant que la file n'est pas vide :

      • Défiler le nœud en tête de la file, puis le parcourir ;
      • Si le nœud en tête de la file a un enfant gauche, enfiler l'enfant gauche ;
      • Si le nœud en tête de la file a un enfant droit, enfiler l'enfant droit ;

Les étapes suivantes sont illustrées dans l'ordre :

(1)D'abord, retirer le nœud racine et le mettre dans la file

(2)Retirez 29, enfilez les nœuds enfants gauche et droit

(3)Le nœud de tête 17 est défilé, et ses nœuds enfants 14 et 23 sont enfilés.

(4)31 est défilé, et ses nœuds enfants 30 et 43 sont enfilés.

(5)Enfin, défilez tout

Exemple de code principal :
...
// Parcours en largeur de l’arbre binaire de recherche
public void levelOrder(){

    // Nous utilisons LinkedList comme file d’attente
    LinkedList<Node> q = new LinkedList<Node>();
    q.add(root);
    while( !q.isEmpty() ){

        Node node = q.remove();

        System.out.println(node.key);

        if( node.left != null )
            q.add( node.left );
        if( node.right != null )
            q.add( node.right );
    }
}
...

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

src/example/binary/LevelTraverse.java code du fichier :

package example.binary;

import java.util.LinkedList;

/**
* Parcours par niveaux
 */

public class LevelTraverse<Key extends Comparable<Key>, Value>{

    // Les nœuds dans l'arbre sont une classe privée ; le monde extérieur n'a pas besoin de connaître l'implémentation spécifique des nœuds de l'arbre binaire de recherche
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // Nœud racine
    private int count;  // Nombre de nœuds dans l'arbre

    // Constructeur, construit un arbre binaire de recherche vide par défaut
    public LevelTraverse() {
        root = null;
        count = 0;
    }

    // Renvoie le nombre de nœuds dans l'arbre binaire de recherche
    public int size() {
        return count;
    }

    // Renvoie si l'arbre binaire de recherche est vide
    public boolean isEmpty() {
        return count == 0;
    }

    // Insère une nouvelle paire de données (key, value) dans l'arbre binaire de recherche
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // Vérifie si key existe dans l'arbre binaire de recherche
    public boolean contain(Key key){
        return contain(root, key);
    }

    // Recherche dans l'arbre binaire de recherche la valeur correspondant à key. Si la valeur n'existe pas, renvoie null
    public Value search(Key key){
        return search( root , key );
    }

    // Parcours préfixe de l'arbre binaire de recherche
    public void preOrder(){
        preOrder(root);
    }

    // Parcours infixe de l'arbre binaire de recherche
    public void inOrder(){
        inOrder(root);
    }

    // Parcours postfixe de l'arbre binaire de recherche
    public void postOrder(){
        postOrder(root);
    }

    // Parcours en largeur de l’arbre binaire de recherche
    public void levelOrder(){

        // Nous utilisons LinkedList comme file d’attente
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(root);
        while( !q.isEmpty() ){

            Node node = q.remove();

            System.out.println(node.key);

            if( node.left != null )
                q.add( node.left );
            if( node.right != null )
                q.add( node.right );
        }
    }

    //********************
    //* Fonctions utilitaires pour l'arbre binaire de recherche
    //********************

    // Insérer le nœud (key, value) dans l'arbre binaire de recherche enraciné au nœud node, en utilisant un algorithme récursif
    // Retourne la racine de l'arbre binaire de recherche après l'insertion du nouveau nœud
    private Node insert(Node node, Key key, Value value){

        if( node == null ){
            count ++;
            return new Node(key, value);
        }

        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);

        return node;
    }

    // Vérifie si l'arbre binaire de recherche enraciné à node contient un nœud dont la valeur de clé est key, en utilisant un algorithme récursif
    private boolean contain(Node node, Key key){

        if( node == null )
            return false;

        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }

    // Trouver la valeur correspondant à key dans l'arbre binaire de recherche enraciné à node, algorithme récursif
    // Renvoyer NULL si la valeur n'existe pas
    private Value search(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }

    // Effectuer un parcours préfixe sur l'arbre binaire de recherche enraciné à node, algorithme récursif
    private void preOrder(Node node){

        if( node != null ){
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // Effectuer un parcours infixe sur l'arbre binaire de recherche enraciné à node, algorithme récursif
    private void inOrder(Node node){

        if( node != null ){
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    // Effectuer un parcours post-ordre sur l'arbre binaire de recherche dont la racine est node, algorithme récursif
    private void postOrder(Node node){

        if( node != null ){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }
   
}
autres extensions