1.4 樹(Tree)
1.4.1 術(shù)語
節(jié)點炭分、邊桃焕、根、路徑欠窒、子節(jié)點、父節(jié)點退子、兄弟岖妄、子樹、葉節(jié)點寂祥、層數(shù)荐虐、高度
1.4.2 代碼表示
class BinaryTree():
def __init__(self, rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self, newnode):
if self.leftChild == None:
self.leftChild = BinaryTree(newnode)
else:
t = BinaryTree(newnode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self, newnode):
if self.rightChild == None:
self.rightChild = BinaryTree(newnode)
else:
t = BinaryTree(newnode)
t.leftChild = self.leftChild
self.leftChild = t
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
def preorder(self):
print(self.key)
if self.leftChild:
self.leftChild.preorder()
if self.rightChild:
self.rightChild.preorder()
r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
a
None
r.insertLeft('b')
print(r.getLeftChild())
<__main__.BinaryTree object at 0x1111f8518>
1.4.3 分析樹
分析樹(parse tree),也叫具體語法樹(concrete syntax tree),不同于抽象語法樹丸凭。
使用表達式:(3+(4*5))福扬,構(gòu)建分析樹腕铸。
規(guī)則如下:
如果當(dāng)前符號是
'('
,添加一個新節(jié)點作為當(dāng)前節(jié)點的左子節(jié)點铛碑,并下降到左子節(jié)點(currentTree)狠裹。如果當(dāng)前符號在列表
['+', '-', '/', '*']
中,請將當(dāng)前節(jié)點的根植設(shè)置為當(dāng)前符號表示的運算符汽烦。添加一個新節(jié)點作為當(dāng)前節(jié)點的右子節(jié)點涛菠。如果當(dāng)前符號是數(shù)字,請將當(dāng)前節(jié)點的根值設(shè)置為該數(shù)字并返回到父節(jié)點撇吞。
如果當(dāng)前符號是
')'
俗冻,則轉(zhuǎn)到當(dāng)前節(jié)點的父節(jié)點。
from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree
def preorder(tree):
if tree:
print(tree.getRootVal())
preorder(tree.getLeftChild())
preorder(tree.getRightChild())
def buildParseTree(fpexp):
fplist = fpexp.split()
pStack = Stack()
eTree = BinaryTree('')
pStack.push(eTree)
currentTree = eTree
for i in fplist:
if i == '(':
# 規(guī)則 1
currentTree.insertLeft('')
pStack.push(currentTree)
currentTree = currentTree.getLeftChild()
elif i not in ['+', '-', '/', '*']:
# 規(guī)則 3
currentTree.setRootVal(i)
parent = pStack.pop()
currentTree = parent
elif i in ['+', '-', '/', '*']:
currentTree.setRootVal(i)
currentTree.insertRight('')
pStack.push(currentTree)
currentTree = currentTree.getRightChild()
elif i == ')':
currentTree = pStack.pop()
else:
raise ValueError
currentTree.preorder()
pt = buildParseTree('((10+5)*3)')
((10+5)*3)
1.4.4 樹的遍歷
前序遍歷:根節(jié)點 -> 左子樹 -> 右子樹
中序遍歷:左子樹 -> 根節(jié)點 -> 右子樹
后序遍歷:左子樹 -> 右子樹 -> 根節(jié)點
后序遍歷的常見用法牍颈,即計算分析樹迄薄。
1.4.5 基于二叉堆的優(yōu)先隊列
1.4.5.1 二叉堆結(jié)構(gòu)
class BinHeap:
def __init__(self):
self.heapList = []
self.currentSize = 0
def percUp(self, i): # i 為末尾
while i//2 > 0: # 不是頭節(jié)點
if self.heapList[i] < self.heapList[i//2]:
self.heapList[i], self.heapList[i//2] = self.heapList[i//2], self.headpList[i]
i = i//2
def insert(self, k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)
def minChild(self, i):
# 給出最小節(jié)點
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 percDown(self, i):
while ( i * 2 ) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
self.heapList[i], self.heapList[mc] = self.heapList[mc] + self.heapList[i]
i = mc
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
def bulidHeap(self, alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 1
1.4.6 二叉查找樹
BST屬性:左子樹的 key 小于父節(jié)點,右子樹的 key 都大于父節(jié)點煮岁。
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 hasBothChildren(self):
return self.rightChild and 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
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
def put(self,key,val):
# 插入新節(jié)點
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,k,v):
return self.put(k,v)
def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
return res.payload
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')
if 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):
return self.delete(key)
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 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 remove(self, currentNode):
if currentNode.isLeaf(): #leaf
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren(): #interior
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload
else: # this node has one child
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)
1.4.7 二叉查找樹分析
如果按照隨機順序添加鍵讥蔽,樹的高度將在 log2^n,n 為樹種的節(jié)點樹人乓。二叉查找樹的最差情況是 O(n)勤篮。
1.4.8 平衡二叉搜索樹 ( AVL樹 )
1.4.9 一些概念
平衡二叉搜索樹,又叫 AVL 樹色罚,能夠自動確保樹的平衡碰缔,從而保持性能穩(wěn)定在 O(logN)。
平衡因子戳护,定義為左子樹高度和右子樹的高度差金抡。如果平衡因子大于零,子樹是左重的腌且。如果平衡因子小于零梗肝,子樹是右重的。如果平衡因子等于零铺董,那么樹就是完美平衡的巫击。
如果平衡因子是`-1`、`0`或者`1`精续,那么樹稱之為平衡坝锰。
1.4.10 代碼實現(xiàn)
class AVLTree(BinarySearchTree):
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)
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)
def rotateLeft(self, rotRoot):
pass
def rotateRight(self, rotRoot):
pass