c++中如何实现二叉树遍历_c++二叉树前序中序后序递归算法【汇总】_技术教程

前序遍
历是根→左→右，必须先访问节点再递归左右子树；中序遍历是左→根→右，BST中序结果升序；后序遍历是左→右→根，适合释放内存和求树高；三者仅visit位置不同，共用同一递归框架。

前序遍历（根→左→右）必须先访问再递归

前序遍历的核心是「访问当前节点 → 递归左子树 → 递归右子树」，顺序不能颠倒。一旦把 visit(node) 放到递归调用之后，就变成中序或后序了。

常见错误：在空指针检查前就调用 node->val，导致段错误。

务必先判 if (node == nullptr)，再访问成员
递归调用时传入 node->left 和 node->right，不是 node 自身
若需返回遍历结果（如 vector），建议用引用参数传入容器，避免频繁拷贝

void preorder(TreeNode* node, vector& res) {
    if (node == nullptr) return;
    res.push_back(node->val);      // 先访问
    preorder(node->left, res);     // 再递归左
    preorder(node->right, res);   // 最后递归右
}

中序遍历（左→根→右）天然适配 BST 排序输出

中序遍历对二叉搜索树（BST）有特殊意义：结果一定是升序排列。但这个性质只在树满足 BST 性质时成立，和遍历算法本身无关。

容易被忽略的点：中序不是“从中间开始”，而是严格按左-根-右顺序深入。有人误以为要先找最左节点再往上回溯——其实递归自然完成该过程。

递归左子树必须放在访问操作之前
若用于验证 BST，可在访问时检查 prev_val val，发现违反即标记非法
非递归中序需要手动模拟栈，但递归版本简洁可靠，无栈溢出风险（除非树深度极大）

void inorder(TreeNode* node, vector& res) {
    if (node == nullptr) return;
    inorder(node->left, res);     // 先递归左
    res.push_back(node->val);      // 再访问
    inorder(node->right, res);   // 最后递归右
}

后序遍历（左→右→根）适合释放内存和求高度

后序是唯一一种左右子树都处理完才接触当前节点的遍历方式，因此天然适用于：释放以该节点为根的整棵子树、计算树高、判断平衡性等场景。

典型误用：把释放逻辑写成 delete node; preorder(node->left) —— 这会导致访问已释放内存，UB（未定义行为）。

必须先递归左右，最后才 delete node
求树高时，返回 1 + max(left_height, right_height)，空节点高为 0
若函数需返回值（如高度），就不能用 void，要改用 int 并注意空节点返回值

int getHeight(TreeNode* node) {
    if (node == nullptr) return 0;
    int leftH = getHeight(node->left);
    int rightH = getHeight(node->right);
    return 1 + max(leftH, rightH);  // 后序：子树高度已知，才能算当前
}