一旦树结构建立起来,无论是用于索引的二叉搜索树还是用于分类的决策树,我们通常都需要一种系统地访问每个节点的方法。这个过程称为树遍历。不同的遍历方法以不同的顺序访问节点,使它们适用于各种任务,例如提取信息、评估树表示的表达式,或者简单地处理所有元素。遍历树有两种主要方法:深度优先搜索 (DFS) 和广度优先搜索 (BFS)。在DFS内部,有三种常见变体。digraph TreeTraversalExample { rankdir=TB; node [shape=circle, style=filled, fontname="Helvetica", fontsize=12, fixedsize=true, width=0.5, height=0.5]; edge [fontname="Helvetica", fontsize=10]; // 节点 Node_10 [label="10", fillcolor="#228be6"]; // 根节点 - 蓝色 Node_5 [label="5", fillcolor="#40c057"]; // 绿色 Node_15 [label="15", fillcolor="#40c057"]; // 绿色 Node_3 [label="3", fillcolor="#fab005"]; // 黄色 Node_7 [label="7", fillcolor="#fab005"]; // 黄色 Node_12 [label="12", fillcolor="#fab005"]; // 黄色 Node_18 [label="18", fillcolor="#fab005"]; // 黄色 // 边 Node_10 -> Node_5 [label="L"]; Node_10 -> Node_15 [label="R"]; Node_5 -> Node_3 [label="L"]; Node_5 -> Node_7 [label="R"]; Node_15 -> Node_12 [label="L"]; Node_15 -> Node_18 [label="R"]; }一个用于演示遍历方法的简单二叉树。'L' 表示左子节点,'R' 表示右子节点。深度优先搜索 (DFS) 遍历DFS 尽可能深入一条分支,然后回溯。三种主要的DFS遍历方法在访问当前节点相对于其左右子树的顺序上有所不同。中序遍历 (左、节点、右)访问左子树。访问当前节点。访问右子树。示例输出: 3, 5, 7, 10, 12, 15, 18用途: 对于二叉搜索树(如我们的例子,如果被解释为二叉搜索树),中序遍历按升序访问节点。这对于高效地获取排序数据非常有用。先序遍历 (节点、左、右)访问当前节点。访问左子树。访问右子树。示例输出: 10, 5, 3, 7, 15, 12, 18用途: 先序遍历常用于创建树的副本或序列化它(保存其结构)。它也是在前缀表示法(波兰表示法)表达式中评估节点的顺序。在决策树中,从根节点遍历路径遵循相对于该特定路径中已访问节点的先序逻辑。后序遍历 (左、右、节点)访问左子树。访问右子树。访问当前节点。示例输出: 3, 7, 5, 12, 18, 15, 10用途: 后序遍历通常用于删除树中的节点(需要先删除子节点,再删除父节点)或评估后缀表示法(逆波兰表示法)表达式。DFS遍历通常递归实现,这种方法通常优雅且符合定义。它们也可以使用显式栈数据结构进行迭代实现。广度优先搜索 (BFS) 遍历 (层序遍历)BFS 逐层访问节点,从上到下,在每层中从左到右。层序遍历访问深度为0的节点(根节点)。访问深度为1的节点。访问深度为2的节点,依此类推。示例输出: 10, 5, 15, 3, 7, 12, 18用途: BFS 用于需要逐层查看树的场景。在边数方面,它找到从根节点到任何其他节点的最短路径。它使用队列数据结构进行迭代实现。机器学习背景下的遍历理解树遍历在机器学习中很重要,原因如下:决策树预测: 使用已训练的决策树进行预测本身就涉及树遍历。从根节点开始,根据输入特征值沿着分支前进,直到到达包含预测的叶节点。这本质上是一种特定路径的遍历,由数据引导。模型检查与解释: 遍历决策树(例如,先序或层序)可让您查看其结构、理解其分割,并可能提取人类可读的规则。您可能希望找到特定深度的所有节点(BFS)或打印到每个叶节点的规则路径(DFS)。特征提取: 在一些特定情况中,穿过树的路径或树结构本身可能被用作另一个模型的特征,需要遍历来获取这些信息。二叉搜索树操作: 如果使用二叉搜索树或平衡树来索引数据点(例如,在某些最近邻预计算方案中),中序遍历提供排序访问,而其他遍历可能用于维护。实现与复杂度在Python中实现这些遍历可以递归完成(对于DFS),也可以迭代完成(使用列表作为DFS的栈,或使用collections.deque作为BFS的队列)。时间复杂度: 所有标准遍历方法(中序、先序、后序、层序)都需要精确访问每个节点一次。因此,对于一个有 $n$ 个节点的树,时间复杂度是 $O(n)$。空间复杂度:对于递归DFS,空间复杂度由递归栈的最大深度决定,对应于树的高度 ($h$)。在最佳情况(平衡树)下,$h = O(\log n)$。在最坏情况(斜树)下,$h = O(n)$。对于使用栈的迭代DFS,空间复杂度也与高度相关,$O(h)$。对于使用队列的BFS,空间复杂度由任意单个级别的最大节点数(树的宽度 $w$)决定。在最坏情况(完全二叉树)下,最后一层可以包含大约 $n/2$ 个节点,导致 $O(n)$ 的空间复杂度。选择正确的遍历方法取决于您希望通过树结构实现什么,无论是提取排序数据、理解模型结构,还是实现核心树操作。