树形结构遍历与搜索技巧分享

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《树形结构遍历与搜索在前端的应用》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~

树形结构遍历分为深度优先（DFS）和广度优先（BFS）；DFS按访问根节点时机分为前序、中序、后序，分别适用于复制树、获取有序序列、计算子节点依赖场景；BFS通过队列实现层序访问，适合查找最短路径或最近匹配；搜索时可基于DFS或BFS框架，在节点访问时加入条件判断，如根据aname查找“袁隆平”节点。

树形结构在前端开发中非常常见，从DOM树到复杂的菜单、文件目录，都离不开它。掌握其遍历与搜索方法，是处理这类数据的关键。

深度优先遍历（DFS）

深度优先遍历会沿着一个分支一直深入下去，直到无法继续，再回溯去探索其他分支。它通常使用递归实现，代码简洁易懂。

根据访问“根节点”的时机不同，又分为三种：

• 前序遍历：先访问当前节点，再递归地前序遍历左子树和右子树。这种顺序很符合直觉，常用于复制或克隆一棵树，因为需要先创建父节点。
• 中序遍历：先递归地中序遍历左子树，然后访问当前节点，最后中序遍历右子树。对于二叉搜索树（BST），中序遍历的结果是一个有序序列。
• 后序遍历：先递归地后序遍历左右子树，最后访问当前节点。这在计算文件夹大小时很有用，必须先知道所有子文件的大小，才能得出父文件夹的总大小。

例如，对于一个包含科学家信息的树形菜单，如果想按层级展开并记录每个节点，前序遍历是最直接的选择。

广度优先遍历（BFS）

广度优先遍历，也叫层序遍历，它像水波一样一圈一圈地向外扩散。首先访问根节点，然后是根的所有直接子节点，接着是这些子节点的子节点，以此类推。

这种遍历方式通常借助队列来实现。将根节点入队，然后循环执行：出队一个节点并访问它，再将其所有子节点依次入队。这样能保证同一层级的节点被连续访问。

BFS的一个典型应用场景是寻找最短路径。比如在一个组织架构树中查找两个人之间的最小层级关系，BFS能确保第一次找到目标时，就是经过最少跳转的路径。

树形数据的搜索

有了遍历的基础，搜索就变得简单了。搜索的目标是在树中找到一个或多个满足特定条件的节点。

你可以选择DFS或BFS的框架，在访问每个节点时进行判断：

• 如果使用递归的DFS，可以在函数中加入判断逻辑，一旦找到目标节点，就可以立即返回结果，效率很高。
• 如果使用BFS，则更适合找离根节点最近的匹配项，因为它是一层一层找的。

例如，给定一个由id和pid构成的扁平数组，需要转换成树并查找名为“袁隆平”的科学家。可以先用DFS遍历构建好的树，当某个节点的aname等于“袁隆平”时，就返回该节点信息。基本上就这些，不复杂但容易忽略细节。

以上就是《树形结构遍历与搜索技巧分享》的详细内容，更多关于数据结构,树形结构的资料请关注golang学习网公众号！