Parcours en profondeur d'un arbre binaire de recherche

Le parcours d'un arbre binaire de recherche se divise en deux grandes catégories : le parcours en profondeur et le parcours en largeur.

Le parcours en profondeur est divisé en trois types : le parcours préfixe d'arbre, le parcours infixe d'arbre et le parcours postfixe d'arbre, qui sont respectivement :

  • 1. Parcours préfixe :Visitez d'abord le nœud actuel, puis parcourez récursivement les sous-arbres gauche et droit dans l'ordre.
  • 2. Parcours infixe: Parcourez d'abord récursivement le sous-arbre gauche, puis visitez le nœud lui-même, puis parcourez récursivement le sous-arbre droit.
  • 3. Parcours postfixe: Parcourez d'abord récursivement les sous-arbres gauche et droit, puis visitez le nœud actuel lui-même.

Diagramme du résultat du parcours préfixé :

Exemple de code correspondant :

...
// 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);
    }
}
...

Diagramme du résultat du parcours infixé :

Exemple de code correspondant :

...
// 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);
    }
}
...

Diagramme du résultat du parcours postfixé :

Exemple de code correspondant :

...
// 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);
    }
}
...

Exemple de code Java

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

Code du fichier src/example/binary/Traverse.java :

package example.binary;

/**
* Parcours prioritaire
 */

public class Traverse<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 Traverse() {
        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);
    }

    //********************
    //* 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