樹
def BinaryTree(r):
return [r, [], []]
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
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)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)
setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))
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.rightChild = self.rightChild
self.rightChild = 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 buildTree():
root_tree = BinaryTree('a')
root_tree.insertRight('c')
root_tree.insertLeft('b')
root_tree.getLeftChild().insertRight('d')
root_tree.getRightChild().insertLeft('e')
root_tree.getRightChild().insertRight('f')
return root_tree
ttree = buildTree()
上面程序生成樹為
樹的遍歷
中文翻譯稿 偷個(gè)懶，加快點(diǎn)進(jìn)度
二叉樹搜索
二叉搜索樹有個(gè)基特征遍尺，左邊的節(jié)點(diǎn)比父節(jié)點(diǎn)小蔬啡，右邊節(jié)點(diǎn)比父節(jié)點(diǎn)大。下面一一分析實(shí)現(xiàn)一個(gè)基本二叉樹常用操作思考過(guò)程：
1血久、創(chuàng)建兩個(gè)類，一個(gè)實(shí)現(xiàn)節(jié)點(diǎn)的常用屬性帮非，如保存child氧吐，parent等。我們實(shí)現(xiàn)的二叉樹保存的類似于字典末盔，key用來(lái)生成二叉搜索樹筑舅，對(duì)應(yīng)一個(gè)value值。
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
另一個(gè)類實(shí)現(xiàn)二叉搜索樹常用操作陨舱，如查找翠拣，刪除等等。這個(gè)實(shí)現(xiàn)也是最為復(fù)雜游盲，需要考慮因素很多误墓，逐步分析邦尊。先完成類的基本屬性。
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)蝉揍，用put方法。分析過(guò)程：說(shuō)先看根節(jié)點(diǎn)有沒有畦娄，沒有根節(jié)點(diǎn)直接作為根節(jié)點(diǎn)又沾。有根節(jié)點(diǎn)根據(jù)大小確定位置，因?yàn)椴淮_定樹長(zhǎng)度熙卡，只能用迭代判斷（迭代是效率比較低杖刷，一般盡量不用，但不確定循環(huán)次數(shù)和為了代碼整潔驳癌，分析問(wèn)題方便使用之滑燃，威力無(wú)窮）
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)
小疑問(wèn)：self.root從何而來(lái)，初始化中賦值不是為None了嗎,難道與__iter__(self):方法有關(guān)
第三步颓鲜，對(duì)給定鍵的值搜索表窘，和put方法一樣，也需要給定一個(gè)根節(jié)點(diǎn)甜滨，然后順著往下一次查找乐严，所以也需要判斷根節(jié)點(diǎn)有沒有。
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)
有了put和get方法衣摩，可以實(shí)現(xiàn)一些特定功能昂验，如__getitem__和__setitem__ __contains__
def __setitem__(self,k,v):
self.put(k,v)
def __getitem__(self,key):
return self.get(key)
def __contains__(self,key):
if self._get(key,self.root):
return True
else:
return False
這些都在常用的數(shù)據(jù)結(jié)構(gòu)中有實(shí)現(xiàn)，每一個(gè)都有特殊的功能艾扮，如__setitem__ 使得我們可以編寫像myZipTree['Plymouth'] = 55446 這樣的 Python 語(yǔ)句既琴，就像 Python 字典一樣。
__getitem__方法泡嘴，我們可以編寫一個(gè)類似于訪問(wèn)字典的 Python 語(yǔ)句甫恩，而實(shí)際上我們使用的是二叉搜索樹，例如 z = myZipTree ['Fargo']
__contains__重載了 in 操作符磕诊，可以實(shí)現(xiàn)
if 'Northfield' in myZipTree:
print("oom ya ya")
第四步填物，實(shí)現(xiàn)刪除纹腌，這也是最最小心的地方霎终。一個(gè)二叉搜索樹的刪除，找到刪除的節(jié)點(diǎn)位置后需要考慮左右兒子的情況
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)
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)
二叉查找樹有個(gè)最大的問(wèn)題就是容易導(dǎo)致層數(shù)特別多升薯，得看數(shù)據(jù)插入的順序莱褒，提出了平衡二叉樹，充分發(fā)揮二叉樹存在的價(jià)值涎劈。
平衡二叉樹實(shí)現(xiàn)
圖和圖算法
圖的實(shí)現(xiàn)
1广凸、領(lǐng)接矩陣
大多元素為空阅茶，所以說(shuō)是稀疏矩陣，事實(shí)上谅海，矩陣不是一個(gè)十分有效的存儲(chǔ)稀疏數(shù)據(jù)的有效方式脸哀。
鄰接表
實(shí)現(xiàn)稀疏連接圖的更空間高效的方法是使用鄰接表。
頂點(diǎn)類的實(shí)現(xiàn)采用字典而不是列表扭吁，字典鍵是頂點(diǎn)撞蜂，值是權(quán)重。
鄰接表實(shí)現(xiàn)
class Vertex:
def __init__(self,key):
self.id = key
self.connectedTo = {}
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo[nbr]
定義了一個(gè)頂點(diǎn)類侥袜，該頂點(diǎn)類用字典標(biāo)識(shí)和鄰居間的鄰接關(guān)系蝌诡，即鄰居節(jié)點(diǎn)和權(quán)重。該類也完成一些通用操作枫吧，如節(jié)點(diǎn)添加浦旱，獲取ID等。
class Graph:
def __init__(self):
self.vertList = {}
self.numVertices = 0
def addVertex(self,key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
return newVertex
def getVertex(self,n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self,n):
return n in self.vertList
def addEdge(self,f,t,cost=0):
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
創(chuàng)建上述圖程序?yàn)椋?/p>
if __name__ == '__main__':
g = Graph()
for i in range(6):
g.addVertex(i)
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1, 2, 4)
g.addEdge(2, 3, 9)
g.addEdge(3, 4, 7)
g.addEdge(3, 5, 3)
g.addEdge(4, 0, 1)
g.addEdge(5, 4, 8)
g.addEdge(5, 2, 1)
for v in g:
for w in v.getConnections():
print "(%s ,%s)" % (v.getId(),w.getId())
字梯問(wèn)題
將單詞 “FOOL” 轉(zhuǎn)換為單詞 “SAGE”九杂。 在字梯中你通過(guò)改變一個(gè)字母逐漸發(fā)生變化颁湖。 在每一步，你必須將一個(gè)字變換成另一個(gè)字例隆。有點(diǎn)像格雷碼爷狈。
從文件中讀入單詞，若兩兩比較裳擎，則當(dāng)單詞數(shù)多時(shí)比較次數(shù)暴增涎永，可以使用以下的辦法
假設(shè)我們有大量的桶，每個(gè)桶在外面有一個(gè)四個(gè)字母的單詞鹿响，除了標(biāo)簽中的一個(gè)字母已經(jīng)被下劃線替代羡微。例如，看 Figure 2惶我，我們可能有一個(gè)標(biāo)記為 “pop” 的桶妈倔。當(dāng)我們處理列表中的每個(gè)單詞時(shí)，我們使用 “” 作為通配符比較每個(gè)桶的單詞绸贡，所以 “pope” 和 “pops “ 將匹配 ”pop_“盯蝴。每次我們找到一個(gè)匹配的桶，我們就把單詞放在那個(gè)桶听怕。同一個(gè)桶中只有一個(gè)字母不同捧挺，形成鄰接棋蚌。
from pythonds.graphs import Graph
def buildGraph(wordFile):
d = {}
g = Graph()
wfile = open(wordFile,'r')
# create buckets of words that differ by one letter
for line in wfile:
word = line[:-1]
for i in range(len(word)):
bucket = word[:i] + '_' + word[i+1:]
if bucket in d:
d[bucket].append(word)
else:
d[bucket] = [word]
# add vertices and edges for words in the same bucket
for bucket in d.keys():
for word1 in d[bucket]:
for word2 in d[bucket]:
if word1 != word2:
g.addEdge(word1,word2)
return g
其他
深度優(yōu)先
廣度優(yōu)先搜索
D算法
prim算法
