Dans la programmation de la vie, nous rencontrons toujours des structures d'arbres. Au cours des derniers jours, nous avons juste besoin d'exploiter la structure des arbres, nous enregistrons donc nos propres méthodes et processus de fonctionnement. Supposons maintenant qu'il y ait un arbre comme celui-ci, (peu importe que ce soit un arbre binaire ou non, les principes sont les mêmes)
1. Priorité de profondeur
L'abréviation anglaise est DFS, à savoir la première recherche en profondeur.
La recherche en profondeur d'abord est une méthode plus couramment utilisée dans les premiers stades des robots de développement. Son objectif est d'atteindre les nœuds foliaires de la structure recherchée (c'est-à-dire les fichiers HTML qui ne contiennent pas d'hyperliens). Dans un fichier HTML, lorsqu'un hyperlien est sélectionné, le fichier HTML lié effectuera une recherche en profondeur d'abord, c'est-à-dire qu'une chaîne séparée doit être recherchée entière avant de rechercher les résultats de l'hyperlien restant. La recherche de priorité en profondeur suit l'hyperlien sur le fichier HTML jusqu'à ce qu'elle ne puisse pas être approfondie, puis revient à un certain fichier HTML et continue de sélectionner d'autres hyperliens dans le fichier HTML. Lorsqu'aucun autre hyperlien n'est disponible, la recherche est terminée. Le processus consiste simplement à approfondir chaque chemin de branche possible jusqu'à ce qu'il ne puisse pas être plus profond, et chaque nœud ne peut être accessible qu'une seule fois. Pour l'exemple ci-dessus, le résultat de la profondeur d'abord de travers est: a, b, d, e, i, c, f, g, h. (en supposant que le côté gauche du nœud enfant est laissé en premier).
La priorité en profondeur est utilisée pour traverser chaque nœud, et une structure de données comme un tas est requise. La caractéristique de la pile est d'aller d'abord, puis de sortir. L'ensemble du processus de traversée est le suivant:
Tout d'abord, appuyez sur le nœud A dans le tas, pile (a);
Pop-up nœud A et appuyez sur les nœuds enfants de A et B dans le tas en même temps. À l'heure actuelle, B est sur le dessus du tas, pile (b, c);
Pop-up nœud B et appuyez sur les nœuds enfants de B de B et D dans le tas. À l'heure actuelle, D est sur le dessus du tas, pile (D, E, C);
Node de pop-up D, aucun nœud enfant n'est pressé et E est en haut du tas, pile (e, c);
Pop up nœud E et appuyez sur le nœud enfant de E dans Stack (I, C);
... En bas à son tour et la traversée finale est terminée. Le code Java est à peu près le suivant:
public void DepthFirst () {stack <map <string, object >> nodestack = new Stack <map <string, object >> (); map <string, object> node = new hashmap <string, object> (); nodestack.add (node); while (! Nodestack.iSempty ()) {node = Nodestack.pop (); System.out.println (nœud); // Obtenez le nœud enfant du nœud. Pour l'arbre binaire, il s'agit d'obtenir le nœud enfant de gauche et le nœud enfant droit de la liste des nœuds <map <string, objet >> enfants = getchildren (nœud); if (enfants! = Null &&! Children.isempty ()) {for (map child: enfants) {nodestack.push (enfant);}}}}} /-2. Priorité d'étendue
L'abréviation anglaise est BFS, ce qui signifie la recherche de première étendue. Selon le test de processus, chaque couche de nœuds est accessible à son tour, et après avoir accédé à une couche, chaque nœud ne peut y accéder qu'une seule fois. Pour l'exemple ci-dessus, le résultat de la largeur de traverse est: a, b, c, d, e, f, g, h, i (en supposant que chaque couche de nœuds est accessible de gauche à droite).
L'étendue est utilisée pour traverser chaque nœud, et une structure de données comme une file d'attente est requise. La caractéristique de la file d'attente est premier, premier-out, et en fait, il peut également utiliser une file d'attente à double extrémité. La différence est que les nœuds peuvent être insérés et apparus à la première position de la file d'attente à double extrémité. L'ensemble du processus de traversée est le suivant:
Insérer d'abord le nœud A dans la file d'attente, file d'attente (a);
Pop up nœud A et insérer les nœuds enfants B et C de A dans la file d'attente. À l'heure actuelle, B est au début de la file d'attente et C est à la fin de la file d'attente, la file d'attente (B, C);
Pop-up nœud b et insérer les nœuds enfants D et E de B dans la file d'attente en même temps. À l'heure actuelle, C est au début de la file d'attente et E est à la fin de la file d'attente, la file d'attente (C, D, E);
Pop up Node C et insérer les nœuds enfants F, G, H de C dans la file d'attente. À l'heure actuelle, D est à la tête de la file d'attente et H est à la fin de la file d'attente (D, E, F, G, H);
Le nœud pop-up D, D n'a pas de nœuds enfants, à ce moment E est à la tête de la file d'attente, H est à la queue de la file d'attente, la file d'attente (E, F, G, H);
... En bas à son tour et la traversée finale est terminée. Le code Java est à peu près le suivant:
public void painFirst () {deque > nodedeque = nouveau Arraydeque > (); Carte node = new hashmap (); nodedequ.add (nœud); while (! nodedeque.isempty ()) {node = nodedequ.PeekFirst (); System.out.println (nœud); // Obtenez le nœud enfant du nœud. Pour l'arbre binaire, le nœud enfant gauche et le nœud enfant droit du nœud doivent obtenir la liste du nœud. > enfants = getchildren (nœud); if (enfants! = null &&! Children.iSempty ()) {for (map Child: Children) {nodedequ.add (enfant); }}}} // La file d'attente à double extrémité est utilisée ici, qui est la même que l'utilisation de la file d'attente Résumer
Ce qui précède est tout le contenu de cet article sur les exemples de code d'implémentation Java en profondeur et de l'étendue, et j'espère que cela sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!