C++二叉树应用实例详解（从零开始掌握C++二叉树的构建与遍历）

C++中如何定义二叉树节点？

在C++中，我们通常使用结构体（struct）或类（class）来定义二叉树的节点。每个节点包含数据域和两个指针，分别指向左子节点和右子节点。

// 定义二叉树节点结构struct TreeNode {    int val;                // 节点存储的数据    TreeNode* left;         // 指向左子节点的指针    TreeNode* right;        // 指向右子节点的指针    // 构造函数，用于初始化节点    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};

二叉树的三种基本遍历方式

遍历是访问二叉树所有节点的过程。常见的三种遍历方式包括：前序遍历、中序遍历和后序遍历。这些是学习二叉树遍历算法的基础。

1. 前序遍历（根 → 左 → 右）

void preorderTraversal(TreeNode* root) {    if (root == nullptr) return;    cout << root->val << " ";          // 访问根节点    preorderTraversal(root->left);     // 遍历左子树    preorderTraversal(root->right);    // 遍历右子树}

2. 中序遍历（左 → 根 → 右）

void inorderTraversal(TreeNode* root) {    if (root == nullptr) return;    inorderTraversal(root->left);      // 遍历左子树    cout << root->val << " ";          // 访问根节点    inorderTraversal(root->right);     // 遍历右子树}

3. 后序遍历（左 → 右 → 根）

void postorderTraversal(TreeNode* root) {    if (root == nullptr) return;    postorderTraversal(root->left);    // 遍历左子树    postorderTraversal(root->right);   // 遍历右子树    cout << root->val << " ";          // 访问根节点}

完整应用实例：构建并遍历二叉树

下面是一个完整的C++程序，演示如何手动构建一棵简单的二叉树，并执行三种遍历操作。这个例子非常适合C++编程入门学习者。

#include <iostream>using namespace std;// 定义二叉树节点struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};// 前序遍历void preorder(TreeNode* root) {    if (!root) return;    cout << root->val << " ";    preorder(root->left);    preorder(root->right);}// 中序遍历void inorder(TreeNode* root) {    if (!root) return;    inorder(root->left);    cout << root->val << " ";    inorder(root->right);}// 后序遍历void postorder(TreeNode* root) {    if (!root) return;    postorder(root->left);    postorder(root->right);    cout << root->val << " ";}int main() {    // 手动构建如下二叉树：    //       1    //      / \    //     2   3    //    / \    //   4   5    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);    cout << "前序遍历: ";    preorder(root);    cout << endl;    cout << "中序遍历: ";    inorder(root);    cout << endl;    cout << "后序遍历: ";    postorder(root);    cout << endl;    return 0;}

运行上述程序，你将看到如下输出：

前序遍历: 1 2 4 5 3 中序遍历: 4 2 5 1 3 后序遍历: 4 5 2 3 1

总结

通过本教程，你已经掌握了C++二叉树应用的基本知识，包括节点定义、三种遍历方式以及一个完整的构建与遍历示例。理解这些内容是深入学习更高级C++数据结构教程（如二叉搜索树、AVL树、红黑树等）的重要基础。

建议你动手敲一遍代码，修改节点值或结构，观察输出变化，从而加深对二叉树遍历算法的理解。如果你是C++编程入门的新手，这种实践将极大提升你的编程能力！

提示：在实际项目中，记得释放动态分配的内存以避免内存泄漏（可使用智能指针或手动 delete）。