链式实现：指向孩子节点的指针
使用“指向孩子节点的指针”，从root节点开始，使用指针将所有节点连成一个整体。
这里我还实现了广度优先遍历（BFS）和深度优先遍历（DFS）算法。其时间复杂度均为O(n)。
这种情况下，BFS利用队列进行遍历，DFS利用栈进行遍历。关于其中的DFS，这里的栈主要是指函数调用栈，也就是利用递归来实现。
广度优先遍历主要思路是：
- 利用队列进行遍历
- 从根节点开始把节点按顺序放入队列
- 每次从队列中取出一个节点，访问数据
- 然后将该节点的所有子节点入队
- 循环直到队列为空
深度优先遍历的关键是利用递归，主要步骤是:
- 访问当前节点数据
- 对当前节点的所有子节点递归调用dfs函数
- 进入每个子节点后，重复1、2步骤
- 递归调用结束后回溯到上一层
这样通过递归不断向更深层遍历，从而完成整棵树的遍历。递归会能保证从某一节点完整遍历其子树，再回溯到上一层节点。
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.child_nodes = []
def append_child(self, node):
self.child_nodes.append(node)
def __repr__(self):
return f'{self.__class__.__name__}({self.data})'
def bfs(self):
lst = []
queue = deque([self])
while queue:
cur = queue.popleft()
lst.append(cur)
for child in cur.child_nodes:
queue.append(child)
return lst
def dfs(self):
lst = []
def recursive_dfs(node):
lst.append(node)
for child in node.child_nodes:
recursive_dfs(child)
recursive_dfs(self)
return lst
if __name__ == '__main__':
tree_struct = """\
- 0
- 1
- 3
- 4
- 5
- 2
- 6
- 8
- 9
- 7
"""
root = Node(0)
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)
node8 = Node(8)
node9 = Node(9)
root.append_child(node1)
root.append_child(node2)
node1.append_child(node3)
node2.append_child(node6)
node2.append_child(node7)
node3.append_child(node4)
node3.append_child(node5)
node6.append_child(node8)
node6.append_child(node9)
print(tree_struct)
print('#' * 30)
print('bfs=', root.bfs())
print('dfs=', root.dfs())
结果：
- 0
- 1
- 3
- 4
- 5
- 2
- 6
- 8
- 9
- 7
##############################
bfs= [Node(0), Node(1), Node(2), Node(3), Node(6), Node(7), Node(4), Node(5), Node(8), Node(9)]
dfs= [Node(0), Node(1), Node(3), Node(4), Node(5), Node(2), Node(6), Node(8), Node(9), Node(7)]
顺序实现：指向双亲节点的指针
使用“指向双亲节点的指针”，来表达树的层级结构，但这样做无法从双亲节点访问孩子节点，因而无法遍历，因此，使用一个顺序表，存储所有的节点。
这种情况下，有三种遍历方式：
- 直接遍历顺序表，时间复杂度O(n)。
- 广度优先遍历（BFS），时间复杂度O(n^2)。
- 深度优先遍历（DFS），时间复杂度O(n^2)。
广度优先遍历（BFS）仍然采取队列方式，深度优先遍历（DFS）仍然采取递归方式。
通常来讲，广度优先遍历（BFS）和深度优先遍历（DFS）的时间复杂度为O(n)，这里显然时间复杂度较高。
时间复杂度达到了O(n^2)，是因为这是一个极其简单的实现，关键在于：没有存储child孩子节点的指针。如果存储了，那还能再优化一下，典型的空间换时间。
于是，每找到一个孩子都需要遍历一遍顺序表，这一步骤就花掉了O(n)的时间。同时，再加上本来的遍历时间O(n)，而且两者叠加是呈现乘法的嵌套结构。所以，时间复杂度就达到了O(n^2)。
from collections import deque
class Node:
def __init__(self, data, parent=None):
self.data = data
self.parent = parent
def __repr__(self):
return f'{self.__class__.__name__}({self.data})'
class Tree:
def __init__(self):
self._data = []
def append(self, node):
self._data.append(node)
def traversal(self):
return self._data
def bfs_traversal(self):
"""
时间复杂度O(n^2)
"""
lst = []
# 首先要找到 root 节点
root_ = None
for x in self._data:
if x.parent is None:
root_ = x
queue = deque([root_])
while queue:
cur = queue.popleft()
lst.append(cur)
for x in self._data:
if x.parent == cur:
queue.append(x)
return lst
def dfs_traversal(self):
"""
时间复杂度O(n^2)
"""
lst = []
# 首先要找到 root 节点
root_ = None
for x in self._data:
if x.parent is None:
root_ = x
def recursive_dfs(node):
lst.append(node)
for y in self._data:
if y.parent == node:
recursive_dfs(y)
recursive_dfs(root_)
return lst
if __name__ == '__main__':
tree_struct = """\
- 0
- 1
- 3
- 4
- 5
- 2
- 6
- 8
- 9
- 7
"""
tree = Tree()
root = Node(0)
node1 = Node(1, parent=root)
node2 = Node(2, parent=root)
node3 = Node(3, parent=node1)
node4 = Node(4, parent=node3)
node5 = Node(5, parent=node3)
node6 = Node(6, parent=node2)
node7 = Node(7, parent=node2)
node8 = Node(8, parent=node6)
node9 = Node(9, parent=node6)
tree.append(root)
tree.append(node1)
tree.append(node2)
tree.append(node3)
tree.append(node4)
tree.append(node5)
tree.append(node6)
tree.append(node7)
tree.append(node8)
tree.append(node9)
print(tree_struct)
print(f'traversal= {tree.traversal()}')
print(f'bfs= {tree.bfs_traversal()}')
print(f'dfs= {tree.dfs_traversal()}')
结果：
- 0
- 1
- 3
- 4
- 5
- 2
- 6
- 8
- 9
- 7
traversal= [Node(0), Node(1), Node(2), Node(3), Node(4), Node(5), Node(6), Node(7), Node(8), Node(9)]
bfs= [Node(0), Node(1), Node(2), Node(3), Node(6), Node(7), Node(4), Node(5), Node(8), Node(9)]
dfs= [Node(0), Node(1), Node(3), Node(4), Node(5), Node(2), Node(6), Node(8), Node(9), Node(7)]
扩展：顺序实现与关系型数据库的“自关联”
关系型数据库的“自关联”（Self Join）（Hierarchical Relationship）可以表达树的层级结构。
在设计时往往通过一个pid字段指向双亲节点（记录行）的id字段。
这与顺序实现的原理如出一辙！
其中最典型的案例当数省市区名称：
例如：（这里主要是为了说明结构，其中部分信息可能有误）
| id | name | pid |
|---|---|---|
| 1 | 四川省 | NULL |
| 2 | 成都市 | 1 |
| 3 | 锦江区 | 2 |
| 4 | 青羊区 | 2 |
| 5 | 金牛区 | 2 |
| 6 | 武侯区 | 2 |
| 7 | 成华区 | 2 |
| 8 | 湖北省 | NULL |
| 9 | 武汉市 | 8 |
| 10 | 江汉区 | 9 |
| 11 | 硚口区 | 9 |
| 12 | 汉阳区 | 9 |
| 13 | 武昌区 | 9 |
| 14 | 青山区 | 9 |
其中:
- 四川省和湖北省在数据库里可看作根节点，pid为NULL。但其实这里可以看作是省略了国家这一根节点。
- 成都市和武汉市的pid为对应的省id。
- 成都市和武汉市管辖区县的pid为各自城市id。
这样通过自关联构建了成都和武汉的省市区三级层级关系。
可以统计每个省下面分别有多少个城市和区县等信息。例如：
SELECT
p.name AS 省份,
COUNT(DISTINCT c.id) AS 城市数量,
COUNT(DISTINCT d.id) AS 区县数量
FROM province p
LEFT JOIN city c ON c.pid = p.id
LEFT JOIN district d ON d.pid = c.id
GROUP BY p.name;
结果：
省份 城市数量 区县数量
四川省 1 5
湖北省 1 5
自关联是表达树形层级逻辑非常直观的数据库模式设计技术。
总结
- 广度优先遍历（BFS）和深度优先遍历（DFS）算法是两种关键的树遍历算法。BFS按层次顺序遍历树，DFS递归访问每个分支。
- 通常来讲，广度优先遍历（BFS）和深度优先遍历（DFS）算法的时间复杂度均为O(n)。
- 树可以通过链式实现，设置指向孩子节点的指针，也可以通过顺序实现，设置指向双亲的指针。
- 关系型数据库自关联也可表达树结构。数据库表通过引用双亲节点的id字段建立双亲-孩子关系，实现树形数据模型。
