二叉树的遍历（前序、中序、后序、层序）

        A
      /   \
     B     C
    / \   / \
   D   E F   G

// C++ 前序迭代版本
#include <stack>
void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->data << " ";          // 访问当前节点
        // 先压右孩子，再压左孩子（这样左孩子先出栈）
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
}

# Python 前序迭代版本
def preorder_iterative(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.data, end=' ')
        # 先压右，再压左，保证左先出
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

void inorderIterative(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr != nullptr || !st.empty()) {
        // 一直向左，把所有左节点压栈
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        // 出栈，访问节点
        curr = st.top();
        st.pop();
        cout << curr->data << " ";
        // 转向右子树
        curr = curr->right;
    }
}

def inorder_iterative(root):
    stack = []
    curr = root
    while curr or stack:
        # 一路向左压栈
        while curr:
            stack.append(curr)
            curr = curr.left
        # 出栈访问
        curr = stack.pop()
        print(curr.data, end=' ')
        # 转向右
        curr = curr.right

void postorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st1, st2;
    st1.push(root);
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st1.pop();
        st2.push(node);                // 把访问顺序暂存在 st2
        if (node->left) st1.push(node->left);
        if (node->right) st1.push(node->right);
    }
    // 从 st2 依次出栈得到后序序列
    while (!st2.empty()) {
        cout << st2.top()->data << " ";
        st2.pop();
    }
}

def postorder_iterative(root):
    if root is None:
        return
    st1 = [root]
    st2 = []
    while st1:
        node = st1.pop()
        st2.append(node)
        if node.left:
            st1.append(node.left)
        if node.right:
            st1.append(node.right)
    while st2:
        node = st2.pop()
        print(node.data, end=' ')

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// 二叉树节点结构体
struct TreeNode {
    char data;              // 节点数据（用字符方便显示）
    TreeNode *left;         // 左孩子指针
    TreeNode *right;        // 右孩子指针
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// ---------- 递归遍历 ----------
void preorderRecursive(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorderRecursive(root->left);
    preorderRecursive(root->right);
}

void inorderRecursive(TreeNode* root) {
    if (root == nullptr) return;
    inorderRecursive(root->left);
    cout << root->data << " ";
    inorderRecursive(root->right);
}

void postorderRecursive(TreeNode* root) {
    if (root == nullptr) return;
    postorderRecursive(root->left);
    postorderRecursive(root->right);
    cout << root->data << " ";
}

// ---------- 迭代遍历 ----------
void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->data << " ";
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
}

void inorderIterative(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top();
        st.pop();
        cout << curr->data << " ";
        curr = curr->right;
    }
}

void postorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> st1, st2;
    st1.push(root);
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st1.pop();
        st2.push(node);
        if (node->left) st1.push(node->left);
        if (node->right) st1.push(node->right);
    }
    while (!st2.empty()) {
        cout << st2.top()->data << " ";
        st2.pop();
    }
}

// ---------- 层序遍历（队列）----------
void levelorder(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        cout << curr->data << " ";
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}

int main() {
    // 构建标准二叉树
    TreeNode* root = new TreeNode('A');
    root->left = new TreeNode('B');
    root->right = new TreeNode('C');
    root->left->left = new TreeNode('D');
    root->left->right = new TreeNode('E');
    root->right->left = new TreeNode('F');
    root->right->right = new TreeNode('G');

    cout << "=== 递归版本 ===" << endl;
    cout << "前序: "; preorderRecursive(root); cout << endl;
    cout << "中序: "; inorderRecursive(root); cout << endl;
    cout << "后序: "; postorderRecursive(root); cout << endl;

    cout << "=== 迭代版本 ===" << endl;
    cout << "前序: "; preorderIterative(root); cout << endl;
    cout << "中序: "; inorderIterative(root); cout << endl;
    cout << "后序: "; postorderIterative(root); cout << endl;

    cout << "=== 层序 ===" << endl;
    cout << "层序: "; levelorder(root); cout << endl;

    // 释放内存（这里省略，实际可以使用递归 delete）
    return 0;
}

=== 递归版本 ===
前序: A B D E C F G 
中序: D B E A F C G 
后序: D E B F G C A 
=== 迭代版本 ===
前序: A B D E C F G 
中序: D B E A F C G 
后序: D E B F G C A 
=== 层序 ===
层序: A B C D E F G