python二叉樹常用算法總結(jié)
更新時間：2021年09月27日 14:54:55 作者：我是一顆大西瓜
這篇文章主要分享的是python二叉樹常用算法，二叉樹的遞歸思想很重要，還有遞歸的復(fù)雜度分析,需下面文章就來詳細解說該算法，要的朋友可以參考一下
1.1 二叉樹的初始化
#initial of BinaryTree
class BinaryTree:
def __init__(self,rootObj):
self.val = rootObj
self.left = None
self.right = None
def insertLeft(self,newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.left = self.left
self.left = t
def insertRight(self,newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.right = self.right
self.right = t
1.2 創(chuàng)建一個二叉樹
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4] # 18 # 7 11 #3 4 5 6 # 1 3 2 4 root = BinaryTree(18) root.left = BinaryTree(7) root.right = BinaryTree(11) root.left.left = BinaryTree(3) root.left.right = BinaryTree(4) root.right.left = BinaryTree(5) root.right.right = BinaryTree(6) root.right.left.left = BinaryTree(1) root.right.left.right = BinaryTree(3) root.right.right.left = BinaryTree(2) root.right.right.right = BinaryTree(4)
1.3 前序遍歷
#遞歸版本
def PreOrder(self, node):
if node:
print(node.val)
self.PreOrder(node.left)
self.PreOrder(node.right)
#循環(huán)版本
def PreOrderLoop(self, node):
if node == None:
return
stack =[]
print(node.val)
stack.append(node)
node = node.left
while stack!=[] or node:
while node:
print(node.val)
stack.append(node)
node = node.left
node = stack[-1].right
stack.pop()
#ouput: 18 7 3 4 11 5 1 3 6 2 4
1.4 中序遍歷
#遞歸版本
def InOrder(self, node):
if node:
self.InOrder(node.left)
print(node.val)
self.InOrder(node.right)
#循環(huán)版本
def InOrderLoop(self, node):
if node == None:
return None
stack = []
stack.append(node)
node = node.left
while stack!=[] or node:
while node:
stack.append(node)
node = node.left
print(stack[-1].val)
node = stack[-1].right
stack.pop()
#output：3 7 4 18 1 5 3 11 2 6 4
1.5 后序遍歷
#遞歸
def PostOrder(self, node):
if node:
self.PostOrder(node.left)
self.PostOrder(node.right)
print(node.val)
#非遞歸
def PostOrderLoop(self, node):
if node == None:
return
stack =[]
stack.append(node)
pre = None
while stack!=[]:
node = stack[-1]
if ((node.left==None and node.right==None) or
(pre and (pre == node.left or pre ==node.right))):
print(node.val)
pre = node
stack.pop()
else:
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
#output:3 4 7 1 3 5 2 4 6 11 18
1.6 層序遍歷
def LevelOrder(self, node):
if node == None:
return
stack = []
stack.append(node)
while stack!=[]:
node = stack[0]
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
print(node.val)
stack.pop(0)
output: 18 7 11 3 4 5 6 1 3 2 4
1.7 計算節(jié)點數(shù)
#遞歸版本
def CountNode(self, root):
if root == None:
return 0
return self.CountNode(root.left) + self.CountNode(root.right) + 1
#非遞歸版本
def CountNodeNotRev(self, root):
if root == None:
return 0
stack = []
stack.append(root)
index = 0
while index<len(stack):
if stack[index].left:
stack.append(stack[index].left)
if stack[index].right:
stack.append(stack[index].right)
index += 1
print(len(stack))
output: 11
1.8 計算樹的深度
def getTreeDepth(self, root):
if root == None:
return 0
left = self.getTreeDepth(root.left) + 1
right = self.getTreeDepth(root.right) + 1
return left if left>right else right
1.9 計算樹的葉子樹
def countLeaves(self, root):
if root == None:
return 0
if root.left==None and root.right==None:
return 1
return self.countLeaves(root.left)+self.countLeaves(root.right)
1.10 獲取第K層節(jié)點數(shù)
def getKLevel(self, root, K):
if root == None: return 0
if K == 1: return 1
return self.getKLevel(root.left, K-1)+self.getKLevel(root.right, K-1)
1.11 判斷兩顆二叉樹是否相同
def StrucCmp(self, root1, root2):
if root1 == None and root2 == None: return True
elif root1 ==None or root2 == None: return False
return self.StrucCmp(root1.left, root2.left) and self.StrucCmp(root1.right, root2.right)
1.12 二叉樹的鏡像
def Mirror(self, root):
if root == None: return
tmp = root.left
root.left = root.right
root.right = tmp
self.Mirror(root.left)
self.Mirror(root.right)
1.13 找最低公共祖先節(jié)點
def findLCA(self, root, node1, node2):
if root == None: return
if root == node1 or root == node2: return root
left = self.findLCA(root.left, node1, node2)
right = self.findLCA(root.right, node1, node2)
if left and right:
return root
return left if left else right
1.14 獲取兩個節(jié)點的距離
def getDist(self, root, node1, node2):
lca = self.findLCA(root, node1, node2) #找最低公共祖宗節(jié)點
level1 = self.FindLevel(lca, node1) #祖節(jié)點到兩個節(jié)點的距離
level2 = self.FindLevel(lca, node2)
return level1+level2
def FindLevel(self, node, target):
if node == None: return -1
if node == target: return 0
level = self.FindLevel(node.left, target)
if level == -1: level = self.FindLevel(node.right, target)
if level != -1: return level + 1
return -1
1.15 找一個節(jié)點的所有祖宗節(jié)點
def findAllAncestor(self, root, target):
if root == None: return False
if root == target: return True
if self.findAllAncestor(root.left, target) or self.findAllAncestor(root.right, target):
print(root.val)
return True
return False
到此這篇關(guān)于python二叉樹常用算法總結(jié)的文章就介紹到這了,更多相關(guān)python二叉樹常用算法，內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了tkinter模塊和ttk模塊的區(qū)別,以及如何在tkinter窗口中設(shè)計組件和進行布局管理的相關(guān)資料,文中通過代碼及圖文介紹的非常詳細,需要的朋友可以參考下2024-11-11
今天小編就為大家分享一篇python:按行讀入,排序然后輸出的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07![三步解決python PermissionError: [WinError 5]拒絕訪問的情況](http://img.jbzj.com/images/xgimg/bcimg2.png)
三步解決python PermissionError: [WinError 5]拒絕訪問的情況
這篇文章主要介紹了三步解決python PermissionError: [WinError 5]拒絕訪問的情況，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-04-04
今天小編就為大家分享一篇python將字符串list寫入excel和txt的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07
python?Django實現(xiàn)增刪改查實戰(zhàn)代碼
這篇文章主要介紹了python?Django增刪改查快速體驗,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-02-02
這篇文章主要介紹了Python logging模塊,logging模塊是在2.3新引進的功能,用來處理程序運行中的日志管理,本文詳細講解了該模塊的一些常用的類和模塊級函數(shù),需要的朋友可以參考下2014-05-05
Python實現(xiàn)輕松合并doc為txt的示例代碼
這篇文章主要為大家詳細介紹了如何利用Python編程語言和wxPython模塊,打開指定文件夾中的DOC文檔,并將它們的內(nèi)容合并成一個便捷的TXT文檔,需要的可以參考下2024-03-03
Python用for循環(huán)實現(xiàn)九九乘法表
本文通過實例代碼給大家介紹了Python用for循環(huán)實現(xiàn)九九乘法表的方法，代碼簡單易懂，非常不錯，具有一定的參考借鑒價值，需要的朋友參考下吧2018-05-05
Python+Pika+RabbitMQ環(huán)境部署及實現(xiàn)工作隊列的實例教程
RabbitMQ是一個消息隊列服務(wù)器,在本文中我們將學(xué)習(xí)到Python+Pika+RabbitMQ環(huán)境部署及實現(xiàn)工作隊列的實例教程,需要的朋友可以參考下2016-06-06
這篇文章主要介紹了python字符串的index和find的區(qū)別,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-06-06