Beherrschen Sie den Deep-First-Algorithmus der JavaScript-Baumstruktur in einem Artikel

Was ist ein Baum?

Ich glaube, jeder kennt Bäume , egal ob es sich um Weiden, Pappeln oder Pfirsichbäume handelt, man kann sagen, dass Bäume überall in unserem Leben zu sehen sind eines hierarchischen Modells ,

wie unten gezeigt:

Es gibt viele Anwendungen der Baumstruktur. Beispielsweise kann die Organisationsstruktur eines Unternehmens durch einen Baum dargestellt werden, wie unten gezeigt:

Neben Organisationsstrukturen können auch Stammbäume, Provinzen und Städte usw. mithilfe von Baumstrukturen dargestellt werden.

Baumterminologie

Es gibt viele Begriffe für Bäume, wie unten gezeigt:

• Baum : eine endliche Menge von n (n≥0) Knoten. Wenn n=0 , wird er als leerer
• Baum bezeichnet Der Grad des Knotens A ist 3;
• der Grad
• des Baums ist der maximale Grad unter allen Knoten des Baums. In der obigen Abbildung ist der Grad des Baums beispielsweise 3;
• , auch Blattknoten genannt
• : wie in der Abbildung oben gezeigt; Geschwisterknoten
• : wie
• in der Abbildung oben gezeigt
• ;
• Beispielsweise beträgt die Tiefe des Baums im Bild oben 3;
• die Ebene des E-Knotens beträgt beispielsweise 3 und die Knotenebene ist die Ebene des übergeordneten Knotens + 1, die Ebene des Wurzelknotens beträgt 1 ;
• Pfad : Der Kanal von einem Knoten zu einem anderen Knoten , zum Beispiel der Pfad von A→H. ADH
• : der Abstand von einem Knoten zu einem anderen Knoten , zum Beispiel der Pfad von A→H.

die Baumstruktur in JavaScript

eine der häufigsten Datenstrukturen im Front-End ist, wie z. B. DOM-Baum, kaskadierende Auswahl, Baumkomponenten usw.;

JavaScript stellt keine Baumdatenstruktur bereit, wir können sie jedoch verwenden Objekte und Array, um einen Baum zu simulieren,

wie zum Beispiel der folgende Code:

const tree = {
  Wert: 'A',
  Kinder: [
    {
      Wert: 'B',
      Kinder: [
        { Wert: 'E', Kinder: null },
        { Wert: 'F', Kinder: null },
      ],
    },
    {
      Wert: 'C',
      Kinder: [{ Wert: 'G', Kinder: null }],
    },
    {
      Wert: 'D',
      Kinder: [
        { Wert: 'H', Kinder: null },
        { Wert: 'I', Kinder: null },
      ],
    },
  ],
}

Vorteile von Breiten- und Tiefendurchquerungsalgorithmen:

Tiefendurchquerung

Der sogenannte Tiefendurchquerungsalgorithmus besteht darin, die Zweige des Baums so tief wie möglich zu durchsuchen. Seine Durchquerungsreihenfolge ist wie folgt:

Die Implementierungsidee lautet wie folgt:

• Besuchen Sie den Wurzelknoten;
• setzen Sie die Tiefendurchquerung (Rekursion) children des Wurzelknotens fort.

Der Implementierungscode lautet wie folgt:

function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // Konsistent mit Folgendem // if (root.children) {
  // root.children.forEach(child => {
  //dfs(child)
  // })
  // }
}
dfs(tree) //Dieser Baum ist der zuvor definierte Baum/* Ergebnis A
B
E
F
C
G
D
H
ICH
*/

Wie Sie sehen, stimmt die Reihenfolge mit dem Bild überein, was bedeutet, dass unser Algorithmus kein Problem darstellt.

Breitenpriorität

Die sogenannte Breitenpriorität besteht darin, die Knoten, die dem Wurzelknoten am nächsten liegen, in der folgenden Reihenfolge zu besuchen:

Die Implementierungsidee ist wie folgt:

• Erstellen Sie eine Warteschlange, fügen Sie den Wurzelknoten zur Warteschlange
• hinzu, entfernen Sie den Kopf der Warteschlange und
• fügen Sie children des Kopfs der Warteschlange nacheinander
• hinzu Die Warteschlange ist leer.

Der Implementierungscode lautet wie folgt:

function bfs(root) {
  // 1. Eine neue Warteschlange erstellen und Knoten zur Warteschlange hinzufügen const q = [root]
  // 4 Wiederholen while (q.length > 0) {
    const node = q.shift() // 2 Warteschlangenkopf wird aus der Warteschlange entfernt console.log(node.value)
    // 3 Kinder, die Leiter des Teams, werden dem Team hinzugefügt node.children &&
      node.children.forEach(child => {
        q.push(Kind)
      })
  }
}
bfs(Baum)
/* Ergebnis A
B
C
D
E
F
G
H
ICH
*/

Wie Sie sehen, stimmt die Reihenfolge mit dem Bild überein, was bedeutet, dass unser Algorithmus kein Problem darstellt.