suchen
HeimBackend-EntwicklungPython-TutorialSo implementieren Sie einen Binärbaum in Python

Python implementiert einen Binärbaum

So implementieren Sie einen Binärbaum in Python

Python kann einen Binärbaum mithilfe objektorientierter Programmierung implementieren, indem es eine Binärbaumknotenklasse definiert. Jeder Knoten enthält ein Datenelement, linke und rechte untergeordnete Knotenzeiger und einige Operationsmethoden, wie z. B. das Einfügen von Knoten, das Suchen von Knoten, das Löschen von Knoten usw.

Das Folgende ist ein einfaches Implementierungsbeispiel für einen Binärbaum:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return str(data) + " Not Found"
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return str(data) + " Not Found"
            return self.right.find(data)
        else:
            return str(self.data) + " is found"

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

Im obigen Code definiert die Node-Klasse einen Knoten, einschließlich der Datenelementdaten und der linken und rechten untergeordneten Knotenzeiger links und rechts. Mit der Methode insert werden Knoten in einen Binärbaum eingefügt, mit der Methode find wird ermittelt, ob ein bestimmter Knoten im Binärbaum vorhanden ist, und mit der Methode inorder_traversal wird der Binärbaum in der richtigen Reihenfolge durchlaufen.

So verwenden Sie diese Node-Klasse, um einen Binärbaum zu erstellen:

root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 查找节点

print(root.find(70)) # Output: 70 is found
print(root.find(90)) # Output: 90 Not Found

# 中序遍历
print(root.inorder_traversal(root)) # Output: [20, 30, 40, 50, 60, 70, 80]

Im obigen Code wird zuerst ein Wurzelknoten root erstellt, dann wird die Einfügungsmethode verwendet, um den Knoten in den Baum einzufügen, und schließlich wird die Suchmethode verwendet wird verwendet, um den Knoten zu finden, und die Methode inorder_traversal wird verwendet. Führen Sie eine Inorder-Traversierung eines Binärbaums durch.

Neben den Einfügungs-, Such- und Durchlaufmethoden verfügen Binärbäume auch über andere Betriebsmethoden, z. B. das Löschen von Knoten, das Bestimmen, ob es sich um einen binären Suchbaum handelt, das Berechnen der Tiefe des Baums usw. Das Folgende ist ein etwas vollständigerer Beispielcode für einen Binärbaum:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

In diesem Beispiel haben wir die Methode delete hinzugefügt, um den angegebenen Knoten zu löschen; die Methode is_bst, um zu bestimmen, ob der Der aktuelle Baum ist eine binäre Gabelsuchbaumhöhenmethode zur Berechnung der Tiefe des Baums.

Wir können den folgenden Code verwenden, um die neue Methode zu testen:

# 创建二叉树
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 删除节点
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))

# 判断是否为二叉搜索树
print("Is it a BST?:", root.is_bst())

# 计算树的深度
print("Tree height:", root.height(root))

Auf diese Weise haben wir eine relativ vollständige Binärbaumimplementierung abgeschlossen und außerdem gezeigt, wie objektorientierte Programmierideen in Python zum Implementieren einer Datenstruktur verwendet werden können.

Schließlich ist der vollständige Implementierungscode der Binärbaumklasse angehängt:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

if __name__ == '__main__':
    # 创建二叉树
    root = Node(50)
    root.insert(30)
    root.insert(20)
    root.insert(40)
    root.insert(70)
    root.insert(60)
    root.insert(80)

    # 删除节点
    print("Deleting node 20:")
    root.delete(20)
    print(root.inorder_traversal(root))

    # 判断是否为二叉搜索树
    print("Is it a BST?:", root.is_bst())

    # 计算树的深度
    print("Tree height:", root.height(root))

Nachdem Sie den Code ausgeführt haben, können Sie die folgende Ausgabe erhalten:

Knoten 20 löschen:
[30, 40, 50, 60, 70, 80]
Ist es ein BST?: True
Baumhöhe: 3

Dieses Beispiel umfasst Einfügen, Suchen, Löschen, Durchlaufen, Bestimmen, ob es sich um einen binären Suchbaum handelt, Berechnen der Tiefe des Baums usw.

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

Stellungnahme
Dieser Artikel ist reproduziert unter:亿速云. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen
Python lernen: Ist 2 Stunden tägliches Studium ausreichend?Python lernen: Ist 2 Stunden tägliches Studium ausreichend?Apr 18, 2025 am 12:22 AM

Ist es genug, um Python für zwei Stunden am Tag zu lernen? Es hängt von Ihren Zielen und Lernmethoden ab. 1) Entwickeln Sie einen klaren Lernplan, 2) Wählen Sie geeignete Lernressourcen und -methoden aus, 3) praktizieren und prüfen und konsolidieren Sie praktische Praxis und Überprüfung und konsolidieren Sie und Sie können die Grundkenntnisse und die erweiterten Funktionen von Python während dieser Zeit nach und nach beherrschen.

Python für die Webentwicklung: SchlüsselanwendungenPython für die Webentwicklung: SchlüsselanwendungenApr 18, 2025 am 12:20 AM

Zu den wichtigsten Anwendungen von Python in der Webentwicklung gehören die Verwendung von Django- und Flask -Frameworks, API -Entwicklung, Datenanalyse und Visualisierung, maschinelles Lernen und KI sowie Leistungsoptimierung. 1. Django und Flask Framework: Django eignet sich für die schnelle Entwicklung komplexer Anwendungen, und Flask eignet sich für kleine oder hochmobile Projekte. 2. API -Entwicklung: Verwenden Sie Flask oder Djangorestframework, um RESTFUFFUPI zu erstellen. 3. Datenanalyse und Visualisierung: Verwenden Sie Python, um Daten zu verarbeiten und über die Webschnittstelle anzuzeigen. 4. Maschinelles Lernen und KI: Python wird verwendet, um intelligente Webanwendungen zu erstellen. 5. Leistungsoptimierung: optimiert durch asynchrones Programmieren, Caching und Code

Python vs. C: Erforschung von Leistung und Effizienz erforschenPython vs. C: Erforschung von Leistung und Effizienz erforschenApr 18, 2025 am 12:20 AM

Python ist in der Entwicklungseffizienz besser als C, aber C ist in der Ausführungsleistung höher. 1. Pythons prägnante Syntax und reiche Bibliotheken verbessern die Entwicklungseffizienz. 2. Die Kompilierungsmerkmale von Compilation und die Hardwarekontrolle verbessern die Ausführungsleistung. Bei einer Auswahl müssen Sie die Entwicklungsgeschwindigkeit und die Ausführungseffizienz basierend auf den Projektanforderungen abwägen.

Python in Aktion: Beispiele in realer WeltPython in Aktion: Beispiele in realer WeltApr 18, 2025 am 12:18 AM

Zu den realen Anwendungen von Python gehören Datenanalysen, Webentwicklung, künstliche Intelligenz und Automatisierung. 1) In der Datenanalyse verwendet Python Pandas und Matplotlib, um Daten zu verarbeiten und zu visualisieren. 2) In der Webentwicklung vereinfachen Django und Flask Frameworks die Erstellung von Webanwendungen. 3) Auf dem Gebiet der künstlichen Intelligenz werden Tensorflow und Pytorch verwendet, um Modelle zu bauen und zu trainieren. 4) In Bezug auf die Automatisierung können Python -Skripte für Aufgaben wie das Kopieren von Dateien verwendet werden.

Pythons Hauptnutzung: ein umfassender ÜberblickPythons Hauptnutzung: ein umfassender ÜberblickApr 18, 2025 am 12:18 AM

Python wird häufig in den Bereichen Data Science, Web Development und Automation Scripting verwendet. 1) In der Datenwissenschaft vereinfacht Python die Datenverarbeitung und -analyse durch Bibliotheken wie Numpy und Pandas. 2) In der Webentwicklung ermöglichen die Django- und Flask -Frameworks Entwicklern, Anwendungen schnell zu erstellen. 3) In automatisierten Skripten machen Pythons Einfachheit und Standardbibliothek es ideal.

Der Hauptzweck von Python: Flexibilität und BenutzerfreundlichkeitDer Hauptzweck von Python: Flexibilität und BenutzerfreundlichkeitApr 17, 2025 am 12:14 AM

Die Flexibilität von Python spiegelt sich in Multi-Paradigm-Unterstützung und dynamischen Typsystemen wider, während eine einfache Syntax und eine reichhaltige Standardbibliothek stammt. 1. Flexibilität: Unterstützt objektorientierte, funktionale und prozedurale Programmierung und dynamische Typsysteme verbessern die Entwicklungseffizienz. 2. Benutzerfreundlichkeit: Die Grammatik liegt nahe an der natürlichen Sprache, die Standardbibliothek deckt eine breite Palette von Funktionen ab und vereinfacht den Entwicklungsprozess.

Python: Die Kraft der vielseitigen ProgrammierungPython: Die Kraft der vielseitigen ProgrammierungApr 17, 2025 am 12:09 AM

Python ist für seine Einfachheit und Kraft sehr beliebt, geeignet für alle Anforderungen von Anfängern bis hin zu fortgeschrittenen Entwicklern. Seine Vielseitigkeit spiegelt sich in: 1) leicht zu erlernen und benutzten, einfachen Syntax; 2) Reiche Bibliotheken und Frameworks wie Numpy, Pandas usw.; 3) plattformübergreifende Unterstützung, die auf einer Vielzahl von Betriebssystemen betrieben werden kann; 4) Geeignet für Skript- und Automatisierungsaufgaben zur Verbesserung der Arbeitseffizienz.

Python in 2 Stunden am Tag lernen: Ein praktischer LeitfadenPython in 2 Stunden am Tag lernen: Ein praktischer LeitfadenApr 17, 2025 am 12:05 AM

Ja, lernen Sie Python in zwei Stunden am Tag. 1. Entwickeln Sie einen angemessenen Studienplan, 2. Wählen Sie die richtigen Lernressourcen aus, 3. Konsolidieren Sie das durch die Praxis erlernte Wissen. Diese Schritte können Ihnen helfen, Python in kurzer Zeit zu meistern.

See all articles

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
1 Monate vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
1 Monate vorBy尊渡假赌尊渡假赌尊渡假赌
Will R.E.P.O. Crossplay haben?
1 Monate vorBy尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

MinGW – Minimalistisches GNU für Windows

MinGW – Minimalistisches GNU für Windows

Dieses Projekt wird derzeit auf osdn.net/projects/mingw migriert. Sie können uns dort weiterhin folgen. MinGW: Eine native Windows-Portierung der GNU Compiler Collection (GCC), frei verteilbare Importbibliotheken und Header-Dateien zum Erstellen nativer Windows-Anwendungen, einschließlich Erweiterungen der MSVC-Laufzeit zur Unterstützung der C99-Funktionalität. Die gesamte MinGW-Software kann auf 64-Bit-Windows-Plattformen ausgeführt werden.

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

WebStorm-Mac-Version

WebStorm-Mac-Version

Nützliche JavaScript-Entwicklungstools

Dreamweaver Mac

Dreamweaver Mac

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)