c++中如何实现前序遍历_c++二叉树前序遍历方法

前序遍历按根→左→右顺序访问节点，C++中可用递归或非递归实现。1. 定义TreeNode结构；2. 递归法：先访问根节点，再依次递归左右子树；3. 非递归法：用栈模拟调用过程，先压右后压左；4. 测试示例构建二叉树并输出结果为1 2 4 3。

二叉树的前序遍历是指按照“根节点 → 左子树 → 右子树”的顺序访问所有节点。在C++中，可以通过递归和非递归两种方式实现前序遍历。

1. 二叉树节点定义

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

2. 递归实现前序遍历

void preorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) return;
    std::cout val     preorderTraversalRecursive(root->left); // 遍历左子树
    preorderTraversalRecursive(root->right); // 遍历右子树
}

3. 非递归实现（使用栈）

非递归方式使用显式栈来模拟系统调用栈的行为。核心思路是：将节点入栈，每次弹出并处理，然后先压入右子节点，再压入左子节点（因为栈是后进先出）。

UP简历

基于AI技术的免费在线简历制作工具

128

查看详情

立即学习“C++免费学习笔记（深入）”；

#include <stack>
void preorderTraversalIterative(TreeNode* root) {
    if (!root) return;
    std::stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        std::cout val
        // 先压入右子树，再压入左子树
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
}

4. 完整示例与测试

// 构建树：
//      1
//    /   \
//  2     3
// /
//4
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);

std::cout preorderTraversalRecursive(root); // 输出: 1 2 4 3
std::cout
std::cout preorderTraversalIterative(root); // 输出: 1 2 4 3

基本上就这些。递归写法简单易懂，适合理解逻辑；非递归更贴近底层，避免深度递归导致栈溢出。根据实际需求选择即可。

以上就是c++++中如何实现前序遍历_c++二叉树前序遍历方法的详细内容，更多请关注php中文网其它相关文章！