Im Programmierleben begegnen wir immer Baumstrukturen. In den letzten Tagen müssen wir nur die Baumstruktur bedienen, damit wir unsere eigenen Betriebsmethoden und -prozesse aufzeichnen. Nehmen wir nun an, es gibt einen solchen Baum (es spielt keine Rolle, ob es sich um einen binären Baum handelt oder nicht, die Prinzipien sind gleich)
1. Tiefe Priorität
Die englische Abkürzung ist DFS, nämlich Tiefe erste Suche.
Die Tiefensuche ist eine Methode, die häufiger in den frühen Stadien von Entwicklungscrawlern verwendet wird. Sein Zweck ist es, die Blattknoten der durchsuchten Struktur zu erreichen (d. H. Die HTML -Dateien, die keine Hyperlinks enthalten). Wenn in einer HTML-Datei ein Hyperlink ausgewählt ist, führt die verknüpfte HTML-Datei eine Tiefensuche durch, dh eine separate Kette muss vollständig durchsucht werden, bevor nach den verbleibenden Hyperlink-Ergebnissen gesucht wird. Die Suche in der Tiefe Priority folgt dem Hyperlink in der HTML -Datei, bis sie erst weiter vertieft werden kann, kehrt dann zu einer bestimmten HTML -Datei zurück und wählt weiterhin andere Hyperlinks in der HTML -Datei aus. Wenn keine anderen Hyperlinks verfügbar sind, ist die Suche beendet. Der Prozess ist einfach tiefer in jeden möglichen Zweig -Pfad, bis er nicht weiter tiefer sein kann und jeder Knoten nur einmal zugegriffen werden kann. Zum obigen Beispiel lautet das Ergebnis der Tiefen-First-Traversal: A, B, D, E, I, C, F, G, H. (vorausgesetzt, die linke Seite des untergeordneten Knotens ist zuerst übrig).
Tiefenpriorität wird verwendet, um jeden Knoten zu durchqueren, und eine Datenstruktur wie ein Haufen ist erforderlich. Das Merkmal von Stack ist es zuerst, zuerst zu gehen und dann zu beenden. Der gesamte Traversalprozess ist wie folgt:
Drücken Sie zuerst den Knoten A in den Haufen, Stapel (a);
Pop -Up den Knoten A und drücken Sie gleichzeitig die Kinderknoten C und B in den Haufen. Zu diesem Zeitpunkt befindet sich B oben auf dem Haufen, Stapel (B, C);
Pop -up -Knoten B und drücken Sie Bs Kinderknoten E und D in den Haufen. Zu diesem Zeitpunkt befindet sich D oben auf dem Haufen, Stapel (d, e, c);
Pop -up -Knoten D, werden keine untergeordneten Knoten eingedrückt, und E befindet sich oben auf dem Haufen, Stapel (e, c);
Pop -up -Knoten E und drücken Sie den Kinderknoten I in Stapel (i, c);
... unten und der endgültige Traversal ist abgeschlossen. Der Java -Code ist ungefähr wie folgt:
public void tiefeThfirst () {stack <map <String, Objekt >> nodestack = new Stack <map <String, Objekt >> (); map <String, Objekt> node = new Hashmap <String, Object> (); nodestack.add (Knoten); while (! nodestack.isempty ()) {node = nodestack.pop (); System.out.println (Knoten); // Holen Sie sich den untergeordneten Knoten des Knotens. Für den binären Baum wird der linke untergeordnete Knoten und den rechten untergeordneten Knoten der Knotenliste <map <String, Objekt >> Kinder = getChildren (Knoten); if (Kinder!2. Breite Priorität
Die englische Abkürzung ist BFS, was bedeutet, dass Breadth FirstSearch. Gemäß dem Prozesstest wird auf jede Knotenschicht zugegriffen, und nach dem Zugriff auf eine Ebene kann jeder Knoten nur einmal darauf zugreifen. Für das obige Beispiel lautet das Ergebnis einer Breite zuerst die Folge: A, B, C, D, E, F, G, H, I (unter der Annahme, dass auf jede Knotenschicht von links nach rechts zugegriffen wird).
Die Priorität der Breite wird verwendet, um jeden Knoten zu durchqueren, und eine Datenstruktur wie eine Warteschlange ist erforderlich. Das Merkmal der Warteschlange ist erstmals, zuerst und in der Tat kann es auch eine doppelte Warteschlange verwenden. Der Unterschied besteht darin, dass Knoten an der ersten Position der Doppel-Warteschlange eingefügt und aufgetaucht werden können. Der gesamte Traversalprozess ist wie folgt:
Fügen Sie zuerst den Knoten A in die Warteschlange ein, Warteschlange (a);
Pop -up -Knoten A und fügen Sie untergeordnete Knoten B und C von A in die Warteschlange ein. Zu diesem Zeitpunkt befindet sich B am Anfang der Warteschlange und C am Ende der Warteschlange, Warteschlange (B, C);
Pop -up den Knoten B und fügen Sie gleichzeitig untergeordnete Knoten D und E von B in die Warteschlange ein. Zu diesem Zeitpunkt befindet sich C am Anfang der Warteschlange und E am Ende der Warteschlange, Warteschlange (C, D, E);
Pop -up -Knoten C und fügen Sie untergeordnete Knoten F, G, H von C in die Warteschlange ein. Zu dieser Zeit steht D an der Spitze der Warteschlange und H am Ende der Warteschlange, Warteschlange (D, E, F, G, H);
Pop -up -Knoten D, D hat keine untergeordneten Knoten, zu diesem Zeitpunkt steht E am Kopf der Warteschlange, H ist am Schwanz der Warteschlange, Warteschlange (E, F, G, H);
... unten und der endgültige Traversal ist abgeschlossen. Der Java -Code ist ungefähr wie folgt:
public void breadfirst () {deque > nodedeque = neuarraydeque > (); Karte node = new Hashmap (); nodedequ.add (Knoten); while (! nodedeque.isempty ()) {node = nodedEqu.peekfirst (); System.out.println (Knoten); // Holen Sie sich den untergeordneten Knoten des Knotens. Für den binären Baum sollen der linke untergeordnete Knoten und der rechte untergeordnete Knoten des Knotens die Liste des Knotens erhalten. > Kinder = Getchildren (Knoten); if (Kinder! }}}} // Die doppelte Warteschlange wird hier verwendet, was der Verwendung der Warteschlange entspricht Zusammenfassen
Das obige ist der Inhalt dieses Artikels über die Beispiele für die Tiefe-First- und Breadth-First-Java-Implementierungscode, und ich hoffe, dass es für alle hilfreich sein wird. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!