Python implementiert einen Binärbaum
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 resNach dem Login kopieren
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]
Nach dem Login kopieren
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 resNach dem Login kopieren
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))Nach dem Login kopieren
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))Nach dem Login kopieren
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!
