Explication détaillée de la structure arborescente binaire en Java

L'arbre binaire est une structure de données courante en informatique et une structure de données couramment utilisée en programmation Java. Cet article présentera en détail la structure arborescente binaire en Java.

1. Qu'est-ce qu'un arbre binaire ?

En informatique, un arbre binaire est une structure arborescente dont chaque nœud a au plus deux nœuds enfants. Parmi eux, le nœud enfant gauche est plus petit que le nœud parent et le nœud enfant droit est plus grand que le nœud parent. Dans la programmation Java, les arbres binaires sont couramment utilisés pour représenter le tri, la recherche et l'amélioration de l'efficacité des requêtes de données.

2. Implémentation d'arbre binaire en Java

En Java, l'implémentation d'arbres binaires utilise généralement la classe de nœuds (Node Class) et la classe d'arbre binaire (Binary Tree Class). La classe de nœuds représente chaque nœud de l'arborescence binaire et peut avoir des octets et des attributs pour stocker les données. La classe d'arbre binaire représente l'intégralité de la structure de données de l'arbre binaire et possède des fonctions telles que l'insertion de nœuds, la suppression de nœuds et le parcours. Ce qui suit est une implémentation simple d'un arbre binaire Java :

public class Node {
    int key;
    String value;
    Node leftChild, rightChild;

    public Node(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

public class BinaryTree {
    Node root;

    public void insert(int key, String value) {
        Node newNode = new Node(key, value);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            while (true) {
                if (key < current.key) {
                    if (current.leftChild == null) {
                        current.leftChild = newNode;
                        return;
                    }
                    current = current.leftChild;
                } else {
                    if (current.rightChild == null) {
                        current.rightChild = newNode;
                        return;
                    }
                    current = current.rightChild;
                }
            }
        }
    }

    public Node find(int key) {
        Node current = root;
        while (current.key != key) {
            if (key < current.key) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    public void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(node.key + ": " + node.value);
            inOrderTraversal(node.rightChild);
        }
    }

    public void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.println(node.key + ": " + node.value);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }
    }

    public void postOrderTraversal(Node node) {
        if (node != null) {
            postOrderTraversal(node.leftChild);
            postOrderTraversal(node.rightChild);
            System.out.println(node.key + ": " + node.value);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.insert(50, "John");
        tree.insert(25, "Alice");
        tree.insert(75, "Bob");
        tree.insert(15, "Chris");
        tree.insert(33, "Diana");
        tree.insert(60, "Emily");
        tree.insert(90, "Fred");

        Node node = tree.find(33);
        System.out.println("Find key: " + node.key + ", value: " + node.value);

        System.out.println("In-order traversal:");
        tree.inOrderTraversal(tree.root);

        System.out.println("Pre-order traversal:");
        tree.preOrderTraversal(tree.root);

        System.out.println("Post-order traversal:");
        tree.postOrderTraversal(tree.root);
    }
}

Le code de l'arbre binaire ci-dessus comprend trois fonctions principales : l'insertion de nœuds, la recherche de nœuds et trois méthodes de traversée différentes. Le nœud d'insertion utilise une boucle while pour insérer les données dans l'ordre de l'arborescence binaire ; le nœud de recherche utilise une boucle while pour parcourir l'arborescence afin de rechercher les données cibles ; les trois méthodes de parcours sont implémentées de manière récursive.

3. Méthodes de traversée d'arbre binaire

Dans le code Java ci-dessus, le programme implémente trois méthodes différentes de traversée d'arbre binaire : traversée dans l'ordre, traversée en pré-ordre et post- ordre traversant. Cette section présentera ces trois méthodes de parcours une par une.

1. Parcours dans l'ordre

Le parcours dans l'ordre parcourt les nœuds de l'arborescence dans l'ordre du plus petit au plus grand. Dans le code Java, l'implémentation du parcours dans l'ordre utilise la récursion : pour chaque nœud, appelez d'abord son propre nœud gauche, puis imprimez les données du nœud, et enfin appelez son propre nœud droit. De cette façon, tous les nœuds de l’arborescence peuvent être parcourus du plus petit au plus grand.

2. Preorder traversal

Preorder traversal parcourt les nœuds de l'arborescence dans l'ordre du nœud parent, du nœud gauche et du nœud droit. Dans le code Java, l'implémentation du parcours de précommande utilise également la récursion : pour chaque nœud, imprimez d'abord les données du nœud, puis appelez son propre nœud gauche, et enfin appelez son propre nœud droit. De cette façon, tous les nœuds de l’arborescence peuvent être parcourus dans l’ordre du nœud parent, du nœud gauche et du nœud droit.

3. Parcours post-commande

Le parcours post-commande parcourt les nœuds de l'arborescence dans l'ordre du nœud gauche, du nœud droit et du parent nœud. Dans le code Java, l'implémentation du parcours post-ordre utilise également la récursion : pour chaque nœud, appelez d'abord son propre nœud gauche, puis appelez son propre nœud droit, et enfin imprimez les données du nœud. De cette façon, tous les nœuds de l’arborescence peuvent être parcourus dans l’ordre du nœud gauche, du nœud droit et du nœud parent.

4. Algorithmes d'arbre binaire couramment utilisés

L'arbre binaire est une structure de données flexible et très utile En programmation Java, l'algorithme d'arbre binaire est souvent utilisé. Les algorithmes d'arbre binaire suivants sont couramment utilisés :

1. Search

La recherche est l'une des fonctions les plus élémentaires des arbres binaires et est également fréquemment utilisée. fonction utilisée. Dans le code Java, la mise en œuvre de la recherche est très simple : pour chaque nœud, en comparant la taille de la valeur du nœud et la valeur cible, recherchez vers le bas couche par couche jusqu'à ce que la valeur cible soit trouvée ou que l'arbre entier soit parcouru.

2. Insertion

L'insertion est la fonction d'ajouter de nouveaux nœuds à l'arbre binaire, et les nouveaux nœuds insérés suivront également l'ordre de tri de l'arbre binaire. En code Java, la mise en œuvre de l'insertion est également relativement simple : comparez la taille du nœud à insérer et du nœud actuel, et insérez un nouveau nœud lorsqu'une position appropriée est trouvée.

3. Delete

La suppression est la fonction de suppression de nœuds de l'arborescence binaire Dans le code Java, la mise en œuvre de la suppression est plus compliquée et nécessite. à considérer. Plus. Si le nœud supprimé n'a pas de nœuds enfants, supprimez-le directement ; s'il n'y a qu'un seul nœud enfant, déplacez simplement le nœud enfant à la position du nœud supprimé ; si le nœud supprimé a deux nœuds enfants, vous devez trouver le minimum ; valeur du nœud enfant droit et remplacez-le par l'emplacement du nœud supprimé.

5. Résumé

Cet article présente en détail la structure des données de l'arbre binaire en Java, y compris la définition de l'arbre binaire, l'implémentation des nœuds et des classes d'arbre binaire, trois différents méthodes de traversée et algorithme d'arbre binaire couramment utilisé. L'arbre binaire est une structure de données largement utilisée et Java fournit de nombreuses fonctions et bibliothèques de classes pour faciliter la mise en œuvre des arbres binaires. Lors de la programmation en Java, la maîtrise de l'utilisation et de la mise en œuvre d'arbres binaires peut améliorer l'efficacité du programme et la précision des requêtes de données.

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!