树的遍历算法：前序、中序、后序遍历的实现

# 1. 树的基本概念与定义

树（Tree）是一种重要的非线性数据结构，它由若干个节点（Node）组成，这些节点之间存在着特定的层次关系。树是一种层次化的结构，由根节点、若干子树以及节点之间的链接组成。

## 1.1 树的结构与节点

在树中，每个节点可以有零个或多个子节点，子节点也可以有自己的子节点，形成了树的层次结构。树的基本结构如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

在上面的代码中，`TreeNode`表示树中的一个节点，包含一个值`val`和左右子节点。根据树的应用场景不同，节点中可能包含其他属性。

## 1.2 树的遍历方法概述

树的遍历是指按照某种顺序访问树的所有节点。常见的树的遍历方式有三种：

- **前序遍历**（Pre-order traversal）：先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
- **中序遍历**（In-order traversal）：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
- **后序遍历**（Post-order traversal）：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。

这三种遍历方式各有特点，适用于不同的场景。接下来将详细介绍前序、中序、后序遍历的实现方法。

# 2. 前序遍历算法实现

在树的遍历算法中，前序遍历是一种常用且重要的方式。通过前序遍历可以以根节点 -> 左子树 -> 右子树的顺序访问树中的所有节点。接下来我们将介绍前序遍历算法的实现方法，包括递归实现和迭代实现，并对其复杂度和应用场景进行分析。

### 2.1 递归方法的实现

递归方式是前序遍历的经典实现方式，实现简洁清晰，代码如下（以Python为例）：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversalRecursive(root):
    if not root:
        return []
    return [root.val] + preorderTraversalRecursive(root.left) + preorderTraversalRecursive(root.right)

# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorderTraversalRecursive(root))  # Output: [1, 2, 4, 5, 3]

#### 代码说明
- 定义了树节点类 `TreeNode`，包含节点值、左子树和右子树。
- 实现了递归函数 `preorderTraversalRecursive`，按照根左右的顺序进行前序遍历。
- 示例创建了一颗二叉树，并进行前序遍历。

### 2.2 迭代方法的实现

除了递归方法，我们也可以使用迭代的方式实现前序遍历。迭代方法通常借助栈来辅助实现，代码如下（以Java为例）：

public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return result;
}

// 示例
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println(preorderTraversalIterative(root));  // Output: [1, 2, 4, 5, 3]

#### 代码说明
- 定义了树节点类 `TreeNode`。
- 实现了迭代方法 `preorderTraversalIterative`，使用栈来辅助实现前序遍历。
- 示例创建了一颗二叉树，并进行前序遍历。

### 2.3 复杂度分析与应用场景

- 递归方法的时间复杂度为 O(N)，空间复杂度取决于递归调用栈的深度，最坏情况下为 O(N)。
- 迭代方法的时间复杂度同样为 O(N)，空间复杂度取决于栈的使用，最坏情况下为 O(N)。
- 前序遍历常用于深度优先搜索，查找路径等场景。

通过前序遍历的实现，我们可以更好地理解树的结构与节点之间的关系，为后续章节的内容做好铺垫。

# 3. 中序遍历算法