Python實作二元樹
Python實作二元樹可以使用物件導向程式設計的方式，透過定義二元樹節點類別來實現。每個節點包含一個資料元素、左右子節點指標和一些操作方法，如插入節點、尋找節點、刪除節點等。
以下是一個簡單的二元樹實作範例：
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在上述程式碼中，Node類別定義了一個節點，包含資料元素data，以及左右子節點指標left和right。 insert方法用於在二元樹中插入節點，find方法用於尋找二元樹中是否存在特定節點，inorder_traversal方法用於對二元樹進行中序遍歷。
下面是如何使用這個Node類別來建立一個二元樹：
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]
在上述程式碼中，首先建立了一個根節點root，然後使用insert方法向樹插入節點，最後使用find方法尋找節點並使用inorder_traversal方法對二元樹進行中序遍歷。
除了插入、尋找和遍歷方法，二元樹還有其他的操作方法，如刪除節點、判斷是否為二元搜尋樹、計算樹的深度等。下面是一個稍微完整一些的二元樹範例程式碼：
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在這個範例中，我們新增了delete方法來刪除指定的節點；minimum方法來尋找樹中的最小節點；is_bst方法來判斷當前樹是否為二元搜尋樹；height方法來計算樹的深度。
我們可以用以下程式碼來測試新增的方法：
# 创建二叉树
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))這樣我們就完成了一個比較完整的二叉樹的實現，同時也示範如何在Python中使用物件導向編程思想來實作一個資料結構。
最後附上完整的二元樹類別實作程式碼：
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))#在執行程式碼後，可以得到以下輸出：
Deleting node 20 :
[30, 40, 50, 60, 70, 80]
Is it a BST?: True
Tree height: 3
#這個範例包含了插入、查找、刪除、遍歷、判斷是否為二元搜尋樹和計算樹的深度等。
以上是Python二元樹怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
