Python學(xué)習(xí)之二叉樹(shù)實(shí)現(xiàn)的示例詳解
Python實(shí)現(xiàn)二叉樹(shù)
Python實(shí)現(xiàn)二叉樹(shù)可以使用面向?qū)ο缶幊痰姆绞?，通過(guò)定義二叉樹(shù)節(jié)點(diǎn)類來(lái)實(shí)現(xiàn)。每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素、左右子節(jié)點(diǎn)指針和一些操作方法，如插入節(jié)點(diǎn)、查找節(jié)點(diǎn)、刪除節(jié)點(diǎn)等。
以下是一個(gè)簡(jiǎn)單的二叉樹(shù)實(shí)現(xiàn)示例：
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類定義了一個(gè)節(jié)點(diǎn)，包含數(shù)據(jù)元素data，以及左右子節(jié)點(diǎn)指針left和right。insert方法用于向二叉樹(shù)中插入節(jié)點(diǎn)，find方法用于查找二叉樹(shù)中是否存在特定節(jié)點(diǎn)，inorder_traversal方法用于對(duì)二叉樹(shù)進(jìn)行中序遍歷。
下面是如何使用這個(gè)Node類來(lái)創(chuàng)建一個(gè)二叉樹(shù)：
root = Node(50) root.insert(30) root.insert(20) root.insert(40) root.insert(70) root.insert(60) root.insert(80) # 查找節(jié)點(diǎn) 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]
在上述代碼中，首先創(chuàng)建了一個(gè)根節(jié)點(diǎn)root，然后使用insert方法向樹(shù)中插入節(jié)點(diǎn)，最后使用find方法查找節(jié)點(diǎn)并使用inorder_traversal方法對(duì)二叉樹(shù)進(jìn)行中序遍歷。
除了插入、查找和遍歷方法，二叉樹(shù)還有其他的操作方法，如刪除節(jié)點(diǎn)、判斷是否為二叉搜索樹(shù)、計(jì)算樹(shù)的深度等。下面是一個(gè)稍微完整一些的二叉樹(shù)示例代碼：
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
在這個(gè)示例中，我們新增了delete方法來(lái)刪除指定的節(jié)點(diǎn)；minimum方法來(lái)查找樹(shù)中的最小節(jié)點(diǎn)；is_bst方法來(lái)判斷當(dāng)前樹(shù)是否為二叉搜索樹(shù)；height方法來(lái)計(jì)算樹(shù)的深度。
我們可以用以下代碼來(lái)測(cè)試新增的方法：
# 創(chuàng)建二叉樹(shù)
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)
# 刪除節(jié)點(diǎn)
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))
# 判斷是否為二叉搜索樹(shù)
print("Is it a BST?:", root.is_bst())
# 計(jì)算樹(shù)的深度
print("Tree height:", root.height(root))
這樣我們就完成了一個(gè)比較完整的二叉樹(shù)的實(shí)現(xiàn)，同時(shí)也演示了如何在Python中使用面向?qū)ο缶幊趟枷雭?lái)實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)。
最后附上完整的二叉樹(shù)類實(shí)現(xiàn)代碼：
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__':
# 創(chuàng)建二叉樹(shù)
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)
# 刪除節(jié)點(diǎn)
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))
# 判斷是否為二叉搜索樹(shù)
print("Is it a BST?:", root.is_bst())
# 計(jì)算樹(shù)的深度
print("Tree height:", root.height(root))
運(yùn)行代碼后，可以得到以下輸出：
Deleting node 20:
[30, 40, 50, 60, 70, 80]
Is it a BST?: True
Tree height: 3
這個(gè)示例包含了插入、查找、刪除、遍歷、判斷是否為二叉搜索樹(shù)和計(jì)算樹(shù)的深度等。希望對(duì)看到的小伙伴有幫助。
到此這篇關(guān)于Python學(xué)習(xí)之二叉樹(shù)實(shí)現(xiàn)的示例詳解的文章就介紹到這了,更多相關(guān)Python二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹Python3.9的一些新特性比如說(shuō)更快速的進(jìn)程釋放，性能的提升，簡(jiǎn)便的新字符串函數(shù)，字典并集運(yùn)算符以及更兼容穩(wěn)定的內(nèi)部API，感興趣的朋友跟隨小編一起看看吧2020-10-10
詳解Python 定時(shí)框架 Apscheduler原理及安裝過(guò)程
Apscheduler是一個(gè)非常強(qiáng)大且易用的類庫(kù)，可以方便我們快速的搭建一些強(qiáng)大的定時(shí)任務(wù)或者定時(shí)監(jiān)控類的調(diào)度系統(tǒng)，這篇文章主要介紹了Python 定時(shí)框架 Apscheduler ,需要的朋友可以參考下2019-06-06
Python使用Tesseract實(shí)現(xiàn)從圖像中讀取文本
Tesseract?是一個(gè)基于計(jì)算機(jī)的系統(tǒng),用于光學(xué)字符識(shí)別?(OCR)?和其他圖像到文本處理,本文將介紹如何使用?Python?中的?Tesseract?創(chuàng)建一個(gè)可以從圖像中讀取文本的程序,需要的可以參考下2023-11-11
本文主要介紹了pygame加載中文名mp3文件出現(xiàn)error的解決方案。具有很好的參考價(jià)值，下面跟著小編一起來(lái)看下吧2017-03-03
這篇文章主要為大家介紹了Python?retrying?重試機(jī)制，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-11-11
編譯 pycaffe時(shí)報(bào)錯(cuò)：fatal error: numpy/arrayobject.h沒(méi)有那個(gè)文件或目錄
這篇文章主要介紹了編譯 pycaffe時(shí)報(bào)錯(cuò)：fatal error: numpy/arrayobject.h沒(méi)有那個(gè)文件或目錄,需要的朋友可以參考下2020-11-11
本文主要介紹了Python3 re.search()方法的具體使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
這篇文章主要介紹了pyqt添加啟動(dòng)等待界面的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-03-03
關(guān)于Python中flask-httpauth庫(kù)用法詳解
這篇文章主要介紹了關(guān)于Python中flask-httpauth庫(kù)用法詳解,Flask-HTTPAuth是一個(gè)?Flask?擴(kuò)展，它簡(jiǎn)化了?HTTP?身份驗(yàn)證與?Flask?路由的使用,需要的朋友可以參考下2023-04-04
這篇文章主要介紹了Python中asyncore的用法,asyncore提供了方便的網(wǎng)絡(luò)操作方法,本文以連接并解析www.python.org主頁(yè)為例加以說(shuō)明,需要的朋友可以參考下2014-09-09