Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析
更新時(shí)間：2022年07月18日 14:34:05 作者：Ding?Jiaxiong
這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
1.示例
樹的一些屬性：
- 層次性：樹是按層級(jí)構(gòu)建的，越籠統(tǒng)就越靠近頂部，越具體則越靠近底部。
- 一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都與另一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)無關(guān)。
- 葉子節(jié)點(diǎn)都是獨(dú)一無二的。
- 嵌套
2.術(shù)語及定義
- 節(jié)點(diǎn)：樹的基礎(chǔ)部分。節(jié)點(diǎn)的名字 → 鍵，附加信息 → 有效載荷。
- 邊：兩個(gè)節(jié)點(diǎn)通過一條邊相連，表示它們之間存在關(guān)系。除了根節(jié)點(diǎn)，其他每個(gè)結(jié)點(diǎn)都僅有一條入邊，出邊則可能有多條。
- 根節(jié)點(diǎn)：樹中唯一沒有入邊的結(jié)點(diǎn)。
- 路徑：由邊連接的有序節(jié)點(diǎn)列表。
- 子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)通過出邊與子節(jié)點(diǎn)相連。
- 父節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)是其所有子節(jié)點(diǎn)的父節(jié)點(diǎn)。
- 兄弟節(jié)點(diǎn)：具有同一父節(jié)點(diǎn)的結(jié)點(diǎn) → 互稱兄弟節(jié)點(diǎn)。
- 子樹：一個(gè)父節(jié)點(diǎn)及其所有后代的節(jié)點(diǎn)和邊構(gòu)成一棵子樹。
- 葉子結(jié)點(diǎn)：葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)。
- 層數(shù)：節(jié)點(diǎn)n的層數(shù)是從根節(jié)點(diǎn)到n的唯一路徑長(zhǎng)度。根節(jié)點(diǎn)的層數(shù)為0。
- 高度：樹的高度是其中節(jié)點(diǎn)層數(shù)的最大值。
1.定義一：樹由節(jié)點(diǎn)及連接節(jié)點(diǎn)的邊構(gòu)成。
樹的屬性：
- 有一個(gè)根節(jié)點(diǎn)除根節(jié)點(diǎn)外，其他每個(gè)節(jié)點(diǎn)都與其唯一的父節(jié)點(diǎn)相連。
- 從根節(jié)點(diǎn)到其他每個(gè)節(jié)點(diǎn)有且僅有一條路徑。
- 如果每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn) → 二叉樹。
2.定義二：一棵樹要么為空，要么由一個(gè)根節(jié)點(diǎn)和零棵或多棵子樹構(gòu)成，子樹本身也是一棵樹。
每棵子樹的根節(jié)點(diǎn)通過一條邊連到父樹的根節(jié)點(diǎn)。
3.實(shí)現(xiàn)
3.1 列表之列表
樹的根節(jié)點(diǎn)是myTree[0]，左子樹是myTree[1]，右子樹是myTree[2]。
# 列表函數(shù)
def BinaryTree(r):
return [r,[],[]] # 根節(jié)點(diǎn)r，和兩個(gè)作為子節(jié)點(diǎn)的空列表
# 插入左子樹
def insertLeft(root,newBranch):
t = root.pop(1)
if len(t) > 1:
root.insert(1,[newBranch,t,[]])
else:
root.insert(1,[newBranch,[],[]])
return root
## 插入右子樹
def insertRight(root , newBranch):
t = root.pop(2)
if len(t) > 1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root
### 樹的訪問函數(shù)
def getRootVal(root):
return root[0]
def setRootVal(root,newVal):
root[0] = newVal
def getLeftChild(root):
return root[1]
def getRightChild(root):
return root[2]
r = BinaryTree(3)
insertLeft(r,4)
print(r)3.2節(jié)點(diǎn)與引用
定義一個(gè)類，其中有根節(jié)點(diǎn)和左右子樹的屬性。
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
## 插入左子節(jié)點(diǎn)
def insertLeft(self,newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.left = self.leftChild
self.leftChild = t
## 插入右子節(jié)點(diǎn)
def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.right = self.rightChild
self.rightChild = t
## 訪問函數(shù)
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key4.二叉樹的應(yīng)用
4.1解析樹
- 根據(jù)完全括號(hào)表達(dá)式構(gòu)建解析樹
- 如何計(jì)算解析樹中的表達(dá)式
- 如何將解析樹還原成最初的數(shù)學(xué)表達(dá)式
解析樹構(gòu)建器：
import operator
from pythonds.basic import Stack
from pythonds.trees import BinaryTree
def buildParseTree(fpexp):
fplist = fpexp.split()
pStack = Stack()
eTree = BinaryTree("")
pStack.push(eTree)
currentTree = eTree
for i in fplist:
if i == "(":
currentTree.insertLeft("")
pStack.push(currentTree)
currentTree = currentTree.getLeftChild()
elif i not in "+-*/)":
currentTree.setRootVal(eval(i))
parent = pStack.pop()
currentTree = parent
elif i in "+-*/":
currentTree.setRootVal(i)
currentTree.insertRight("")
currentTree = currentTree.getRightChild()
elif i == ")":
currentTree = pStack.pop()
else:
raise ValueError("Unkown Operator :" + i )
return eTree
## 計(jì)算二叉解析樹的遞歸函數(shù)
def evaluate(parseTree):
opers = {
"+":operator.add,"-":operator.sub,
"*":operator.mul,"/":operator.truediv
}
leftC = parseTree.getLeftChild()
rightC = parseTree.getRightChild()
if leftC and rightC:
fn = opers[parseTree.getRootVal()]
return fn(evaluate(leftC),evaluate(rightC))
else:
return parseTree.getRootVal()4.2樹的遍歷
- 前序遍歷【根左右】
- 中序遍歷【左根右】
- 后序遍歷【左右根】
前序遍歷算法實(shí)現(xiàn)為外部函數(shù)：
def preorder(tree):
if tree:
print(tree.getRootVal())
preorder(tree.getLeftChild())
preorder(tree.getRightChild)前序遍歷算法實(shí)現(xiàn)為BinaryTree類的方法
def preorder(self):
print(self.key)
if self.leftChild:
self.leftChild.preorder()
if self.rightChild:
self.rightChild.preorder()后序遍歷函數(shù)
def postorder(tree):
if tree != None:
postorder(tree.getLeftChild())
postorder(tree.getRightChild())
print(tree.getRootVal())中序遍歷函數(shù)
def inorder(tree):
if tree != None:
inorder(tree.getLeftChild())
print(tree.getRootVal())
inorder(tree.getRightChild())5.利用二叉堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列
隊(duì)列一個(gè)重要的變體 → 優(yōu)先級(jí)隊(duì)列。和隊(duì)列一樣，優(yōu)先級(jí)隊(duì)列從頭部移除元素，不過元素的邏輯順序是由優(yōu)先級(jí)決定的，優(yōu)先級(jí)最高的元素在最前，最低的元素在最后。
實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的經(jīng)典方法 → 二叉堆。入隊(duì)和出隊(duì)操作均可達(dá)到O(logn)
- 最小堆【最小的元素一直在隊(duì)首】
- 最大堆【最大的元素一直在隊(duì)首】 6.6.2 二叉堆的實(shí)現(xiàn)
結(jié)構(gòu)屬性：
- 完全二叉樹：除了最底層，其他每一層的節(jié)點(diǎn)都是滿的。且在最底層，從左往右填充節(jié)點(diǎn)。
- 完全二叉樹可以用一個(gè)列表直接表示。
堆的有序性：對(duì)于堆中任意元素x及其父元素p，p都不大于x。
堆操作
代碼實(shí)現(xiàn)：
class EchaDui:
# 新建二叉堆
def __init__(self):
self.heapList = [0]
self.currentSize = 0
def percUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2
# 新加元素
def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)
def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc
def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2 + 1]:
return i * 2
else:
return i * 2 + 1
## 從二叉堆中刪除最小的元素
def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval
## 根據(jù)元素列表構(gòu)建堆
def builgHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 16.二叉搜索樹
6.1搜索樹的實(shí)現(xiàn)
二叉搜索樹依賴性質(zhì)：小于父節(jié)點(diǎn)的鍵都在左子樹中，大于父節(jié)點(diǎn)的鍵則都在右子樹。
代碼實(shí)現(xiàn)：
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
def __iter__(self):
return self.root.__iter__()
# 插入新節(jié)點(diǎn)
def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root = TreeNode(key,val)
self.size = self.size + 1
def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)
def __setitem__(self, key, value):
self._put(key,value)
## 查找鍵對(duì)應(yīng)的值
def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
return res.payload
else:
return None
else:
return None
def _get(self,key,currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key,currentNode.leftChild)
else:
return self._get(key,currentNode.rightChild)
def __getitem__(self, key):
return self.get(key)
# 檢查樹中是否有某個(gè)鍵
def __contains__(self, key):
if self._get(key,self.root):
return True
else:
return False
# 刪除
def delete(self,key):
if self.size > 1:
nodeToRemove = self._get(key,self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self.size - 1
else:
raise KeyError("Error,key not in tree")
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError("Error,key not in tree")
def __delitem__(self, key):
self.delete(key)
"""
1. 待刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)
2. 待刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)
3. 待刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
"""
# 尋找后繼結(jié)點(diǎn)
def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ
def findMin(self):
current = self
while current.hasLeftChild():
current = current.leftChild
return current
def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent
def remove(self,currentNode):
if currentNode.isLeaf():
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren():
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload
else:
if currentNode.hasLeftChild():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
else:
currentNode.replaceNodeData(currentNode.leftChild.key,
currentNode.leftChild.payload,
currentNode.leftChild.leftChild,
currentNode.leftChild.rightChild
)
else:
if currentNode.isLeftChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
else:
currentNode.replaceNodeData(currentNode.rightChild.key,
currentNode.rightChild.payload,
currentNode.rightChild.leftChild,
currentNode.rightChild.rightChild
)
# 二叉搜索樹迭代器
def __iter__(self):
if self:
if self.hasLeftChild():
for elem in self.leftChild:
yield elem
yield self.key
if self.hasRightChild():
for elem in self.rightChild:
yield elem
class TreeNode:
def __init__(self,key,val,left = None,right = None,parent = None):
self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent
def hasLeftChild(self):
return self.leftChild
def hasRightChild(self):
return self.rightChild
def isLeftChild(self):
return self.parent and self.parent.leftChild == self
def isRightChild(self):
return self.parent and self.parent.rightChild == self
def isRoot(self):
return not self.parent
def isLeaf(self):
return not (self.rightChild or self.leftChild)
def hasAnyChildren(self):
return self.rightChild or self.leftChild
def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.payload = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self7.平衡二叉搜索樹（AVL樹）
實(shí)現(xiàn)AVL樹時(shí)，要記錄每個(gè)節(jié)點(diǎn)的平衡因子。
平衡因子 = 左右子樹的高度之差
→ 保證樹的平衡因子為-1，0,1，可以使得關(guān)鍵操作獲得更好的大O性能
#from 第6章樹.二叉搜索樹 import TreeNode
def _put(self, key, val, currentNode):
if key < currentNode.key:
if currentNode.hasLeftchi1d():
self._put(key, val, currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key, val,parent=currentNode)
self.updateBalance(currentNode.leftChild)
else:
if currentNode.hasRightChild():
self._put(key, val, currentNode.rightChild)
else:
currentNode.rightchild - TreeNode(key, val,parent=currentNode)
self.updateBalance(currentNode.rightChild)
def updateBalance(self, node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.rebalance(node)
return
if node.parent != None:
if node.isLeftChild():
node.parent.balanceFactor += 1
elif node.isRightChild():
node.parent.balanceFactor -= 1
if node.parent.balanceFactor != 0:
self.updateBalance(node.parent)
# 實(shí)現(xiàn)左旋
def rotateLeft (self, rotRoot) :
newRoot = rotRoot .rightchild
rotRoot .rightChild = newRoot.leftChild
if newRoot . leftChild !=None :
newRoot . leftChild. parent = rotRoot
newRoot.parent =rotRoot.parent
if rotRoot .isRoot( ):
self.root = newRoot
else:
if rotRoot .isLeftChild():
rotRoot.parent .leftChild = newRoot
else:
rotRoot.parent .rightChild = newRoot
newRoot . leftChild = rotRoot
rotRoot.parent = newRoot
rotRoot. balanceFactor = rotRoot . balanceFactor + 1 - min(newRoot . balanceFactor,0)
newRoot . balanceFactor = newRoot . balanceFactor + 1 +max(rotRoot . balanceFactor,o )
# 實(shí)現(xiàn)再平衡
def rebalance(self, node) :
if node. balanceFactor < 0:
if node .rightChild .balanceFactor > 0:
self.rotateRight (node.rightChild)self.rotateLeft (node)
else:
self.rotateLeft (node)
elif node. balanceFactor > 0 :
if node . leftChild. balanceFactor < 0:
self.rotateLeft (node. leftChild)
self.rotateRight (node)
else:
self.rotateRight (node)
nceFactor + 1 - min(newRoot . balanceFactor,0)
newRoot . balanceFactor = newRoot . balanceFactor + 1 +max(rotRoot . balanceFactor,o )
# 實(shí)現(xiàn)再平衡
def rebalance(self, node) :
if node. balanceFactor < 0:
if node .rightChild .balanceFactor > 0:
self.rotateRight (node.rightChild)self.rotateLeft (node)
else:
self.rotateLeft (node)
elif node. balanceFactor > 0 :
if node . leftChild. balanceFactor < 0:
self.rotateLeft (node. leftChild)
self.rotateRight (node)
else:
self.rotateRight (node)到此這篇關(guān)于Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析的文章就介紹到這了,更多相關(guān)Python數(shù)據(jù)結(jié)構(gòu)樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
python實(shí)現(xiàn)端口轉(zhuǎn)發(fā)器的方法
這篇文章主要介紹了python實(shí)現(xiàn)端口轉(zhuǎn)發(fā)器的方法,涉及Python實(shí)現(xiàn)端口轉(zhuǎn)發(fā)的技巧,支持TCP和UDP協(xié)議,需要的朋友可以參考下2015-03-03
四年一度的世界杯已經(jīng)開始了，對(duì)于不少熱愛足球運(yùn)動(dòng)的球迷來說，這可是十分難得的盛宴。今天小編就通過Python數(shù)據(jù)分析以及機(jī)器學(xué)習(xí)等方式來預(yù)測(cè)一下誰能獲得最后的冠軍，感興趣的可以了解一下2022-11-11
python 將日期戳（五位數(shù)時(shí)間）轉(zhuǎn)換為標(biāo)準(zhǔn)時(shí)間
這篇文章主要介紹了python 將日期戳（五位數(shù)時(shí)間）轉(zhuǎn)換為標(biāo)準(zhǔn)時(shí)間的實(shí)現(xiàn)方法，本文圖文并茂給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-07-07
Python讀取英文文件并記錄每個(gè)單詞出現(xiàn)次數(shù)后降序輸出示例
這篇文章主要介紹了Python讀取英文文件并記錄每個(gè)單詞出現(xiàn)次數(shù)后降序輸出,涉及Python文件讀取、字符串替換、分割以及字典遍歷、排序等相關(guān)操作技巧,需要的朋友可以參考下2018-06-06
這篇文章主要介紹了pandas 如何分割字符的實(shí)現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
Python+Pandas 獲取數(shù)據(jù)庫并加入DataFrame的實(shí)例
今天小編就為大家分享一篇Python+Pandas 獲取數(shù)據(jù)庫并加入DataFrame的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-07-07
利用Python判斷整數(shù)是否是回文數(shù)的3種方法總結(jié)
這篇文章主要給大家介紹了關(guān)于如何利用Python判斷整數(shù)是否是回文數(shù)的3種方總結(jié),回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù),需要的朋友可以參考下2021-07-07
這篇文章主要介紹了在Python的Flask框架中使用模版的入門教程,模版的使用是Flask使用當(dāng)中的基礎(chǔ),需要的朋友可以參考下2015-04-04
Python在報(bào)表自動(dòng)化的優(yōu)勢(shì)及實(shí)現(xiàn)流程
本文利用Python實(shí)現(xiàn)報(bào)表自動(dòng)化,通過介紹環(huán)境設(shè)置、數(shù)據(jù)收集和準(zhǔn)備、報(bào)表生成以及自動(dòng)化流程,展示Python的靈活性和豐富的生態(tài)系統(tǒng)在報(bào)表自動(dòng)化中的卓越表現(xiàn),從設(shè)置虛擬環(huán)境到使用Pandas和Matplotlib處理數(shù)據(jù),到借助APScheduler實(shí)現(xiàn)定期自動(dòng)化,每個(gè)步驟都得到詳盡闡述2023-12-12
這篇文章主要介紹了Python中對(duì)列表排序?qū)嵗?本文給出了9個(gè)List的排序?qū)嵗?需要的朋友可以參考下,希望能夠給你帶來幫助2021-10-10