Python二元樹怎麼實現
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中文網其他相關文章！
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
Video Face Swap
使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！
熱門文章
熱工具
記事本++7.3.1
好用且免費的程式碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
強大的PHP整合開發環境
Dreamweaver CS6
視覺化網頁開發工具
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
PHP和Python：解釋了不同的範例
Apr 18, 2025 am 12:26 AM
PHP主要是過程式編程，但也支持面向對象編程（OOP）；Python支持多種範式，包括OOP、函數式和過程式編程。 PHP適合web開發，Python適用於多種應用，如數據分析和機器學習。
在PHP和Python之間進行選擇：指南
Apr 18, 2025 am 12:24 AM
PHP適合網頁開發和快速原型開發，Python適用於數據科學和機器學習。 1.PHP用於動態網頁開發，語法簡單，適合快速開發。 2.Python語法簡潔，適用於多領域，庫生態系統強大。
PHP和Python：深入了解他們的歷史
Apr 18, 2025 am 12:25 AM
PHP起源於1994年，由RasmusLerdorf開發，最初用於跟踪網站訪問者，逐漸演變為服務器端腳本語言，廣泛應用於網頁開發。 Python由GuidovanRossum於1980年代末開發，1991年首次發布，強調代碼可讀性和簡潔性，適用於科學計算、數據分析等領域。
Python vs. JavaScript：學習曲線和易用性
Apr 16, 2025 am 12:12 AM
Python更適合初學者，學習曲線平緩，語法簡潔；JavaScript適合前端開發，學習曲線較陡，語法靈活。 1.Python語法直觀，適用於數據科學和後端開發。 2.JavaScript靈活，廣泛用於前端和服務器端編程。
vs code 可以在 Windows 8 中運行嗎
Apr 15, 2025 pm 07:24 PM
VS Code可以在Windows 8上運行，但體驗可能不佳。首先確保系統已更新到最新補丁，然後下載與系統架構匹配的VS Code安裝包，按照提示安裝。安裝後，注意某些擴展程序可能與Windows 8不兼容，需要尋找替代擴展或在虛擬機中使用更新的Windows系統。安裝必要的擴展，檢查是否正常工作。儘管VS Code在Windows 8上可行，但建議升級到更新的Windows系統以獲得更好的開發體驗和安全保障。
sublime怎麼運行代碼python
Apr 16, 2025 am 08:48 AM
在 Sublime Text 中運行 Python 代碼，需先安裝 Python 插件，再創建 .py 文件並編寫代碼，最後按 Ctrl B 運行代碼，輸出會在控制台中顯示。
visual studio code 可以用於 python 嗎
Apr 15, 2025 pm 08:18 PM
VS Code 可用於編寫 Python，並提供許多功能，使其成為開發 Python 應用程序的理想工具。它允許用戶：安裝 Python 擴展，以獲得代碼補全、語法高亮和調試等功能。使用調試器逐步跟踪代碼，查找和修復錯誤。集成 Git，進行版本控制。使用代碼格式化工具，保持代碼一致性。使用 Linting 工具，提前發現潛在問題。
notepad 怎麼運行python
Apr 16, 2025 pm 07:33 PM
在 Notepad 中運行 Python 代碼需要安裝 Python 可執行文件和 NppExec 插件。安裝 Python 並為其添加 PATH 後，在 NppExec 插件中配置命令為“python”、參數為“{CURRENT_DIRECTORY}{FILE_NAME}”，即可在 Notepad 中通過快捷鍵“F6”運行 Python 代碼。
