链式实现：指向孩子节点的指针

使用“指向孩子节点的指针”，从root节点开始，使用指针将所有节点连成一个整体。

这里我还实现了广度优先遍历（BFS）和深度优先遍历（DFS）算法。其时间复杂度均为O(n)。

这种情况下，BFS利用队列进行遍历，DFS利用栈进行遍历。关于其中的DFS，这里的栈主要是指函数调用栈，也就是利用递归来实现。

广度优先遍历主要思路是：

1. 利用队列进行遍历
2. 从根节点开始把节点按顺序放入队列
3. 每次从队列中取出一个节点，访问数据
4. 然后将该节点的所有子节点入队
5. 循环直到队列为空

深度优先遍历的关键是利用递归，主要步骤是:

1. 访问当前节点数据
2. 对当前节点的所有子节点递归调用dfs函数
3. 进入每个子节点后，重复1、2步骤
4. 递归调用结束后回溯到上一层

这样通过递归不断向更深层遍历，从而完成整棵树的遍历。递归会能保证从某一节点完整遍历其子树，再回溯到上一层节点。

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)]

顺序实现：指向双亲节点的指针

使用“指向双亲节点的指针”，来表达树的层级结构，但这样做无法从双亲节点访问孩子节点，因而无法遍历，因此，使用一个顺序表，存储所有的节点。

这种情况下，有三种遍历方式：

1. 直接遍历顺序表，时间复杂度O(n)。
2. 广度优先遍历（BFS），时间复杂度O(n^2)。
3. 深度优先遍历（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字段。

这与顺序实现的原理如出一辙！

其中最典型的案例当数省市区名称：

例如：（这里主要是为了说明结构，其中部分信息可能有误）

其中:

• 四川省和湖北省在数据库里可看作根节点，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字段建立双亲-孩子关系，实现树形数据模型。