C++二叉树遍历方法详解

C++中二叉树遍历有四种主要方式：1. 前序遍历（根-左-右），递归或栈实现；2. 中序遍历（左-根-右），常用于BST获取有序序列；3. 后序遍历（左-右-根），适用于释放内存；4. 层序遍历（广度优先），使用队列按层访问节点。

在C++中，二叉树的遍历主要有四种常见方式：前序遍历、中序遍历、后序遍历和层序遍历（广度优先）。每种遍历方式访问节点的顺序不同，适用于不同的场景。下面详细介绍这些方法的实现。

1. 二叉树节点定义

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 前序遍历（根-左-右）

前序遍历先访问根节点，然后递归地遍历左子树，最后遍历右子树。

递归实现：

迭代实现（使用栈）：

3. 中序遍历（左-根-右）

中序遍历常用于二叉搜索树，可以得到有序序列。

递归实现：

迭代实现：

4. 后序遍历（左-右-根）

后序遍历在删除节点或释放内存时很有用。

递归实现：

迭代实现（双栈法）：

5. 层序遍历（从上到下，从左到右）

层序遍历使用队列实现，适合按层级处理节点。

基本上就这些。根据实际需求选择合适的遍历方式，递归写法简洁易懂，迭代写法更节省系统栈空间。不复杂但容易忽略细节，比如空指针判断和入栈顺序。