树与图

Python 中的数据结构与算法

Miriam Antona

Software engineer

树——定义

带有节点的树示意图。

基于节点的数据结构
每个节点可有指向多个节点的连接

树——术语

带有节点的树示意图。根节点为黄色。

树——术语

带有节点的树示意图。根节点为黄色。一个父节点为橙色。

树——术语

带有节点的树示意图。根节点为黄色。一个父节点为橙色，其子节点为绿色。

树——术语

带有节点的树示意图。

树——术语

标注不同层级的树示意图。

树——二叉树

二叉树的图示。

每个节点有：
- 0 个子节点
- 1 个子节点
- 2 个子节点

树——二叉树实现

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

带有节点的树示意图。

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)

树——实际用途

存储层级关系
- 计算机文件系统
- HTML 文档结构
国际象棋：对手的可能走法
查找与排序算法

图

带有节点的图示。

由以下组成：
- 节点/顶点
- 连接/边
树是图的一种

图——类型

有向图：
- 具有特定方向

有向图示意图。

图——类型

无向图：
- 边无方向
- 关系是互相的

无向图示意图。

图——类型

加权图：
- 边关联数值
- 可为有向或无向

无向图，标注城市名称及其间距离。

图 vs. 树

树

不含环
所有节点必须连通

带有节点的树示意图。

图

可含环
可能存在不连通节点

带有节点的图示。

图 vs. 树

树

不含环
所有节点必须连通

带有节点的树示意图。

图

可含环
可能存在不连通节点

带有节点的图示。一个节点未与其他节点相连。

图——真实用例

社交网络中的用户关系
- 好友
- 关注
- 点赞
- 等等
位置与距离
- 路线优化
图数据库
查找与排序算法

图——实现

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

有向图示意图。

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}

Vamos praticar!

Python 中的数据结构与算法