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中文網其他相關文章！
详细讲解Python之Seaborn（数据可视化）Apr 21, 2022 pm 06:08 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于Seaborn的相关问题，包括了数据可视化处理的散点图、折线图、条形图等等内容，下面一起来看一下，希望对大家有帮助。
详细了解Python进程池与进程锁May 10, 2022 pm 06:11 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于进程池与进程锁的相关问题，包括进程池的创建模块，进程池函数等等内容，下面一起来看一下，希望对大家有帮助。
Python自动化实践之筛选简历Jun 07, 2022 pm 06:59 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于简历筛选的相关问题，包括了定义 ReadDoc 类用以读取 word 文件以及定义 search_word 函数用以筛选的相关内容，下面一起来看一下，希望对大家有帮助。
Python数据类型详解之字符串、数字Apr 27, 2022 pm 07:27 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于数据类型之字符串、数字的相关问题，下面一起来看一下，希望对大家有帮助。
分享10款高效的VSCode插件，总有一款能够惊艳到你！！Mar 09, 2021 am 10:15 AMVS Code的确是一款非常热门、有强大用户基础的一款开发工具。本文给大家介绍一下10款高效、好用的插件，能够让原本单薄的VS Code如虎添翼，开发效率顿时提升到一个新的阶段。
详细介绍python的numpy模块May 19, 2022 am 11:43 AM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于numpy模块的相关问题，Numpy是Numerical Python extensions的缩写，字面意思是Python数值计算扩展，下面一起来看一下，希望对大家有帮助。
python中文是什么意思Jun 24, 2019 pm 02:22 PMpythn的中文意思是巨蟒、蟒蛇。1989年圣诞节期间，Guido van Rossum在家闲的没事干，为了跟朋友庆祝圣诞节，决定发明一种全新的脚本语言。他很喜欢一个肥皂剧叫Monty Python，所以便把这门语言叫做python。
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
熱工具
ZendStudio 13.5.1 Mac
強大的PHP整合開發環境
SublimeText3 Linux新版
SublimeText3 Linux最新版
MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具，用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。
Atom編輯器mac版下載
最受歡迎的的開源編輯器
mPDF
mPDF是一個PHP庫，可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件，並處理不同的語言。與原始腳本如HTML2FPDF相比，它的速度較慢，並且在使用Unicode字體時產生的檔案較大，但支援CSS樣式等，並進行了大量增強。支援幾乎所有語言，包括RTL（阿拉伯語和希伯來語）和CJK（中日韓）。支援嵌套的區塊級元素（如P、DIV），
