树、图的构造与遍历和图的最小生成树
1.二叉树
1.1 二叉树类的实现
首先构造节点类，它的属性包括元素、左孩子、右孩子。然后构造二叉树类，它的属性有根节点。
class Node(object):
def __init__(self, item):
self.elem = item
self.lchild = None
self.rchild = None
class Tree(object):
'''二叉树类， 需要指定一个根节点'''
def __init__(self):
self.root = None
1.2 二叉树添加元素
首先将新元素构造为一个新的节点类的实例，然后根据广度优先原则首先找到添加节点的位置，添加节点。
# 伪代码如下
def add(self, item):
新节点node = 新节点类的实例
如果根节点为空，self.root = node.
queue = [self.root] # 用队列来存放遍历的节点
当队列不为空：
当前节点 = queue 队首的节点，并在queue中删除该节点
如果当前节点的左孩子为空：
新节点赋值给当前节点左孩子
否则：
将当前节点的左孩子加入到队列中
如果当前节点的右孩子为空：
新节点赋值给当前节点右孩子
否则：
将当前节点的右孩子加入到队列中
def add(self, item):
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root] # 用来存放要处理的东西
while queue:
cur_node = queue.pop(0)
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
1.3 二叉树的广度优先遍历
广度优先遍历即先遍历兄弟节点，再遍历孩子节点。
# 伪代码
def breadth_travel(self):
如果根为空，直接返回
queue = [self.root] # 将根节点添加到队列
当队列不为空：
当前节点 = queue 队首的节点，并在queue中删除该节点
打印出该节点的元素值
如果当前节点的左孩子非空：
将当前节点的左孩子添加到队列中
如果当前节点的右孩子非空：
将当前节点的右孩子添加到队列中
def breadth_travel(self):
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem, end=' ')
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
1.4 二叉树的深度优先遍历
深度优先遍历即先遍历孩子节点，再遍历兄弟节点。这里实现的深度优先遍历是“中序遍历”，即“左孩子——根节点——右孩子”。运用递归的思想，只需不断调用自身函数就能遍历完。
# 伪代码
# 调用时需要传入二叉树的根节点，不断递归调用
def preorder_travel(self, node):
如果node为空，直接返回
打印node的元素值
preorder_travel(self, node的左孩子)
preorder_travel(self, node的右孩子)
def preorder_travel(self, node):
if node is None:
return
print(node.elem, end=' ')
self.preorder_travel(node.lchild)
self.preorder_travel(node.rchild)
2.图
2.1 图的实现
图作为数据结构由 “字典” 实现，字典的键为“点”，值为“与键相邻的点”。
class Gragh():
def __init__(self,sequense):
'''sequense是一个集合，key是点，value是与key相连接的点'''
self.sequense = sequense
在实例化一个图的时候，需要传入如下所示的集合，表示 'A' 与 'B', 'C'相邻。
sequense = {'A': ['B'],
'B': ['C', 'D'],
'C': ['E'],
'D': [],
'E': ['A']}
2.2 图的广度优先遍历
图的遍历需要指定一个节点，将图转化为以这个节点为根的树，沿着树的广度进行遍历。
（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col。
（7）直到顶点v的所有未被访问过的邻接点处理完。
def BFS(self, source):
frontiers = [source] # 前驱节点
traveled = [source] # 遍历过的节点
while frontiers:
nexts = []
for frontier in frontiers:
for cur in self.sequense[frontier]:
if cur not in traveled:
traveled.append(cur)
nexts.append(cur)
frontiers = nexts # 更新一层前驱节点
return traveled
2.3 图的深度优先遍历
指定一个节点，将图转化为以这个节点为根的树，沿着树的深度进行遍历。
（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。
（6）直到所有顶点访问完。
def DFS(self, source):
traveled = []
stack = [source]
while stack:
cur = stack.pop()
if cur not in traveled:
traveled.append(cur)
for next_adj in self.sequense[cur]:
if next_adj not in traveled:
stack.append(next_adj)
return traveled
3.图的最小生成树
所有节点分成两个group，一个为已经选取的selected_node（用python中的list实现），一个为candidate_node。
首先任取一个节点加入到selected_node，然后遍历头节点在selected_node，尾节点在candidate_node的边，选取符合这个条件的边里面权重最小的边，加入到最小生成树，选出的边的尾节点加入到selected_node，并从candidate_node删除。直到candidate_node中没有备选节点。
在这里的图的每条边是有权重的，所以需要实现一个新的图的类，不同于 章节2 中通过点与点的临接关系确定图，而是用邻接矩阵描述图。
class Graph(object):
def __init__(self, maps):
self.maps = maps
self.nodenum = self.get_nodenum()
self.edgenum = self.get_edgenum()
def get_nodenum(self):
return len(self.maps)
def get_edgenum(self):
count = 0
for i in range(self.nodenum):
for j in range(i):
if self.maps[i][j] > 0 and self.maps[i][j] < 9999:
count += 1
return count
def prim(self):
res = []
if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
return res
res = []
seleted_node = [0]
candidate_node = [i for i in range(1, self.nodenum)]
while len(candidate_node) > 0:
begin, end, minweight = 0, 0, 9999
for i in seleted_node:
for j in candidate_node:
if self.maps[i][j] < minweight:
minweight = self.maps[i][j]
begin = i
end = j
res.append([begin, end, minweight])
seleted_node.append(end)
candidate_node.remove(end)
return res
构建一个如下图所示的图的实例
图结构
max_value = 9999
row0 = [0,7,max_value,max_value,max_value,5]
row1 = [7,0,9,max_value,3,max_value]
row2 = [max_value,9,0,6,max_value,max_value]
row3 = [max_value,max_value,6,0,8,10]
row4 = [max_value,3,max_value,8,0,4]
row5 = [5,max_value,max_value,10,4,0]
maps = [row0, row1, row2,row3, row4, row5]
graph = Graph(maps)
print(graph.prim())
输出为：[[0,5,5], [5,4,4], [4,1,3], [4,3,8], [3,2,6]]
其中每一项前两位为点，第三位为这两个点连边的权重
最小生成树为：0——5——4——1
4——3——2
