下面为你详细介绍二叉树的四种遍历方式（前序、中序、后序、层序）的实现方法，使用C++语言进行演示。

二叉树的遍历是指按某种特定顺序访问树中的所有节点，使得每个节点被访问一次且仅被访问一次。

二叉树节点定义

首先，我们需要定义二叉树节点的结构：

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

1. 前序遍历 (Pre-order Traversal)

前序遍历的顺序是：根节点 -> 左子树 -> 右子树

递归实现：

void preorderTraversalRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    result.push_back(root->val);          // 访问根节点
    preorderTraversalRecursive(root->left, result);  // 遍历左子树
    preorderTraversalRecursive(root->right, result); // 遍历右子树
}

迭代实现：

vector<int> preorderTraversalIterative(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
        
        // 注意：栈是先进后出，所以先压右子树，再压左子树
        if (node->right != nullptr) {
            st.push(node->right);
        }
        if (node->left != nullptr) {
            st.push(node->left);
        }
    }
    return result;
}

2. 中序遍历 (In-order Traversal)

中序遍历的顺序是：左子树 -> 根节点 -> 右子树

递归实现：

void inorderTraversalRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    inorderTraversalRecursive(root->left, result);   // 遍历左子树
    result.push_back(root->val);          // 访问根节点
    inorderTraversalRecursive(root->right, result);  // 遍历右子树
}

迭代实现：

vector<int> inorderTraversalIterative(TreeNode* root) {
    vector<int> result;
    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();
        result.push_back(curr->val);
        
        // 转向右子树
        curr = curr->right;
    }
    return result;
}

3. 后序遍历 (Post-order Traversal)

后序遍历的顺序是：左子树 -> 右子树 -> 根节点

递归实现：

void postorderTraversalRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorderTraversalRecursive(root->left, result);  // 遍历左子树
    postorderTraversalRecursive(root->right, result); // 遍历右子树
    result.push_back(root->val);          // 访问根节点
}

迭代实现：

vector<int> postorderTraversalIterative(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    TreeNode* prev = nullptr;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* curr = st.top();
        
        // 如果当前节点是叶子节点，或者前一个访问的节点是它的子节点
        if ((curr->left == nullptr && curr->right == nullptr) ||
            (prev != nullptr && (prev == curr->left || prev == curr->right))) {
            result.push_back(curr->val);
            st.pop();
            prev = curr;
        } else {
            // 先压右子树，再压左子树
            if (curr->right != nullptr) {
                st.push(curr->right);
            }
            if (curr->left != nullptr) {
                st.push(curr->left);
            }
        }
    }
    return result;
}

4. 层序遍历 (Level-order Traversal)

层序遍历也称为广度优先遍历，按层次从上到下、从左到右访问节点

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel;
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        result.push_back(currentLevel);
    }
    return result;
}

完整示例代码

下面是一个完整的示例，包含了二叉树的构建和四种遍历方法的演示：

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 前序遍历 - 递归
void preorderTraversalRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    result.push_back(root->val);
    preorderTraversalRecursive(root->left, result);
    preorderTraversalRecursive(root->right, result);
}

// 前序遍历 - 迭代
vector<int> preorderTraversalIterative(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
        
        if (node->right != nullptr) {
            st.push(node->right);
        }
        if (node->left != nullptr) {
            st.push(node->left);
        }
    }
    return result;
}

// 中序遍历 - 递归
void inorderTraversalRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    inorderTraversalRecursive(root->left, result);
    result.push_back(root->val);
    inorderTraversalRecursive(root->right, result);
}

// 中序遍历 - 迭代
vector<int> inorderTraversalIterative(TreeNode* root) {
    vector<int> result;
    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();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}

// 后序遍历 - 递归
void postorderTraversalRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorderTraversalRecursive(root->left, result);
    postorderTraversalRecursive(root->right, result);
    result.push_back(root->val);
}

// 后序遍历 - 迭代
vector<int> postorderTraversalIterative(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    TreeNode* prev = nullptr;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* curr = st.top();
        
        if ((curr->left == nullptr && curr->right == nullptr) ||
            (prev != nullptr && (prev == curr->left || prev == curr->right))) {
            result.push_back(curr->val);
            st.pop();
            prev = curr;
        } else {
            if (curr->right != nullptr) {
                st.push(curr->right);
            }
            if (curr->left != nullptr) {
                st.push(curr->left);
            }
        }
    }
    return result;
}

// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel;
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        result.push_back(currentLevel);
    }
    return result;
}

// 辅助函数：打印向量内容
void printVector(const vector<int>& v, const string& title) {
    cout << title << ": ";
    for (int num : v) {
        cout << num << " ";
    }
    cout << endl;
}

// 辅助函数：打印层序遍历结果
void printLevelOrder(const vector<vector<int>>& v) {
    cout << "层序遍历: " << endl;
    for (const auto& level : v) {
        for (int num : level) {
            cout << num << " ";
        }
        cout << endl;
    }
}

// 构建示例二叉树
TreeNode* buildExampleTree() {
    // 构建如下二叉树:
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(5);
    TreeNode* node2 = new TreeNode(2, node4, node5);
    
    TreeNode* node6 = new TreeNode(6);
    TreeNode* node3 = new TreeNode(3, nullptr, node6);
    
    TreeNode* root = new TreeNode(1, node2, node3);
    
    return root;
}

// 释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    TreeNode* root = buildExampleTree();
    
    // 前序遍历
    vector<int> preorderRecursive;
    preorderTraversalRecursive(root, preorderRecursive);
    printVector(preorderRecursive, "前序遍历(递归)");
    
    vector<int> preorderIterative = preorderTraversalIterative(root);
    printVector(preorderIterative, "前序遍历(迭代)");
    
    // 中序遍历
    vector<int> inorderRecursive;
    inorderTraversalRecursive(root, inorderRecursive);
    printVector(inorderRecursive, "中序遍历(递归)");
    
    vector<int> inorderIterative = inorderTraversalIterative(root);
    printVector(inorderIterative, "中序遍历(迭代)");
    
    // 后序遍历
    vector<int> postorderRecursive;
    postorderTraversalRecursive(root, postorderRecursive);
    printVector(postorderRecursive, "后序遍历(递归)");
    
    vector<int> postorderIterative = postorderTraversalIterative(root);
    printVector(postorderIterative, "后序遍历(迭代)");
    
    // 层序遍历
    vector<vector<int>> level = levelOrder(root);
    printLevelOrder(level);
    
    // 释放内存
    deleteTree(root);
    
    return 0;
}

代码说明

上述代码实现了二叉树的四种基本遍历方式，每种方式都有其特点：

1. 前序遍历：先访问根节点，再递归遍历左子树，最后递归遍历右子树。对于示例树，遍历结果为：1 2 4 5 3 6

2. 中序遍历：先递归遍历左子树，再访问根节点，最后递归遍历右子树。对于示例树，遍历结果为：4 2 5 1 3 6

3. 后序遍历：先递归遍历左子树，再递归遍历右子树，最后访问根节点。对于示例树，遍历结果为：4 5 2 6 3 1

4. 层序遍历：按层次从上到下、从左到右访问节点。对于示例树，遍历结果为：

   1
   2 3
   4 5 6
   

递归实现简洁直观，符合遍历的定义，但对于深度很大的树可能会导致栈溢出。迭代实现使用栈（前序、中序、后序）或队列（层序）来模拟递归过程，避免了栈溢出问题，但代码相对复杂一些。

你可以根据实际需求选择合适的遍历方式和实现方法。