一基础学习
1.pylab 模块是一款由python提供的可以绘制二维，三维数据的工具模块，其中包括了绘图软件包 matplotlib,其可以生成matab绘图库的图像。
安装pylab模块：pylab是matplotlib中的一个模块 所以我们直接安装matplotlib库。
pip install matplotlib
例子：y = 2x
import pylab
my_list=[ ]
for counter in range(10):
my_list.append(counter*2)
print my_list
print len(my_list)
#now plot the list
pylab.plot(my_list)
pylab.show()
2.数据结构-树
树是一种非线性的数据结构，是由n（n >=0）个结点组成的有限集合。
如果n==0，树为空树。
如果n>0，
树有一个特定的结点，根结点
根结点只有直接后继，没有直接前驱。
除根结点以外的其他结点划分为m（m>=0）个互不相交的有限集合，T0，T1，T2，...，Tm-1，每个结合是一棵树，称为根结点的子树。
数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3树、红黑树等等。
树的度／树的前驱后继／树的层次／树的有序性／森林等概念参考博文学习：http://blog.51cto.com/9291927/2068745
3.树的遍历
不要带着二叉树的遍历来限制了对树的遍历的理解。
树的遍历的定义：以某种方式访问树中的每一个结点，且仅访问一次。
树的遍历主要有先根遍历和后根遍历。
先根遍历：若树非空，则先访问根结点，再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。
后根遍历：若树非空，则按照从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。
森林的遍历：需要注意的是，只有二叉树森林才有中序遍历与完整二叉树中序遍历对应
先序遍历森林。
博文学习：树的常见算法&图的DFS和BFS（https://www.cnblogs.com/LUO77/p/5839273.html）
二练习错题
1.证明算法的正确性
要做下面的事情：
● 合法输入数据的说明
● 输入和期望输出之间的关系
算法的正确性：整体正确和部分正确
证明正确性的时候我们一般分两个阶段：
● 一用不变式来证明算法的部分正确性。不变式指的是依附于算法中的一条特定的语句，该语句对计算的结果状态进行判断。
● 二用收敛性来严整算法的整体正确性。收敛性是证明算法在特定的合法输入数据的情况下，会正常结束的一种方法。
2.树的练习
def set_children(self, mother, list_of_children):
# convert name to Member node (should check for validity)
mom_node = self.names_to_nodes[mother]
# add each child
for c in list_of_children:
# create Member node for a child
c_member = Member(c)
# remember its name to node mapping
self.names_to_nodes[c] = c_member
# set child's parent
c_member.add_parent(mom_node)
# set the parent's child
mom_node.add_child(c_member)
def is_parent(self, mother, kid):
mom_node = self.names_to_nodes[mother]
child_node = self.names_to_nodes[kid]
return child_node.is_parent(mom_node)
def is_child(self, kid, mother):
mom_node = self.names_to_nodes[mother]
child_node = self.names_to_nodes[kid]
return mom_node.is_child(child_node)
3.PROBLEM 7
#7-1
definsert(atMe, newFrob):
if newFrob.name == atMe.name:
newFrob.after = atMe.after
atMe.after = newFrob
newFrob.before = atMe
if newFrob.after:
newFrob.after.before = newFrob
elif newFrob.name < atMe.name:
if not atMe.before:
atMe.before = newFrob
newFrob.after = atMe
elif atMe.before and atMe.before == newFrob.before:
newFrob.after = atMe
atMe.before = newFrob
newFrob.before.after = newFrob
else:
newFrob.after = atMe
insert(atMe.before, newFrob)
else:
if atMe.after and atMe.after == newFrob.after:
newFrob.before = atMe
atMe.after = newFrob
newFrob.after.before = newFrob
elif atMe.after ==None:
atMe.after = newFrob
newFrob.before = atMe
else:
newFrob.before = atMe
insert(atMe.after, newFrob)
#7-2
def findFront(start):
if not start.getBefore():
return start
else:
return findFront(start.getBefore())
