hello-algo二叉树遍历详解——BFS 层序遍历与 DFS 前中后序遍历的两种体系【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo树是一种基于链表的物理结构却是一种非线性的逻辑结构因此无法像链表那样从头节点一路指针走到底而必须借助搜索算法来系统性地访问每个节点。本文基于 hello-algo 仓库中 二叉树遍历文档 展开完整讲解二叉树两大遍历体系——广度优先的层序遍历BFS与深度优先的前序/中序/后序遍历DFS并对照仓库中 Python、C、Go 等多语言源码给出可复制实现的代码、输出序列与复杂度结论帮助读者真正掌握二叉树遍历的原理与工程实现。一、遍历为什么比链表更难从物理结构的角度看树是一种基于链表的数据结构遍历方式是顺着指针逐个访问节点。但树是非线性结构一个节点可能分叉出左右两个子树若只是“走到下一个指针”就会遗漏分支因此遍历必须借助搜索算法来实现广度优先搜索breadth-first search, BFS体现“一圈一圈向外扩展”的逐层推进思路对应层序遍历深度优先搜索depth-first search, DFS体现“先走到尽头再回溯继续”的深入思路对应前序、中序、后序遍历。下面分别结合 hello-algo 仓库源码讲解这两套遍历的算法与实现。二、层序遍历BFS层序遍历level-order traversal从顶部到底部逐层遍历二叉树并在每一层按照从左到右的顺序访问节点。如上图中那棵 7 节点树层序访问顺序为1, 2, 3, 4, 5, 6, 7先第 1 层的 1再第 2 层的 2、3最后第 3 层的 4、5、6、7。2.1 算法思路广度优先遍历通常借助队列实现队列遵循“先进先出”的规则而广度优先遍历遵循“逐层推进”的规则两者背后的思想一致——当前层的节点先出队处理其子节点入队等待下一轮天然保证了“逐层、从左到右”的访问次序。2.2 代码实现Python仓库中 binary_tree_bfs.py 的level_order函数是标准实现def level_order(root: TreeNode | None) - list[int]: 层序遍历 # 初始化队列加入根节点 queue: deque[TreeNode] deque() queue.append(root) # 初始化一个列表用于保存遍历序列 res [] while queue: node: TreeNode queue.popleft() # 队列出队 res.append(node.val) # 保存节点值 if node.left is not None: queue.append(node.left) # 左子节点入队 if node.right is not None: queue.append(node.right) # 右子节点入队 return res实现要点根节点先入队循环以队列非空为终止条件出队即“访问”把node.val追加进结果列表左、右子节点按左前右后的顺序入队保证同一层从左到右的次序。驱动代码中使用了list_to_tree(arr[1, 2, 3, 4, 5, 6, 7])从数组直接构造一棵满二叉树该工具函数定义在 tree_node.py其内部通过递归按“下标i的左子节点在2*i1、右子节点在2*i2”的数组表示规则反序列化建树。2.3 多语言实现对照仓库提供了与 Python 版逻辑完全一致的多语言实现可以互相印证Cbinary_tree_bfs.cpp 的levelOrder使用std::queueTreeNode*与std::vectorint通过queue.front()/queue.pop()出队访问Gobinary_tree_bfs.go 的levelOrder使用标准库container/list的双向链表作队列queue.Remove(queue.Front())出队此外Java、C#、JavaScript、TypeScript、Kotlin、Swift、Rust、Ruby 等版本也分别在 codes/java/chapter_tree/、codes/csharp/、codes/rust/ 等目录下提供了对应的levelOrder实现核心步骤入队根节点 → 出队访问 → 左右子节点入队完全一致。2.4 复杂度分析时间复杂度为 O(n)所有节点被访问一次使用 O(n) 时间其中 n 为节点数量。空间复杂度为 O(n)在最差情况下即满二叉树时遍历到最底层之前队列中最多同时存在 (n1)/2 个节点即倒数一层的全部节点加上最后一层的一半占用 O(n) 空间。三、前序、中序、后序遍历DFS对应层序遍历前序、中序和后序遍历都属于深度优先遍历体现“先走到尽头再回溯继续”的遍历方式。3.1 核心原理绕树一圈三个访问位置深度优先遍历就像是绕着整棵二叉树的外围“走”一圈在每个节点都会遇到三个位置分别对应前序遍历、中序遍历和后序遍历前序进入节点时访问左子树之前记录中序左子树访问完、即将访问右子树时记录后序左右子树都访问完、函数返回前记录。以下图第 4 步为例虚线表示“已走过的路径”实线箭头表示“即将深入的方向”。图中节点 1、2、4 已经被访问前序序列为1, 2, 4搜索路径正沿虚线向上回溯准备进入节点 4 的右兄弟节点 5。以这棵 7 节点满二叉树为例三种深度优先遍历的输出序列分别为与上图标注一致遍历方式访问时机节点访问序列前序遍历根 → 左 → 右1, 2, 4, 5, 3, 6, 7中序遍历左 → 根 → 右4, 2, 5, 1, 6, 3, 7后序遍历左 → 右 → 根4, 5, 2, 6, 7, 3, 1一个值得注意的细节前序序列恰好与层序序列不同但都以 1 开头而中序、后序序列首元素都是最左边的节点 4——这与“沿左子树一路深入”的搜索方向完全吻合。3.2 代码实现Python深度优先搜索通常基于递归实现。仓库 binary_tree_dfs.py 给出了三个函数它们结构几乎完全相同唯一的区别就是res.append(root.val)这一“访问”语句的位置def pre_order(root: TreeNode | None): 前序遍历 if root is None: return # 访问优先级根节点 - 左子树 - 右子树 res.append(root.val) pre_order(rootroot.left) pre_order(rootroot.right) def in_order(root: TreeNode | None): 中序遍历 if root is None: return # 访问优先级左子树 - 根节点 - 右子树 in_order(rootroot.left) res.append(root.val) in_order(rootroot.right) def post_order(root: TreeNode | None): 后序遍历 if root is None: return # 访问优先级左子树 - 右子树 - 根节点 post_order(rootroot.left) post_order(rootroot.right) res.append(root.val)实现要点递归终止条件root is None时直接返回保证空子树不会触发越界访问三种遍历的差异仅在访问语句的位置放在两个递归调用之前即前序、夹在中间即中序、放在之后即后序从源码结构看res是一个模块级共享列表驱动代码中通过res.clear()在三种遍历之间复用见 binary_tree_dfs.py 的 main 部分避免每次遍历都新建列表。3.3 递归的“递”与“归”前序遍历的递归过程可分为两个逆向的部分“递”开启新方法程序沿指针向下推进访问下一个节点“归”函数返回代表当前节点已经访问完毕回溯到父节点继续处理右子树。文档原文档配有 11 步动画序列preorder_step1.png~preorder_step11.png位于 binary_tree_traversal.assets完整演示了从根节点出发、一路“递”到节点 4再“归”回并逐个处理 5、3、6、7 的全过程。读者可以对照动画理解递归栈帧的压入与弹出。3.4 多语言实现对照Cbinary_tree_dfs.cpp 中同样提供preOrder、inOrder、postOrder三个函数使用文件作用域的全局vectorint vec保存序列main 中每次调用前执行vec.clear()其余语言Java、C#、Go、JavaScript、TypeScript、Kotlin、Swift、Rust 等在各自chapter_tree目录下均有等价实现如 codes/java/chapter_tree/binary_tree_dfs.java、codes/go/chapter_tree/。值得指出的是原文档提示深度优先搜索也可以基于迭代实现用显式栈模拟递归有兴趣的读者可以在仓库的其他章节代码中继续研究。3.5 复杂度分析时间复杂度为 O(n)所有节点被访问一次使用 O(n) 时间空间复杂度为 O(n)在最差情况下即树退化为链表每个节点只有一个子节点时递归深度达到 n系统占用 O(n) 栈帧空间。与层序遍历的空间开销来源不同BFS 的 O(n) 来自队列DFS 的 O(n) 来自递归调用栈。四、两种遍历体系对比总结维度层序遍历BFS前/中/后序遍历DFS搜索思想一圈一圈向外扩展逐层推进先走到尽头再回溯继续辅助数据结构队列先进先出递归调用栈可改为显式栈迭代时间复杂度O(n)O(n)空间复杂度O(n)满二叉树时队列最多 (n1)/2 个节点O(n)树退化为链表时递归深度达 n仓库参考实现Python、C、GoPython、C五、小结hello-algo 的 二叉树遍历文档 通过“外围绕一圈”的视角把四种遍历统一为两个体系层序遍历用队列逐层扩展前中后序遍历用递归深入并回溯三者差别只是“访问节点”这一动作在递归中的位置。仓库中各语言的实现代码level_order/levelOrder与pre_order/in_order/post_order与文档描述一一对应且驱动代码统一使用list_to_tree([1, 2, 3, 4, 5, 6, 7])构造满二叉树可以直接运行验证层序1,2,3,4,5,6,7、前序1,2,4,5,3,6,7、中序4,2,5,1,6,3,7、后序4,5,2,6,7,3,1四组输出序列是理解二叉树遍历原理与工程落地的完整材料。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
hello-algo：二叉树遍历详解——BFS 层序遍历与 DFS 前中后序遍历的两种体系
hello-algo二叉树遍历详解——BFS 层序遍历与 DFS 前中后序遍历的两种体系【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo树是一种基于链表的物理结构却是一种非线性的逻辑结构因此无法像链表那样从头节点一路指针走到底而必须借助搜索算法来系统性地访问每个节点。本文基于 hello-algo 仓库中 二叉树遍历文档 展开完整讲解二叉树两大遍历体系——广度优先的层序遍历BFS与深度优先的前序/中序/后序遍历DFS并对照仓库中 Python、C、Go 等多语言源码给出可复制实现的代码、输出序列与复杂度结论帮助读者真正掌握二叉树遍历的原理与工程实现。一、遍历为什么比链表更难从物理结构的角度看树是一种基于链表的数据结构遍历方式是顺着指针逐个访问节点。但树是非线性结构一个节点可能分叉出左右两个子树若只是“走到下一个指针”就会遗漏分支因此遍历必须借助搜索算法来实现广度优先搜索breadth-first search, BFS体现“一圈一圈向外扩展”的逐层推进思路对应层序遍历深度优先搜索depth-first search, DFS体现“先走到尽头再回溯继续”的深入思路对应前序、中序、后序遍历。下面分别结合 hello-algo 仓库源码讲解这两套遍历的算法与实现。二、层序遍历BFS层序遍历level-order traversal从顶部到底部逐层遍历二叉树并在每一层按照从左到右的顺序访问节点。如上图中那棵 7 节点树层序访问顺序为1, 2, 3, 4, 5, 6, 7先第 1 层的 1再第 2 层的 2、3最后第 3 层的 4、5、6、7。2.1 算法思路广度优先遍历通常借助队列实现队列遵循“先进先出”的规则而广度优先遍历遵循“逐层推进”的规则两者背后的思想一致——当前层的节点先出队处理其子节点入队等待下一轮天然保证了“逐层、从左到右”的访问次序。2.2 代码实现Python仓库中 binary_tree_bfs.py 的level_order函数是标准实现def level_order(root: TreeNode | None) - list[int]: 层序遍历 # 初始化队列加入根节点 queue: deque[TreeNode] deque() queue.append(root) # 初始化一个列表用于保存遍历序列 res [] while queue: node: TreeNode queue.popleft() # 队列出队 res.append(node.val) # 保存节点值 if node.left is not None: queue.append(node.left) # 左子节点入队 if node.right is not None: queue.append(node.right) # 右子节点入队 return res实现要点根节点先入队循环以队列非空为终止条件出队即“访问”把node.val追加进结果列表左、右子节点按左前右后的顺序入队保证同一层从左到右的次序。驱动代码中使用了list_to_tree(arr[1, 2, 3, 4, 5, 6, 7])从数组直接构造一棵满二叉树该工具函数定义在 tree_node.py其内部通过递归按“下标i的左子节点在2*i1、右子节点在2*i2”的数组表示规则反序列化建树。2.3 多语言实现对照仓库提供了与 Python 版逻辑完全一致的多语言实现可以互相印证Cbinary_tree_bfs.cpp 的levelOrder使用std::queueTreeNode*与std::vectorint通过queue.front()/queue.pop()出队访问Gobinary_tree_bfs.go 的levelOrder使用标准库container/list的双向链表作队列queue.Remove(queue.Front())出队此外Java、C#、JavaScript、TypeScript、Kotlin、Swift、Rust、Ruby 等版本也分别在 codes/java/chapter_tree/、codes/csharp/、codes/rust/ 等目录下提供了对应的levelOrder实现核心步骤入队根节点 → 出队访问 → 左右子节点入队完全一致。2.4 复杂度分析时间复杂度为 O(n)所有节点被访问一次使用 O(n) 时间其中 n 为节点数量。空间复杂度为 O(n)在最差情况下即满二叉树时遍历到最底层之前队列中最多同时存在 (n1)/2 个节点即倒数一层的全部节点加上最后一层的一半占用 O(n) 空间。三、前序、中序、后序遍历DFS对应层序遍历前序、中序和后序遍历都属于深度优先遍历体现“先走到尽头再回溯继续”的遍历方式。3.1 核心原理绕树一圈三个访问位置深度优先遍历就像是绕着整棵二叉树的外围“走”一圈在每个节点都会遇到三个位置分别对应前序遍历、中序遍历和后序遍历前序进入节点时访问左子树之前记录中序左子树访问完、即将访问右子树时记录后序左右子树都访问完、函数返回前记录。以下图第 4 步为例虚线表示“已走过的路径”实线箭头表示“即将深入的方向”。图中节点 1、2、4 已经被访问前序序列为1, 2, 4搜索路径正沿虚线向上回溯准备进入节点 4 的右兄弟节点 5。以这棵 7 节点满二叉树为例三种深度优先遍历的输出序列分别为与上图标注一致遍历方式访问时机节点访问序列前序遍历根 → 左 → 右1, 2, 4, 5, 3, 6, 7中序遍历左 → 根 → 右4, 2, 5, 1, 6, 3, 7后序遍历左 → 右 → 根4, 5, 2, 6, 7, 3, 1一个值得注意的细节前序序列恰好与层序序列不同但都以 1 开头而中序、后序序列首元素都是最左边的节点 4——这与“沿左子树一路深入”的搜索方向完全吻合。3.2 代码实现Python深度优先搜索通常基于递归实现。仓库 binary_tree_dfs.py 给出了三个函数它们结构几乎完全相同唯一的区别就是res.append(root.val)这一“访问”语句的位置def pre_order(root: TreeNode | None): 前序遍历 if root is None: return # 访问优先级根节点 - 左子树 - 右子树 res.append(root.val) pre_order(rootroot.left) pre_order(rootroot.right) def in_order(root: TreeNode | None): 中序遍历 if root is None: return # 访问优先级左子树 - 根节点 - 右子树 in_order(rootroot.left) res.append(root.val) in_order(rootroot.right) def post_order(root: TreeNode | None): 后序遍历 if root is None: return # 访问优先级左子树 - 右子树 - 根节点 post_order(rootroot.left) post_order(rootroot.right) res.append(root.val)实现要点递归终止条件root is None时直接返回保证空子树不会触发越界访问三种遍历的差异仅在访问语句的位置放在两个递归调用之前即前序、夹在中间即中序、放在之后即后序从源码结构看res是一个模块级共享列表驱动代码中通过res.clear()在三种遍历之间复用见 binary_tree_dfs.py 的 main 部分避免每次遍历都新建列表。3.3 递归的“递”与“归”前序遍历的递归过程可分为两个逆向的部分“递”开启新方法程序沿指针向下推进访问下一个节点“归”函数返回代表当前节点已经访问完毕回溯到父节点继续处理右子树。文档原文档配有 11 步动画序列preorder_step1.png~preorder_step11.png位于 binary_tree_traversal.assets完整演示了从根节点出发、一路“递”到节点 4再“归”回并逐个处理 5、3、6、7 的全过程。读者可以对照动画理解递归栈帧的压入与弹出。3.4 多语言实现对照Cbinary_tree_dfs.cpp 中同样提供preOrder、inOrder、postOrder三个函数使用文件作用域的全局vectorint vec保存序列main 中每次调用前执行vec.clear()其余语言Java、C#、Go、JavaScript、TypeScript、Kotlin、Swift、Rust 等在各自chapter_tree目录下均有等价实现如 codes/java/chapter_tree/binary_tree_dfs.java、codes/go/chapter_tree/。值得指出的是原文档提示深度优先搜索也可以基于迭代实现用显式栈模拟递归有兴趣的读者可以在仓库的其他章节代码中继续研究。3.5 复杂度分析时间复杂度为 O(n)所有节点被访问一次使用 O(n) 时间空间复杂度为 O(n)在最差情况下即树退化为链表每个节点只有一个子节点时递归深度达到 n系统占用 O(n) 栈帧空间。与层序遍历的空间开销来源不同BFS 的 O(n) 来自队列DFS 的 O(n) 来自递归调用栈。四、两种遍历体系对比总结维度层序遍历BFS前/中/后序遍历DFS搜索思想一圈一圈向外扩展逐层推进先走到尽头再回溯继续辅助数据结构队列先进先出递归调用栈可改为显式栈迭代时间复杂度O(n)O(n)空间复杂度O(n)满二叉树时队列最多 (n1)/2 个节点O(n)树退化为链表时递归深度达 n仓库参考实现Python、C、GoPython、C五、小结hello-algo 的 二叉树遍历文档 通过“外围绕一圈”的视角把四种遍历统一为两个体系层序遍历用队列逐层扩展前中后序遍历用递归深入并回溯三者差别只是“访问节点”这一动作在递归中的位置。仓库中各语言的实现代码level_order/levelOrder与pre_order/in_order/post_order与文档描述一一对应且驱动代码统一使用list_to_tree([1, 2, 3, 4, 5, 6, 7])构造满二叉树可以直接运行验证层序1,2,3,4,5,6,7、前序1,2,4,5,3,6,7、中序4,2,5,1,6,3,7、后序4,5,2,6,7,3,1四组输出序列是理解二叉树遍历原理与工程落地的完整材料。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
