Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析
1.示例
樹的一些屬性:
- 層次性:樹是按層級構(gòu)建的,越籠統(tǒng)就越靠近頂部,越具體則越靠近底部。
- 一個節(jié)點的所有子節(jié)點都與另一個節(jié)點的所有子節(jié)點無關(guān)。
- 葉子節(jié)點都是獨一無二的。
- 嵌套
2.術(shù)語及定義
- 節(jié)點:樹的基礎部分。節(jié)點的名字 → 鍵,附加信息 → 有效載荷。
- 邊:兩個節(jié)點通過一條邊相連,表示它們之間存在關(guān)系。除了根節(jié)點,其他每個結(jié)點都僅有一條入邊,出邊則可能有多條。
- 根節(jié)點:樹中唯一沒有入邊的結(jié)點。
- 路徑:由邊連接的有序節(jié)點列表。
- 子節(jié)點:一個節(jié)點通過出邊與子節(jié)點相連。
- 父節(jié)點:一個節(jié)點是其所有子節(jié)點的父節(jié)點。
- 兄弟節(jié)點:具有同一父節(jié)點的結(jié)點 → 互稱兄弟節(jié)點。
- 子樹:一個父節(jié)點及其所有后代的節(jié)點和邊構(gòu)成一棵子樹。
- 葉子結(jié)點:葉子節(jié)點沒有子節(jié)點。
- 層數(shù):節(jié)點n的層數(shù)是從根節(jié)點到n的唯一路徑長度。根節(jié)點的層數(shù)為0。
- 高度:樹的高度是其中節(jié)點層數(shù)的最大值。
1.定義一:樹由節(jié)點及連接節(jié)點的邊構(gòu)成。
樹的屬性:
- 有一個根節(jié)點除根節(jié)點外,其他每個節(jié)點都與其唯一的父節(jié)點相連。
- 從根節(jié)點到其他每個節(jié)點有且僅有一條路徑。
- 如果每個節(jié)點最多有兩個子節(jié)點 → 二叉樹。
2.定義二:一棵樹要么為空,要么由一個根節(jié)點和零棵或多棵子樹構(gòu)成,子樹本身也是一棵樹。
每棵子樹的根節(jié)點通過一條邊連到父樹的根節(jié)點。
3.實現(xiàn)
3.1 列表之列表
樹的根節(jié)點是myTree[0],左子樹是myTree[1],右子樹是myTree[2]。
# 列表函數(shù) def BinaryTree(r): return [r,[],[]] # 根節(jié)點r,和兩個作為子節(jié)點的空列表 # 插入左子樹 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é)點與引用
定義一個類,其中有根節(jié)點和左右子樹的屬性。
class BinaryTree: def __init__(self,rootObj): self.key = rootObj self.leftChild = None self.rightChild = None ## 插入左子節(jié)點 def insertLeft(self,newNode): if self.leftChild == None: self.leftChild = BinaryTree(newNode) else: t = BinaryTree(newNode) t.left = self.leftChild self.leftChild = t ## 插入右子節(jié)點 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.key
4.二叉樹的應用
4.1解析樹
- 根據(jù)完全括號表達式構(gòu)建解析樹
- 如何計算解析樹中的表達式
- 如何將解析樹還原成最初的數(shù)學表達式
解析樹構(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 ## 計算二叉解析樹的遞歸函數(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樹的遍歷
- 前序遍歷【根左右】
- 中序遍歷【左根右】
- 后序遍歷【左右根】
前序遍歷算法實現(xiàn)為外部函數(shù):
def preorder(tree): if tree: print(tree.getRootVal()) preorder(tree.getLeftChild()) preorder(tree.getRightChild)
前序遍歷算法實現(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.利用二叉堆實現(xiàn)優(yōu)先級隊列
隊列一個重要的變體 → 優(yōu)先級隊列。和隊列一樣,優(yōu)先級隊列從頭部移除元素,不過元素的邏輯順序是由優(yōu)先級決定的,優(yōu)先級最高的元素在最前,最低的元素在最后。
實現(xiàn)優(yōu)先級隊列的經(jīng)典方法 → 二叉堆。入隊和出隊操作均可達到O(logn)
- 最小堆【最小的元素一直在隊首】
- 最大堆【最大的元素一直在隊首】 6.6.2 二叉堆的實現(xiàn)
結(jié)構(gòu)屬性:
- 完全二叉樹:除了最底層,其他每一層的節(jié)點都是滿的。且在最底層,從左往右填充節(jié)點。
- 完全二叉樹可以用一個列表直接表示。
堆的有序性:對于堆中任意元素x及其父元素p,p都不大于x。
堆操作
代碼實現(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 - 1
6.二叉搜索樹
6.1搜索樹的實現(xiàn)
二叉搜索樹依賴性質(zhì):小于父節(jié)點的鍵都在左子樹中,大于父節(jié)點的鍵則都在右子樹。
代碼實現(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é)點 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) ## 查找鍵對應的值 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) # 檢查樹中是否有某個鍵 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é)點沒有子節(jié)點 2. 待刪除節(jié)點只有一個子節(jié)點 3. 待刪除節(jié)點有兩個子節(jié)點 """ # 尋找后繼結(jié)點 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 = self
7.平衡二叉搜索樹(AVL樹)
實現(xiàn)AVL樹時,要記錄每個節(jié)點的平衡因子。
平衡因子 = 左右子樹的高度之差
→ 保證樹的平衡因子為-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) # 實現(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 ) # 實現(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 ) # 實現(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
OpenCV里的imshow()和Matplotlib.pyplot的imshow()的實現(xiàn)
這篇文章主要介紹了OpenCV里的imshow()和Matplotlib.pyplot的imshow()的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2019-11-11用python實現(xiàn)操縱mysql數(shù)據(jù)庫插入
大家好,本篇文章主要講的是用python實現(xiàn)操縱mysql數(shù)據(jù)庫插入,感興趣的同學趕快來看一看吧,對你有幫助的話記得收藏一下2022-01-01python os.system執(zhí)行cmd指令代碼詳解
在本篇文章里小編給大家整理的是一篇關(guān)于python os.system執(zhí)行cmd指令代碼詳解內(nèi)容,有興趣的朋友們可以學習下。2021-10-10如何將yolo格式轉(zhuǎn)化為voc格式:txt轉(zhuǎn)xml(親測有效)
這篇文章主要介紹了如何將yolo格式轉(zhuǎn)化為voc格式:txt轉(zhuǎn)xml,親測有效,可以使用,本文通過圖文并茂的形式給大家介紹的非常詳細,感興趣的朋友參考下吧2023-12-12