学习安排（8月2日-8月4日）
1.主要学习视频Week7
链接(http://www.xuetangx.com/courses/course-v1:MITx+6_00_1x+sp/about)
2.辅助内容：教材第11章绘图以及类的进一步扩展‘
树和搜索
本节课介绍另一种非常拥有的数据结构：树。
- 树可以很方便的存储层次类型的数据结构
- 树形结构本身就支持对信息的一系列操作，尤其是信息检索，如果可以进行排序，那么可以用一种高效的方式查找某个元素是否在一个特定数据集合之中
- 它可以使任何类型的问题转化成决策问题
二叉树
二叉树是一种特殊的树，它的每个节点最多有两个子节点。如果我们的数据都按照顺序排列，那么，二叉树存储和检索数据就会非常方便。
二叉树构建
class binaryTree(object):
def __init__(self, value):
self.value = value
self.leftBranch = None
self.rightBranch = None
self.parent = None
def setLeftBranch(self, node):
self.leftBranch = node
def setRightBranch(self, node):
self.rightBranch = node
def setParent(self, parent):
self.parent = parent
def getValue(self):
return self.value
def getLeftBranch(self):
return self.leftBranch
def getRightBranch(self):
return self.rightBranch
def getParent(self):
return self.parent
def __str__(self):
return self.value
n5 = binaryTree(5)
n2 = binaryTree(2)
n1 = binaryTree(1)
n4 = binaryTree(4)
n8 = binaryTree(8)
n6 = binaryTree(6)
n7 = binaryTree(7)
n3 = binaryTree(3)
n5.setLeftBranch(n2)
n2.setParent(n5)
n5.setRightBranch(n8)
n8.setParent(n5)
n2.setLeftBranch(n1)
n1.setParent(n2)
n2.setRightBranch(n4)
n4.setParent(n2)
n8.setLeftBranch(n6)
n6.setParent(n8)
n6.setRightBranch(n7)
n7.setParent(n6)
n4.setLeftBranch(n3)
n3.setParent(n4)
二叉树运用（运算）
- 某个元素是否在树中
- 查找路径：穿过哪些节点才能找到特定元素
- 做出一系列决定以达到某些目的
深度优先检索和广度优先检索
二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。
#深度优先
def DFSBinary(root, fcn):
queue = [root]
while len(queue) > 0:
print 'at node ' + str(queue[0].getValue())
if fcn(queue[0]):
return True
else:
temp = queue.pop(0)
if temp.getRightBranch():
queue.insert(0, temp.getRightBranch())
if temp.getLeftBranch():
queue.insert(0, temp.getLeftBranch())
return False
#广度优先
def BFSBinary(root, fcn):
queue = [root]
while len(queue) > 0:
print 'at node ' + str(queue[0].getValue())
if fcn(queue[0]):
return True
else:
temp = queue.pop(0)
if temp.getLeftBranch():
queue.append(temp.getLeftBranch())
if temp.getRightBranch():
queue.append(temp.getRightBranch())
return False
def find6(node):
return node.getValue() == 6
# test examples
print 'DFS'
DFSBinary(n5, find6)
print 'BFS'
BFSBinary(n5, find6)
Depth first search
Breadth first search
Depth first ordered search
决策树（Decision Trees）
在每一个节点，左分支还是右分支，都取决于一个决定，要不要把它添加进来？左边还是右边？这类问题被称为决策树。在这个情况中，到达目标节点的路径顺序或决策顺序（或者目标节点返回根节点的路径顺序）便定义了问题的解决方案。决策树问题可以通过树形检索完美解决。
下面，我们来看一下这个问题。我们将要做到的是：
- 建立一个真正的决策树，创建树并检索它。
- 很多情况下，只需简单地隐式地建立一个树，即仅仅在我们需要的时候创建分支，使用这个路径来确定解决方案会更好。
- 我们将要使用背包问题这个例子来建立决策树。
为背包问题建立决策树。
- 在根节点这层，我们需要决定是否把第一个对象包含进来。如果想要把第一个对象加进来，就走左边这个分支；如果不想包括就选右边这个分支。这就是一个决定。
- 在第n层，我们要对第n个元素做出相同的决策。
- 通过持续追踪至今已经放进背包的东西，所选择的分支路径，以及剩下的东西，我们可以创建一个决策二叉树。
## make a decision tree
## for efficiency should really generate on the fly, but here will build
## and then search
def buildDTree(sofar, todo):
if len(todo) == 0:
return binaryTree(sofar)
else:
withelt = buildDTree(sofar + [todo[0]], todo[1:])
withoutelt = buildDTree(sofar, todo[1:])
here = binaryTree(sofar)
here.setLeftBranch(withelt)
here.setRightBranch(withoutelt)
return here
def DFSDTree(root, valueFcn, constraintFcn):
queue = [root]
best = None
visited = 0
while len(queue) > 0:
visited += 1
if constraintFcn(queue[0].getValue()):
if best == None:
best = queue[0]
print best.getValue()
elif valueFcn(queue[0].getValue()) > valueFcn(best.getValue()):
best = queue[0]
print best.getValue()
temp = queue.pop(0)
if temp.getRightBranch():
queue.insert(0, temp.getRightBranch())
if temp.getLeftBranch():
queue.insert(0, temp.getLeftBranch())
else:
queue.pop(0)
print 'visited', visited
return best
def BFSDTree(root, valueFcn, constraintFcn):
queue = [root]
best = None
visited = 0
while len(queue) > 0:
visited += 1
if constraintFcn(queue[0].getValue()):
if best == None:
best = queue[0]
print best.getValue()
elif valueFcn(queue[0].getValue()) > valueFcn(best.getValue()):
best = queue[0]
print best.getValue()
temp = queue.pop(0)
if temp.getLeftBranch():
queue.append(temp.getLeftBranch())
if temp.getRightBranch():
queue.append(temp.getRightBranch())
else:
queue.pop(0)
print 'visited', visited
return best
#test example
a = [6,3]
b = [7,2]
c = [8,4]
d = [9,5]
treeTest = buildDTree([], [a,b,c,d])
def sumValues(lst):
vals = [e[0] for e in lst]
return sum(vals)
def sumWeights(lst):
wts = [e[1] for e in lst]
return sum(wts)
def WeightsBelow10(lst):
return sumWeights(lst) <= 10
def WeightsBelow6(lst):
return sumWeights(lst) <= 6
print ''
print 'DFS decision tree'
foobar = DFSDTree(treeTest, sumValues, WeightsBelow10)
print foobar.getValue()
print ''
print 'BFS decision tree'
foobarnew = BFSDTree(treeTest, sumValues, WeightsBelow10)
print foobarnew.getValue()
