树形结构遍历分为深度优先（dfs）和广度优先（bfs）；dfs按访问根节点时机分为前序、中序、后序，分别适用于复制树、获取有序序列、计算子节点依赖场景；bfs通过队列实现层序访问，适合查找最短路径或最近匹配；搜索时可基于dfs或bfs框架，在节点访问时加入条件判断，如根据aname查找“袁隆平”节点。
树形结构在前端开发中非常常见，从DOM树到复杂的菜单、文件目录，都离不开它。掌握其遍历与搜索方法，是处理这类数据的关键。
深度优先遍历（DFS）
深度优先遍历会沿着一个分支一直深入下去，直到无法继续，再回溯去探索其他分支。它通常使用递归实现，代码简洁易懂。
根据访问“根节点”的时机不同，又分为三种：
- 前序遍历：先访问当前节点，再递归地前序遍历左子树和右子树。这种顺序很符合直觉，常用于复制或克隆一棵树，因为需要先创建父节点。
- 中序遍历：先递归地中序遍历左子树，然后访问当前节点，最后中序遍历右子树。对于二叉搜索树（BST），中序遍历的结果是一个有序序列。
- 后序遍历：先递归地后序遍历左右子树，最后访问当前节点。这在计算文件夹大小时很有用，必须先知道所有子文件的大小，才能得出父文件夹的总大小。
例如，对于一个包含科学家信息的树形菜单，如果想按层级展开并记录每个节点，前序遍历是最直接的选择。
立即学习“前端免费学习笔记（深入）”；
广度优先遍历（BFS）
广度优先遍历，也叫层序遍历，它像水波一样一圈一圈地向外扩散。首先访问根节点，然后是根的所有直接子节点，接着是这些子节点的子节点，以此类推。
这种遍历方式通常借助队列来实现。将根节点入队，然后循环执行：出队一个节点并访问它，再将其所有子节点依次入队。这样能保证同一层级的节点被连续访问。
BFS的一个典型应用场景是寻找最短路径。比如在一个组织架构树中查找两个人之间的最小层级关系，BFS能确保第一次找到目标时，就是经过最少跳转的路径。
树形数据的搜索
有了遍历的基础，搜索就变得简单了。搜索的目标是在树中找到一个或多个满足特定条件的节点。
你可以选择DFS或BFS的框架，在访问每个节点时进行判断：
- 如果使用递归的DFS，可以在函数中加入判断逻辑，一旦找到目标节点，就可以立即返回结果，效率很高。
- 如果使用BFS，则更适合找离根节点最近的匹配项，因为它是一层一层找的。
例如，给定一个由id和pid构成的扁平数组，需要转换成树并查找名为“袁隆平”的科学家。可以先用DFS遍历构建好的树，当某个节点的aname等于“袁隆平”时，就返回该节点信息。基本上就这些，不复杂但容易忽略细节。
