在C++中使用函数作为参数来遍历二叉树

在C++中，使用函数作为参数来遍历二叉树是一种常见的设计模式，通常称为回调函数（Callback Function）。这种模式允许你在遍历过程中对每个节点执行自定义的操作。下面我将详细介绍这个概念及其应用。

基础概念

回调函数：回调函数是一个通过函数指针或函数对象传递给另一个函数的函数。当某个事件发生时，被调用的函数会调用回调函数。

二叉树遍历：二叉树的遍历主要有三种方式：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）和后序遍历（Post-order Traversal）。

类型与应用场景

前序遍历（Pre-order Traversal）

访问顺序：根节点 -> 左子树 -> 右子树应用场景：复制树、序列化树等。

中序遍历（In-order Traversal）

访问顺序：左子树 -> 根节点 -> 右子树应用场景：二叉搜索树的排序输出。

后序遍历（Post-order Traversal）

访问顺序：左子树 -> 右子树 -> 根节点应用场景：删除树、计算表达式树等。

示例代码

下面是一个使用回调函数遍历二叉树的示例代码：

#include <iostream>

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

// 回调函数类型定义
typedef void (*CallbackFunc)(TreeNode*);

// 前序遍历
void preOrderTraversal(TreeNode* root, CallbackFunc callback) {
    if (root == nullptr) return;
    callback(root); // 访问根节点
    preOrderTraversal(root->left, callback); // 遍历左子树
    preOrderTraversal(root->right, callback); // 遍历右子树
}

// 中序遍历
void inOrderTraversal(TreeNode* root, CallbackFunc callback) {
    if (root == nullptr) return;
    inOrderTraversal(root->left, callback); // 遍历左子树
    callback(root); // 访问根节点
    inOrderTraversal(root->right, callback); // 遍历右子树
}

// 后序遍历
void postOrderTraversal(TreeNode* root, CallbackFunc callback) {
    if (root == nullptr) return;
    postOrderTraversal(root->left, callback); // 遍历左子树
    postOrderTraversal(root->right, callback); // 遍历右子树
    callback(root); // 访问根节点
}

// 示例回调函数：打印节点值
void printNode(TreeNode* node) {
    std::cout << node->val << " ";
}

int main() {
    // 构建一个简单的二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "Pre-order traversal: ";
    preOrderTraversal(root, printNode);
    std::cout << std::endl;

    std::cout << "In-order traversal: ";
    inOrderTraversal(root, printNode);
    std::cout << std::endl;

    std::cout << "Post-order traversal: ";
    postOrderTraversal(root, printNode);
    std::cout << std::endl;

    // 清理内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}