Erkunden der Baumdurchquerung in JavaScript: Inorder, Preorder und Postorder mit Beispielen

Baumdurchquerung ist ein grundlegendes Konzept in der Informatik, bei dem jeder Knoten in einer Baumdatenstruktur systematisch besucht wird. Durch die Baumdurchquerung können wir die Knoten in einer vorgegebenen Reihenfolge verarbeiten und so Vorgänge wie das Suchen, Sortieren und Auswerten von Ausdrücken erleichtern.

In diesem Artikel werden wir drei der am häufigsten verwendeten Methoden zur Baumdurchquerung untersuchen: Inorder, Preorder und Postorder.

Durch klare und prägnante Beispiele, die in JavaScript implementiert sind, erhalten Sie ein solides Verständnis dieser Traversierungstechniken.

Definition der Baumstruktur

Bevor wir uns mit den Baumdurchlaufalgorithmen befassen, definieren wir die Struktur, die wir für den Binärbaum verwenden werden. Der Baum besteht aus Knoten, wobei jeder Knoten einen Wert und Verweise auf seine linken und rechten untergeordneten Knoten enthält.

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

Nachdem wir nun die Baumstruktur definiert haben, können wir mit der Erkundung der drei Baumdurchquerungsmethoden fortfahren.

Inorder-Durchquerung

Die Inorder-Traversierung folgt dem nächsten Muster des Besuchs von Knoten in einem Binärbaum – der Algorithmus durchläuft zuerst den linken Teilbaum, besucht dann den aktuellen Knoten und durchläuft schließlich den rechten Teilbaum. Dadurch wird sichergestellt, dass die Knoten in aufsteigender Reihenfolge besucht werden, wenn der Baum eine sortierte Datenstruktur darstellt.

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

Rekursive Inorder-Traversierung

1. Überprüfen Sie, ob der aktuelle Knoten null ist. Wenn ja, kehren Sie zurück.

   
   

2. Rufen Sie die Funktion im linken Teilbaum rekursiv auf.

   
   

3. Besuchen Sie den aktuellen Knoten.

   
   

4. Rufen Sie die Funktion rekursiv im rechten Teilbaum auf.

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

Nicht rekursiver Inorder-Traversal

1. Initialisieren Sie einen leeren Stapel und setzen Sie den aktuellen Knoten auf die Wurzel des Baums.

   
   

2. Iterieren Sie, während der Stapel nicht leer ist oder der aktuelle Knoten nicht null ist.

   • Schieben Sie alle linken Knoten auf den Stapel, bis ein linker untergeordneter Knoten von Null erreicht ist.

   • Entfernen Sie einen Knoten vom Stapel, besuchen Sie ihn und setzen Sie den aktuellen Knoten auf seinen rechten untergeordneten Knoten.

     
     

3. Wiederholen Sie Schritt 2, bis der Stapel leer ist und der aktuelle Knoten null ist.

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

Traversal vorbestellen

Bei der Durchquerung vor der Bestellung besucht der Algorithmus zuerst den aktuellen Knoten, durchläuft dann den linken Teilbaum und schließlich den rechten Teilbaum. Durch diese Reihenfolge wird sichergestellt, dass die Knoten von oben nach unten besucht werden, beginnend bei der Wurzel und in Richtung der Blätter.

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

Rekursive Vorbestellungsdurchquerung

1. Überprüfen Sie, ob der aktuelle Knoten null ist. Wenn ja, kehren Sie zurück.

   
   

2. Besuchen Sie den aktuellen Knoten.

   
   

3. Rufen Sie die Funktion im linken Teilbaum rekursiv auf.

   
   

4. Rufen Sie die Funktion rekursiv im rechten Teilbaum auf.

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

Nicht rekursiver Preorder-Traversal

1. Beginnen Sie mit einem leeren Stapel und schieben Sie den Wurzelknoten auf den Stapel.

   
   

2. Initialisieren Sie ein leeres Array, um das Ergebnis der Vorbestellungsdurchquerung zu speichern.

   
   

3. Geben Sie eine While-Schleife ein, die so lange läuft, bis der Stapel leer ist.

   
   

4. Entfernen Sie einen Knoten vom Stapel und besuchen Sie ihn, indem Sie seinen Wert zum Ergebnisarray hinzufügen.

   
   

5. Wenn der Knoten ein rechtes Kind hat, schieben Sie das rechte Kind auf den Stapel.

   
   

6. Wenn der Knoten ein linkes Kind hat, schieben Sie das linke Kind auf den Stapel.

   
   

7. Wiederholen Sie die Schritte 3–6, bis der Stapel leer ist.

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

Postorder-Traversal

Bei dieser Durchquerung durchläuft der Algorithmus zuerst den linken Teilbaum, dann den rechten Teilbaum und besucht schließlich den aktuellen Knoten. Durch diese Reihenfolge wird sichergestellt, dass die Knoten von unten nach oben besucht werden, beginnend bei den Blättern und in Richtung Wurzel.

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

Rekursive Postorder-Traversierung

1. Überprüfen Sie, ob der aktuelle Knoten null ist. Wenn ja, kehren Sie zurück.

   
   

2. Rufen Sie die Funktion im linken Teilbaum rekursiv auf.

   
   

3. Rufen Sie die Funktion rekursiv im rechten Teilbaum auf.

   
   

4. Besuchen Sie den aktuellen Knoten.

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

Nicht rekursiver Postorder-Traversal

1. Beginnen Sie mit einem leeren Stapel und schieben Sie den Wurzelknoten auf den Stapel.

   
   

2. Initialisieren Sie ein leeres Array, um das Postorder-Traversal-Ergebnis zu speichern.

   
   

3. Geben Sie eine While-Schleife ein, die so lange läuft, bis der Stapel leer ist.

   
   

4. Holen Sie sich den obersten Knoten vom Stapel (ohne ihn zu entfernen).

   
   

5. Wenn der Knoten ein linkes Kind hat, schieben Sie das linke Kind auf den Stapel und setzen Sie das linke Kind des aktuellen Knotens auf Null.

   
   

6. Wenn der Knoten ein rechtes Kind hat, schieben Sie das rechte Kind auf den Stapel und setzen Sie das rechte Kind des aktuellen Knotens auf Null.

   
   

7. Wenn der Knoten weder ein linkes noch ein rechtes Kind hat, handelt es sich um einen Blattknoten. Entfernen Sie den Knoten vom Stapel und fügen Sie seinen Wert zum Ergebnisarray hinzu.

   
   

8. Wiederholen Sie die Schritte 4–7, bis der Stapel leer ist.

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

Abschluss

Ich hoffe, dass Sie jetzt ein klares Verständnis für die Unterschiede zwischen Inorder-, Preorder- und Postorder-Traversal in JavaScript haben. Mit den bereitgestellten Kenntnissen und Beispielen sind Sie nun in der Lage, diese Techniken effektiv auf Ihre eigenen Aufgaben und Projekte anzuwenden.