So implementieren Sie die Binärbaum-Traversierung mit Python

Als häufig verwendete Datenstruktur werden Binärbäume häufig zum Speichern, Suchen und Sortieren von Daten verwendet. Das Durchlaufen eines Binärbaums ist eine der häufigsten Operationen. Als einfache und benutzerfreundliche Programmiersprache verfügt Python über viele Methoden zur Implementierung der Binärbaumdurchquerung. In diesem Artikel wird erläutert, wie Sie mit Python die Durchquerung eines Binärbaums vor, in der Reihenfolge und nach der Bestellung implementieren.

Grundlagen von Binärbäumen

Bevor wir lernen, wie man einen Binärbaum durchquert, müssen wir die Grundkonzepte von Binärbäumen verstehen. Ein Binärbaum besteht aus Knoten, jeder Knoten hat einen Wert und zwei untergeordnete Elemente (linkes untergeordnetes und rechtes untergeordnetes Element). Die Kinder eines Knotens können leer sein.

Binärbaum-Traversierung

Binärbaum-Traversierung bezieht sich auf den Besuch aller Knoten im Binärbaum in einer bestimmten Reihenfolge. Es gibt drei häufig verwendete Durchquerungsmethoden: Durchquerung vor der Bestellung, Durchquerung in der Reihenfolge und Durchquerung nach der Bestellung.

Durchquerung vor der Bestellung

Die Reihenfolge der Durchquerung vor der Bestellung ist der Wurzelknoten, der linke Teilbaum und der rechte Teilbaum. In einer bestimmten Implementierung können Sie zunächst den Wert des Wurzelknotens ausgeben und dann den linken Teilbaum und den rechten Teilbaum rekursiv durchlaufen.

Das Folgende ist die Python-Code-Implementierung:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

Durchlauf in der richtigen Reihenfolge

Die Reihenfolge des Durchlaufs in der richtigen Reihenfolge ist linker Teilbaum, Wurzelknoten und rechter Teilbaum. In einer bestimmten Implementierung ist es erforderlich, den linken Teilbaum rekursiv zu durchlaufen, den Wert des Wurzelknotens auszugeben und dann den rechten Teilbaum rekursiv zu durchlaufen.

Das Folgende ist die Python-Code-Implementierung:

def inorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += inorderTraversal(root.left)
    res.append(root.val)
    res += inorderTraversal(root.right)
    return res

Post-Order-Traversal

Die Reihenfolge des Post-Order-Traversals ist linker Teilbaum, rechter Teilbaum und Wurzelknoten. In einer bestimmten Implementierung ist es erforderlich, den linken Teilbaum und den rechten Teilbaum rekursiv zu durchlaufen und schließlich den Wert des Wurzelknotens auszugeben.

Das Folgende ist die Python-Code-Implementierung:

def postorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += postorderTraversal(root.left)
    res += postorderTraversal(root.right)
    res.append(root.val)
    return res

Zusammenfassung

In Python kann bei Verwendung der binären Baumdurchquerung die Vorbestellungs-, In-Reihenfolge- und Nachbestellungs-Durchquerung durch Rekursion erreicht werden. Neben der Rekursion können auch Methoden wie Stack- und Breitensuche verwendet werden. Die Beherrschung der Methode der Binärbaumdurchquerung wird für die tägliche Programmierarbeit sehr nützlich sein.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Binärbaum-Traversierung mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!