Verwenden von JS zum Implementieren von Beispielcode für den Algorithmus zur binären Baumdurchquerung

Vorwort

In der Informatik ist ein Baum ein weit verbreiteter abstrakter Datentyp (ADT), also eine Art nichtlinearer Datenstruktur. Bäume werden in der Computerbranche häufig verwendet, insbesondere Binärbäume.

Baumbezogene Konzepte:

• Knoten: Jedes Element wird als Knoten bezeichnet
• Baumwurzel: Wurzelknoten
• Grad: Die Anzahl der untergeordneten Knoten, die ein Knoten enthält, wird als Grad des Knotens bezeichnet.
• Blattknoten: ein Knoten mit Grad 0

1. Binärer Baum

Konzept: Ein Baum, in dem jeder Knoten höchstens zwei Teilbäume enthält, wird als binärer Baum bezeichnet.

1.1. Durchlaufen eines Binärbaums

Es gibt zwei Arten der Durchquerung binärer Bäume: Tiefendurchquerung und Breitendurchquerung. Für die Tiefendurchquerung gibt es drei Durchquerungsmethoden: Pre-Order, In-Order und Post-Order. Bei der Breitendurchquerung handelt es sich um eine Ebenendurchquerung, bei der die einzelnen Schichten der Reihe nach durchlaufen werden.

Die Hauptideen der vier Durchquerungen sind:

• Vorreihenfolge: Besuchen Sie zuerst die Wurzel, dann den linken Teilbaum und schließlich den rechten Teilbaum, DLR.
• Der Reihe nach: Besuchen Sie zuerst den linken Teilbaum, dann die Wurzel und schließlich den rechten Teilbaum, LDR.
• Postorder: Besuchen Sie zuerst den linken Teilbaum, dann den rechten Teilbaum und schließlich die Wurzel LRD.
• Breite: Der Reihe nach Schicht für Schicht durchlaufen.

Beispielsweise wird der Ausdruck a+b*(cd)-e/f durch einen binären Baum dargestellt:

Durchlaufen Sie sie separat:

• Präambel: -+a*b-cd/ef
• In der Reihenfolge: a+b*cde/f
• Nachtrag: abcd-*+ef/-
• Breite: -+/a*efb-cd

1.2. Verwenden Sie js, um einen Binärbaum darzustellen

Wir verwenden js-Objekte, um binäre Bäume darzustellen. Das Objekt hat drei Eigenschaften: links, Wert und rechts, die jeweils den linken Teilbaum, den Wert und den rechten Teilbaum darstellen. Das obige Beispiel a+b*(cd)-e/f kann mit js wie folgt dargestellt werden.

var Baum = {
    Wert: '-',
    links: {
        Wert: '+',
        links: {
            Wert: „a“
        },
        Rechts:
            Wert: '*',
            links: {
                Wert: „b“
            },
            Rechts:
                Wert: '-',
                links: {
                    Wert: „c“
                },
                Rechts:
                    Wert: „d“
                }
            }
        }
    },
    Rechts:
        Wert: '/',
        links: {
            Wert: „e“
        },
        Rechts:
            Wert: „d“
        }
    }
}

1.3 Pre-Order-Traversal-Algorithmus

Vorwort: Es gibt zwei Methoden. Die erste ist sehr einfach und besteht darin, direkt Rekursion zu verwenden.

Funktion Vorbestellung(Baumknoten) {
  wenn(Baumknoten) {
    console.log(treeNode.value); // Ausdrucken bedeutet, diesen Knoten zu besuchen preOrder(treeNode.left);
    vorBestellen(treeNode.right);
  }
}

Der Algorithmus ist sehr einfach. Zuerst wird der Stammknoten durchlaufen, dann wird der linke Teilbaum rekursiv durchlaufen. Nachdem der linke Teilbaum durchlaufen wurde, wird der rechte Teilbaum rekursiv durchlaufen.

Die zweite nicht-rekursive Durchquerung

Funktion Vorbestellung(Baumknoten) {
  wenn(Baumknoten) {
    var stack = [treeNode]; //Den binären Baum in den Stapel schieben while (stack.length !== 0) {
      treeNode = stack.pop(); // Holen Sie sich die Spitze des Stapels document.getElementById('text').appendChild(document.createTextNode(treeNode.value)); // Besuchen Sie den Knoten if(treeNode.right) stack.push(treeNode.right); // Schieben Sie den rechten Teilbaum in den Stapel if(treeNode.left) stack.push(treeNode.left); // Schieben Sie den linken Teilbaum in den Stapel }
  }
}

Die zweite Möglichkeit besteht darin, die Idee eines Stapels zu verwenden. Wie wir alle wissen, ist ein Stapel eine First-In-Last-Out-Datenstruktur. Wir schieben zuerst den Stammknoten in den Stapel, nehmen dann die Spitze des Stapels, besuchen den Stammknoten und schieben jeweils den rechten und linken Teilbaum in den Stapel. Die rechte Seite muss zuerst in den Stapel geschoben werden, da wir zuerst von links her besuchen müssen. Daher wird der rechte Teilbaum zuerst in den Stapel geschoben. Anschließend führen wir eine Schleife aus, um den Stapel herauszunehmen, bis der Stapel leer ist.

1.4. In-Order-Traversal-Algorithmus

In-Order-Rekursiver Algorithmus:

Funktion InOrder(Baumknoten) {
    wenn(Baumknoten) {
        InOrder(treeNode.links);
        document.getElementById('text').appendChild(document.createTextNode(treeNode.value));
        InOrder(treeNode.rechts);
    }
}

Dieselbe Idee wie der rekursive Pre-Order-Algorithmus, aber die Position der besuchten Knoten ist anders

Zweiter Typ:

Funktion InOrder(Knoten) {
  wenn(Knoten) {
    var stack = []; // Einen leeren Stapel erstellen // Wenn der Stapel oder der Knoten nicht leer ist, durchlaufe while (stack.length !== 0 || node) { 
      if (node) { //Wenn der Knoten nicht leer ist stack.push(node); //Den Knoten in den Stapel schieben node = node.left; //Den linken Teilbaum als aktuellen Knoten verwenden } else { //Der linke Teilbaum ist leer, d. h. es gibt keinen linken Teilbaum node = stack.pop(); //Den Knoten herausnehmen document.getElementById('text').appendChild(document.createTextNode(node.value));
          node = node.right; //Verwende den rechten Knoten als aktuellen Knoten}
    }
  }
}

Die Idee des nicht rekursiven In-Order-Algorithmus besteht darin, den aktuellen Knoten in den Stapel zu schieben, dann den linken Teilbaum zu durchlaufen, wenn der linke Teilbaum vorhanden ist, ihn weiter in den Stapel zu schieben, bis der linke Teilbaum leer ist, den vorherigen Knoten zu besuchen und dann den rechten Teilbaum in den Stapel zu schieben.

1.5. Post-Order-Traversal-Algorithmus

Der erste: rekursiver Durchlaufalgorithmus

Funktion postOrder(Knoten) {
    if (node) { //Beurteilen, ob der Binärbaum leer ist postOrder(node.left); //Den linken Teilbaum rekursiv durchlaufen postOrder(node.right); //Den rechten Teilbaum rekursiv durchlaufen document.getElementById('text').appendChild(document.createTextNode(node.value));
    }
}

Zweitens: nicht-rekursiver Durchquerungsalgorithmus

Funktion postOrder(Knoten) {
    if (node) { //Beurteilen, ob der Binärbaum leer istvar stack = [node]; //Den Binärbaum in den Stapel schiebenvar tmp = null; //Cache-Variablen definierenwhile (stack.length !== 0) { //Wenn der Stapel nicht leer ist, durchlaufe tmp = stack[stack.length - 1]; //Den obersten Wert des Stapels in tmp speichernif (tmp.left && node !== tmp.left && node !== tmp.right) { //Wenn ein linker Teilbaum vorhanden ist, soll node !== tmp.left && node !== tmp.right vermeiden, dass der linke und der rechte Teilbaum wiederholt in den Stapel geschoben werdenstack.push(tmp.left); //Den Knoten des linken Teilbaums in den Stapel schieben} else if (tmp.right && node !== tmp.right) { //Wenn der Knoten einen rechten Teilbaum hatstack.push(tmp.right); //Den rechten Teilbaum in den Stapel schieben} else {
                document.getElementById('text').appendChild(document.createTextNode(stack.pop().value));
                Knoten = tmp;
            }
        }
    }
}

Hier wird eine temporäre Variable verwendet, um die zuletzt gepoppten und gepushten Knoten aufzuzeichnen. Die Idee besteht darin, zuerst den Wurzelknoten und den linken Baum in den Stapel zu schieben, dann den linken Baum herauszunehmen, den rechten Baum zu schieben, ihn herauszunehmen und schließlich den Wurzelknoten zu nehmen.

Nachfolgend wird der Prozess der Durchquerung des vorherigen Binärbaums mit diesem Algorithmus beschrieben.

Stapel temporärer Knoten drucken Initiale: - null -
Runde 1: -+ - -
Runde 2: -+a + -
Runde 3: -+ a a a
Runde 4: -+* + a
Runde 5: -+*b * a
Runde 6: -+* b b b
Runde 7: -+*- * b
Runde 8: -+*-c - b
Runde 9: -+*- c c c
Runde 10: -+*-d - c
Runde 11: -+*- d d d
Runde 12: -+* - - -
Runde 13: -+ * * *
Runde 14: - + + +
Runde 15: -/-+
Runde 16: -/e / +
Runde 17: -/ e e e
Runde 18: -/f / e
Runde 19: -/ f f f
Runde 20: - / / /
Runde 21: - - -

Ergebnis: abcd-*+ef/-

1.6. Schicht-für-Schicht-Durchquerungsalgorithmus

Funktion widththTraversal(Knoten) {
    if (node) { //Beurteilen, ob der Binärbaum leer istvar que = [node]; //Den Binärbaum in die Warteschlange stellenwhile (que.length !== 0) { //Beurteilen, ob die Warteschlange leer istnode = que.shift(); //Einen Knoten aus der Warteschlange nehmendocument.getElementById('text').appendChild(document.createTextNode(node.value)); //Den Wert des genommenen Knotens im Array speichernif (node.left) que.push(node.left); //Wenn der linke Teilbaum existiert, den linken Teilbaum in die Warteschlange stellenif (node.right) que.push(node.right); //Wenn der rechte Teilbaum existiert, den rechten Teilbaum in die Warteschlange stellen}
    }
}

Verwenden Sie ein Array, um eine Warteschlange zu simulieren, und fügen Sie zuerst den Stammknoten in die Warteschlange ein. Wenn die Warteschlange nicht leer ist, führen Sie die Schleife aus: Nehmen Sie einen Knoten aus der Warteschlange. Wenn der Knoten einen linken Teilbaum hat, speichern Sie den linken Teilbaum des Knotens in der Warteschlange. Wenn der Knoten einen rechten Teilbaum hat, speichern Sie den rechten Teilbaum des Knotens in der Warteschlange.

2. Fragen zum Algorithmus

1.1. Maximale Tiefe eines Binärbaums

Bestimmen Sie die maximale Tiefe eines gegebenen Binärbaums.

Die Tiefe eines binären Baums ist die Anzahl der Knoten auf dem längsten Pfad vom Wurzelknoten zum am weitesten entfernten Blattknoten.

Beispielsweise gibt der folgende Binärbaum eine Tiefe von 3 zurück.

3
/ \
9 20
/ \
15 7

const Baum = {
Wert: 3,
links: {
Wert: 9
},
Rechts:
Wert: 20,
links: { Wert: 15 },
rechts: { Wert: 9 }
}
}

Rekursiver Algorithmus: Die Idee des rekursiven Algorithmus ist sehr einfach: Holen Sie sich zuerst die tiefste Schicht des linken Teilbaums, dann die tiefste Schicht des rechten Teilbaums und der Maximalwert davon ist die Tiefe des Baums.

var maxDepth = Funktion(Wurzel) {
  wenn (!root) {
    gebe 0 zurück;
  }
  const leftDeep = maxDepth(root.left) + 1;
  const rightDeep = maxDepth(root.right) + 1;
  returniere Math.max(linkesTief, rechtesTief);
};
/*
maxDepth(Wurzel) = maxDepth(Wurzel.links) + 1 = 2
maxDepth(root.links) = maxDepth(root.links.links) + 1 = 1
maxDepth(root.links.links) = 0;

maxDepth(Wurzel) = maxDepth(Wurzel.rechts) + 1 = 3
maxDepth(root.rechts) = maxDepth(root.rechts.rechts) + 1 = 2
maxDepth(root.rechts.rechts) = maxDepth(root.rechts.rechts.rechts) + 1 = 1
maxDepth(root.rechts.rechts.rechts) = 0
*/

1.2. Alle Pfade eines Binärbaums

Geben Sie bei einem binären Baum alle Pfade vom Wurzelknoten zu einem Blattknoten zurück.

Zum Beispiel:

3
/ \
9 20
/ \
15 7

Gibt zurück: ['3->9', '3->20->15', '3->20->7']

Verwenden der rekursiven Methode:

var binaryTreePaths = Funktion(Wurzel) {
  wenn (!root) return [];
  Konstantenres = [];
  Funktion dfs(aktueller Knoten, aktueller Pfad) {
    wenn(!curNode.left && !curNode.right) {
      res.push(aktueller Pfad);
    }
    wenn(aktuellerNode.links) {
      dfs(curNode.left, `${curPath}->${curNode.left.value}`)
    }
    wenn(aktuellerNode.rechts) {
      dfs(curNode.right, `${curPath}->${curNode.right.value}`)
    }
  }
  dfs(root, `${root.value}`);
  Rückgabewert;
};

Zusammenfassen

Dies ist das Ende dieses Artikels über die Verwendung von JS zur Implementierung eines binären Baumdurchlaufalgorithmus. Weitere relevante Inhalte zum binären Baumdurchlaufalgorithmus von JS finden Sie in früheren Artikeln auf 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!