Python实现二叉树遍历及操作

"这篇文档详细介绍了如何在Python中实现二叉树的各种遍历方法，包括先序、中序、后序遍历以及宽度优先遍历。同时，还涉及到了二叉树的深度计算和到达叶子节点的所有路径。文档提供了一个简单的二叉树节点类`TreeNode`的定义，并给出了各种遍历的递归和迭代实现代码。" 二叉树是一种重要的数据结构，广泛应用于计算机科学的各个领域，如编译器设计、文件系统、搜索算法等。在Python中，我们可以自定义类来构建二叉树结构。在这个文档中，作者首先定义了一个基本的二叉树节点类`TreeNode`，它包含三个属性：节点值`val`、左子节点`left`和右子节点`right`。 接下来，文档详细讲解了二叉树的四种遍历方法： 1. **先序遍历**：先访问根节点，然后遍历左子树，最后遍历右子树。递归实现时，首先检查节点是否为空，若非空则打印节点值，再分别递归遍历左子节点和右子节点。迭代实现则是利用栈，先将根节点压入栈，然后循环处理栈顶元素，直到栈为空。 2. **中序遍历**：先遍历左子树，然后访问根节点，最后遍历右子树。递归实现中，先递归遍历左子节点，然后打印根节点值，最后递归遍历右子节点。迭代实现与先序遍历类似，但需在节点入栈前将其右子节点压入栈，确保正确顺序。 3. **后序遍历**：先遍历左子树，然后遍历右子树，最后访问根节点。递归实现时，先递归遍历左右子树，最后打印根节点值。迭代实现较复杂，通常使用两个栈，一个用于存储待访问的子树，另一个记录当前访问节点，以便正确地按后序顺序打印。 4. **宽度优先遍历（BFS）**：从根节点开始，按照层级顺序遍历所有节点。可以使用队列数据结构实现，依次将根节点及其子节点入队，然后出队并访问，再将当前层未访问的子节点入队。 此外，文档还提到了计算二叉树的深度和获取到叶子节点的所有路径。二叉树的深度通常可以通过递归方式求解，对于每个节点，其深度等于左子树深度和右子树深度中的较大值加1。到达叶子节点的所有路径则可以通过深度优先遍历并记录路径来获取。 这个文档提供了完整的Python代码示例，对于理解和实现二叉树的基本操作非常有帮助，无论是对初学者还是有一定经验的开发者，都是很好的学习参考资料。