Trouver des nœuds parents dans un arbre général: Guide de mise en œuvre basé sur la traverse de la traversée

Ce tutoriel détaille comment trouver le nœud parent d'un nœud spécifié dans une structure de données d'arborescence générale. Nous utiliserons l'algorithme de traversée (BFS) de largeur pour explorer systématiquement les nœuds de la couche d'arbre par couche et localiser efficacement le parent du nœud cible. L'article couvrira la définition de la structure des nœuds, les principes d'algorithmes BFS, la mise en œuvre du code Java, l'analyse de complexité du temps et de l'espace et des précautions connexes pour aider les lecteurs à maîtriser ces compétences de fonctionnement de l'arbre central.

1. Définition de la structure du nœud d'arbre général

Tout d'abord, nous définissons la structure du nœud de l'arbre général. Un nœud d'arbre commun contient généralement une clé pour l'identification, et une liste de nœuds enfants, car chaque nœud d'une arbre commun peut avoir n'importe quel nombre de nœuds enfants.

 import java.util.arraylist;

Node de classe publique {
    int key; // Valeur de clé de nœud ArrayList <node> enfants = new ArrayList  (); // Stockez la liste des nœuds enfants / **
     * Déterminez si le nœud actuel a des nœuds enfants.
     * Bien qu'il ne soit pas utilisé directement dans la logique de trouver des nœuds parents, il aide à comprendre les caractéristiques du nœud.
     * @return Renvoie True s'il y a des enfants, sinon vous rendez false.
     * /
    booléen public haschildren () {
        retour! Children.Isempty (); // une manière de jugement plus concise}
}</node>

2. Trouver le nœud parent: Principe d'élargissement de la traversée (BFS)

Pour trouver le nœud parent d'un nœud avec une valeur de clé spécifiée (Token), nous pouvons utiliser l'algorithme de recherche (BFS) de largeur (BFS). BFS est un algorithme qui explore la couche d'arbre ou de graphique par couche, ce qui est idéal pour résoudre des problèmes qui doivent trouver la relation la plus proche ou le chemin le plus court, comme la recherche du nœud parent.

Idée principale de l'algorithme: BFS utilise des files d'attente (files d'attente) pour gérer les nœuds à accéder. Il commence par le nœud racine, accède d'abord à tous les nœuds enfants du nœud actuel, puis ajoute ces nœuds enfants à la file d'attente, puis prend le nœud suivant de la file d'attente pour la même opération jusqu'à ce que la file d'attente soit vide ou que la cible soit trouvée.

Dans un scénario où nous recherchons un nœud parent, lorsque nous prenons un nœud P (en tant que parent potentiel) de la file d'attente, nous iterons à travers tous ses nœuds enfants c. Si nous constatons que la valeur clé d'un nœud enfant C correspond au jeton que nous recherchons, alors le P actuel est le nœud parent de notre nœud cible, et nous pouvons retourner P immédiatement. Si C ne correspond pas, nous faisons la file d'attente C afin qu'il puisse être vérifié en tant que parent potentiel dans les itérations ultérieures.

3. Implémentation Java

Ce qui suit est le code d'implémentation Java basé sur le principe ci-dessus:

 import java.util.arraylist;
import java.util.linkedlist;
Importer Java.util.Queue;

classe publique TreeOperations {

    / **
     * Trouvez le nœud parent du nœud de valeur clé spécifiée dans l'arborescence générale.
     * Implémenté à l'aide de la traversée de largeur de largeur (BFS).
     *
     * @Param Root Tree Root Node.
     * Token @param La valeur clé du nœud enfant à trouver.
     * @return Si trouvé, renvoyez le nœud parent du nœud cible; Si cela n'est pas trouvé ou que le nœud cible est le nœud racine (pas de nœud parent), renvoyez NULL.
     * /
    Public Static Node Findparent (Root de nœud, jeton int) {
        // Si l'arbre est vide ou si le nœud racine est vide, retournez NULL directement
        if (root == null) {
            retourner null;
        }

        // Utilisez LinkedList comme implémentation de la file d'attente Fitre <node> queue = new LinkedList  ();
        queue.add (root); // Ajoutez le nœud racine à la file d'attente comme point de départ de la traversée de traversée // la traversée de la priorité while (! Queue.isempty ()) {
            Nœud currentNode = queue.poll (); // Prenez le nœud actuel de la file d'attente, il servira de nœud parent potentiel // traversera tous les enfants du nœud actuel pour (nœud enfant: currentnode.children) {
                // Si la valeur clé du nœud enfant correspond au jeton cible if (child.key == token) {
                    return currentNode; // trouvé, le nœud actuel est le nœud parent du nœud cible}
                // Si le nœud enfant ne correspond pas, ajoutez-le à la file d'attente afin qu'il puisse être vérifié comme un nœud parent potentiel plus tard queue.add (enfant);
            }
        }

        // Après avoir traversé tous les nœuds, il n'a toujours pas été trouvé, indiquant que le nœud cible n'existe pas ou c'est le nœud racine (pas de nœud parent)
        retourner null;
    }

    public static void main (String [] args) {
        // construire un échantillon d'arbre générique // 1
        // / | \
        // 2 3 4
        // / \ \
        // 5 6 7
        Node root = new node ();
        root.key = 1;

        Node node2 = new node (); Node2.Key = 2;
        Node node3 = new node (); node3.key = 3;
        Node node4 = new node (); node4.key = 4;
        root.children.add (node2);
        root.children.add (node3);
        root.children.add (node4);

        Node node5 = new node (); Node5.key = 5;
        Node node6 = new node (); node6.key = 6;
        Node2.children.Add (Node5);
        Node2.children.Add (Node6);

        Node node7 = new node (); node7.key = 7;
        node4.children.Add (Node7);

        // tester pour trouver le nœud parentof6 = findparent (root, 6);
        if (parentof6! = null) {
            System.out.println ("Le nœud parent du nœud 6 est:" parentof6.key); // Sortie attendue 2
        } autre {
            System.out.println ("Non trouvé le nœud parent 6.");
        }

        Nœud parentof7 = findparent (root, 7);
        if (parentof7! = null) {
            System.out.println ("Le nœud parent du nœud 7 est:" parentof7.key); // Sortie attendue 4
        } autre {
            System.out.println ("nœud parent non trouvé du nœud 7.");
        }

        Nœud parentof1 = findparent (root, 1); // Le nœud racine n'a pas de nœud parent if (parentof1! = Null) {
            System.out.println ("Le nœud parent du nœud 1 est:" parentof1.key);
        } autre {
            System.out.println ("nœud parent non trouvé (ou c'est le nœud racine)."); // La sortie attendue n'est pas trouvée ...
        }

        Nœud parentof99 = findparent (root, 99); // nœud qui n'existe pas si (parentof99! = Null) {
            System.out.println ("Le nœud parent du nœud 99 est:" Parentof99.Key);
        } autre {
            System.out.println ("nœud parent non trouvé du nœud 99."); // La sortie attendue n'est pas trouvée ...
        }
    }
}</node>

4. Analyse de la complexité

• Complexité temporelle: o (n), où n est le nombre total de nœuds dans l'arbre. Dans le pire des cas, nous devons accéder à tous les nœuds de l'arborescence pour trouver le nœud parent du nœud cible (par exemple, le nœud cible est le dernier nœud feuille à accéder, ou le nœud cible n'existe pas). Chaque nœud est accessible au maximum une fois (entrez une fois, déshabillez une fois).
• Complexité de l'espace: o (w), où w est la largeur maximale de l'arbre (c'est-à-dire le nombre maximum de nœuds dans n'importe quelle couche). Dans le pire des cas, par exemple, un arbre binaire complet, le nombre de nœuds dans la dernière couche est proche de N / 2, et à ce moment, près des nœuds N / 2 peuvent être stockés dans la file d'attente. Pour un arbre parfaitement équilibré avec une hauteur de H, la complexité spatiale est O (n). Dans les cas extrêmes (par exemple, un arbre plat avec une seule couche et contenant tous les nœuds enfants), la complexité spatiale est également O (n).

5. Précautions et résumé

• Nœud parent du nœud racine: le nœud racine n'a pas de nœud parent. Si le jeton est la valeur clé du nœud racine, la fonction FindParent renvoie NULL, ce qui est logique.
• Le nœud cible n'existe pas: s'il n'y a pas de nœud correspondant au jeton dans l'arborescence, la fonction renverra également null.
• Avantages de BFS: Pour des problèmes tels que la recherche de nœuds parents qui nécessitent la traversée de tous les chemins possibles, BFS peut assurer que nous découvrions les nœuds dans l'ordre hiérarchique et le retour immédiatement lorsque la première correspondance est trouvée, ce qui est plus efficace.
• Choix de la récursivité et de l'itération: bien que certains problèmes de traversée d'arbres adoptent souvent la récursivité (comme la profondeur de traverse de traverse), pour des problèmes tels que la recherche de nœuds parents, la traversée de traversée (BFS) (BFS) est généralement plus intuitive et efficace par les files d'attente itératives et coordonnées. Lorsque le nœud de courant de courant est traité comme un nœud parent potentiel, si son enfant correspond au jeton, le Node de courant de courant est immédiatement son nœud parent. Cette relation hiérarchique se reflète naturellement dans BFS. Il est plus compliqué d'utiliser directement Recursion (DFS) pour trouver le nœud parent et peut nécessiter des paramètres supplémentaires pour transmettre les informations du nœud parent ou renvoyer un résultat contenant une paire parent-enfant.

Grâce à ce tutoriel, vous auriez dû maîtriser la méthode de recherche du nœud parent d'un nœud spécifié en utilisant la traversée de largeur d'abord dans un arbre général. comprendre

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!