Comment implémenter un algorithme d'arbre de recherche binaire à l'aide de Java

Comment utiliser Java pour implémenter l'algorithme de l'arbre de recherche binaire

L'arbre de recherche binaire (BST) est une structure de données couramment utilisée qui peut implémenter efficacement des opérations telles que l'insertion, la suppression et la recherche. Cet article explique comment utiliser Java pour implémenter un arbre de recherche binaire et fournit des exemples de code correspondants.

1. Définition de l'arbre de recherche binaire

L'arbre de recherche binaire est un arbre ordonné avec les caractéristiques suivantes :

1. Chaque nœud a une valeur clé unique.
2. La valeur clé du sous-arbre gauche est inférieure à la valeur clé du nœud et la valeur clé du sous-arbre droit est supérieure à la valeur clé du nœud.
3. Le sous-arbre gauche et le sous-arbre droit sont également des arbres de recherche binaires.

2. Implémentez la classe de nœuds de l'arbre de recherche binaire

Tout d'abord, nous définissons une classe de nœuds de l'arbre de recherche binaire, comprenant les valeurs clés et les références aux nœuds enfants gauche et droit. Le code est le suivant :

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

Dans cette classe de nœuds, nous sauvegardons les références des nœuds enfants gauche et droit via le champ data字段保存节点的键值，left和right.

3. Implémentez l'opération d'insertion de l'arbre de recherche binaire

Ensuite, nous implémentons l'opération d'insertion de l'arbre de recherche binaire. L'opération d'insertion détermine la position d'insertion du nœud en comparant la taille de la valeur clé du nœud. Si la valeur clé est plus petite que le nœud actuel, elle est insérée dans le sous-arbre de gauche, sinon elle est insérée dans le sous-arbre de droite. Le code est le suivant :

class BinarySearchTree {
    Node root;

    // 插入操作
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        // 如果树为空，创建一个新的节点
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // 否则，递归地插入节点到左子树或右子树
        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);

        return root;
    }
}

Dans l'opération d'insertion, nous déterminons d'abord si l'arborescence est vide, si elle est vide, créons un nouveau nœud comme nœud racine. Sinon, insérez de manière récursive dans le sous-arbre gauche ou droit en comparant la relation de taille entre la valeur clé et le nœud actuel.

4. Implémenter l'opération de recherche de l'arbre de recherche binaire

L'opération de recherche de l'arbre de recherche binaire est relativement simple. Elle compare étape par étape la relation de taille entre la valeur clé et le nœud jusqu'à ce qu'une correspondance soit trouvée ou un vide. Le nœud est rencontré. Le code est le suivant :

class BinarySearchTree {
    ...

    // 查找操作
    public boolean contains(int key) {
        return containsRec(root, key);
    }

    private boolean containsRec(Node root, int key) {
        // 树为空或者找到匹配节点
        if (root == null || root.data == key)
            return (root != null);

        // 比较键值与当前节点
        if (key < root.data)
            return containsRec(root.left, key);
        else
            return containsRec(root.right, key);
    }
}

Dans l'opération de recherche, nous déterminons d'abord si l'arborescence est vide ou si le nœud actuel correspond. Renvoie vrai s'il y a une correspondance, sinon recherche récursivement le sous-arbre gauche ou droit en comparant la taille de la valeur clé avec le nœud actuel.

5. Code pour tester l'arbre de recherche binaire

Enfin, nous écrivons du code pour tester l'arbre de recherche binaire que nous avons implémenté. Le code est le suivant :

public class Main {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println(tree.contains(30));
        System.out.println(tree.contains(90));
    }
}

Le résultat courant est :

true
false

Ici, nous insérons quelques nœuds dans l'arborescence en appelant l'opération d'insertion. Ensuite, nous appelons l'opération find pour trouver des nœuds avec des valeurs clés respectivement 30 et 90. Le résultat renvoyé indique si l'opération d'insertion a réussi.

Grâce aux étapes ci-dessus, nous avons implémenté avec succès l'algorithme d'arbre de recherche binaire à l'aide de Java et implémenté les opérations d'insertion et de recherche. Dans les applications pratiques, les arbres de recherche binaires peuvent également prendre en charge des fonctions telles que les opérations de suppression, le parcours de pré-commande, dans l'ordre et après l'ordre. Les lecteurs peuvent étendre davantage la mise en œuvre en fonction de besoins spécifiques.

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!