用C++实现二叉链表的前序遍历

在C++中，我们可以使用递归或迭代的方式来实现二叉链表的前序遍历（Preorder Traversal）。前序遍历的顺序是根节点 -> 左子树 -> 右子树。以下是两种方法的示例：

**方法一：递归实现**

struct Node {
    int data;
    Node* left;
    Node* right;
};

void preorder(Node* root) {
    if (root != nullptr) {
        // 输出当前节点的数据
        cout << root->data << " ";
        // 递归遍历左子树
        preorder(root->left);
        // 递归遍历右子树
        preorder(root->right);
    }
}

**方法二：迭代实现（使用栈）**

void preorder(Node* root) {
    stack<Node*> s;
    Node* current = root;

    while (current != nullptr || !s.empty()) {
        // 当前节点不为空或栈不空时
        while (current != nullptr) {
            // 将当前节点压入栈
            s.push(current);
            current = current->left;
        }

        // 弹出栈顶节点并访问
        current = s.top();
        s.pop();
        cout << current->data << " ";

        // 更新当前节点为右子节点
        current = current->right;
    }
}

在上述代码中，记得在使用前先创建一个二叉链表结构，并设置好节点之间的链接。