Inwiefern ähnelt die Breitendurchquerung der Durchquerung eines Binärbaums?

Breadth-First-Traversal ähnelt dem Level-Traversal eines Binärbaums. Die Breitensuche beginnt am Wurzelknoten und durchsucht und durchläuft die Breite des Baums, d. h. sie durchläuft jede Ebene nacheinander von oben nach unten und in jeder Ebene von links nach rechts (oder von rechts). nach links), um auf Knoten zuzugreifen, und nach dem Zugriff auf eine Ebene die nächste Ebene betreten, bis kein Knoten mehr erreichbar ist.

Die Breitensuche (eigentlich eine hierarchische Durchquerung eines Binärbaums), auch Breitensuche oder Horizontalsuche genannt, beginnt am Wurzelknoten eine Suchdurchquerung entlang der Breite des Baums.

Besuchen Sie in jeder Ebene die Knoten von links nach rechts (oder von rechts nach links) und betreten Sie die nächste Ebene, bis kein Knoten mehr erreichbar ist .

Die Durchlaufreihenfolge des obigen Binärbaums lautet: ABCDEFG. Warteschlangen können zur Implementierung der Breitensuche verwendet werden.

Breite-First-Suchalgorithmus:

Behält alle Knoten und nimmt viel Platz ein; keine Backtracking-Operationen (d. h. keine Push- oder Pop-Operationen), hohe Laufgeschwindigkeit .

Der Breitensuchalgorithmus muss im Allgemeinen alle generierten Knoten speichern, und der belegte Speicherplatz ist viel größer als der der Tiefensuche. Daher müssen beim Programmentwurf Überlauf und Speicherplatz eingespart werden berücksichtigt. Allerdings verfügt die Breitensuche im Allgemeinen nicht über Backtracking-Operationen, also Push- und Pop-Operationen, sodass sie schneller ausgeführt wird als die Tiefensuche.

Beispiel:

Die Prozessinspektion besteht darin, jede Knotenschicht nacheinander zu besuchen und die Schicht Go zu vervollständigen zur nächsten Ebene, und jeder Knoten kann nur einmal besucht werden. Für das obige Beispiel sind die Ergebnisse der Breitendurchquerung: A, B, C, D, E, F, G, H, I (unter der Annahme, dass auf Knoten in jeder Schicht von links nach rechts zugegriffen wird).

Breite-zuerst-Durchquerung jedes Knotens erfordert die Verwendung einer Warteschlangen-Datenstruktur. Die Eigenschaft der Warteschlange ist „First-In-First-Out“. Tatsächlich kann auch eine Double-Ended-Warteschlange verwendet werden Der Unterschied besteht darin, dass die erste Position einer doppelseitigen Warteschlange eingefügt und der Knoten geöffnet werden kann. Der gesamte Durchlaufvorgang läuft wie folgt ab:

Fügen Sie zuerst den A-Knoten in die Warteschlange ein, Warteschlange (A);

Öffnen Sie den A-Knoten und fügen Sie die untergeordneten Knoten B und von A ein C in die Warteschlange. Zu diesem Zeitpunkt befindet sich B am Anfang der Warteschlange, C am Ende der Warteschlange, Warteschlange (B, C);

Fügt den B-Knoten ein und fügt die untergeordneten Knoten von B ein D und E in die Warteschlange, zu diesem Zeitpunkt befindet sich C am Anfang der Warteschlange, E befindet sich am Ende der Warteschlange, Warteschlange (C, D, E);

Öffnet den C-Knoten und fügt den ein Untergeordnete Knoten F, G und H von C in die Warteschlange. Zu diesem Zeitpunkt befindet sich D am Anfang der Warteschlange und H am Ende der Warteschlange, Warteschlange (D, E, F, G,). H);

Öffnen Sie den D-Knoten, D hat keine untergeordneten Knoten, zu diesem Zeitpunkt befindet sich E am Anfang der Warteschlange, H befindet sich am Ende der Warteschlange, Warteschlange (E, F, G, H );

... gehen Sie nacheinander nach unten und schließlich ist die Durchquerung abgeschlossen

Der Java-Code lautet ungefähr wie folgt:

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ArrayList<Integer> wide(TreeNode root) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(root==null)
            return lists;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            lists.add(node.val);
		}
        return lists;
    }
}

Für weitere verwandte Kenntnisse , besuchen Sie bitte: PHP chinesische Website!

Das obige ist der detaillierte Inhalt vonInwiefern ähnelt die Breitendurchquerung der Durchquerung eines Binärbaums?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!