C++树数据结构详解（从零开始掌握二叉树的构建与遍历）

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

首先，我们需要定义一个结构体或类来表示树的节点：

struct TreeNode {    int data;               // 节点存储的数据    TreeNode* left;         // 指向左子节点的指针    TreeNode* right;        // 指向右子节点的指针    // 构造函数    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}};

创建一棵简单的二叉树

下面的代码演示了如何手动构建一棵包含几个节点的小型二叉树：

#include <iostream>using namespace std;struct TreeNode {    int data;    TreeNode* left;    TreeNode* right;    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}};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);    cout << "二叉树创建成功！" << endl;    return 0;}

树的三种基本遍历方式

遍历是访问树中所有节点的过程。常见的三种遍历方式是：前序遍历、中序遍历和后序遍历。它们的区别在于访问根节点的顺序不同。

• 前序遍历（Pre-order）：根 → 左 → 右
• 中序遍历（In-order）：左 → 根 → 右
• 后序遍历（Post-order）：左 → 右 → 根

下面是这三种遍历方式的C++实现：

// 前序遍历void preorder(TreeNode* node) {    if (node == nullptr) return;    cout << node->data << " ";   // 访问根    preorder(node->left);        // 遍历左子树    preorder(node->right);       // 遍历右子树}// 中序遍历void inorder(TreeNode* node) {    if (node == nullptr) return;    inorder(node->left);         // 遍历左子树    cout << node->data << " ";   // 访问根    inorder(node->right);        // 遍历右子树}// 后序遍历void postorder(TreeNode* node) {    if (node == nullptr) return;    postorder(node->left);       // 遍历左子树    postorder(node->right);      // 遍历右子树    cout << node->data << " ";   // 访问根}

完整示例：构建并遍历二叉树

#include <iostream>using namespace std;struct TreeNode {    int data;    TreeNode* left;    TreeNode* right;    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}};void preorder(TreeNode* node) {    if (!node) return;    cout << node->data << " ";    preorder(node->left);    preorder(node->right);}void inorder(TreeNode* node) {    if (!node) return;    inorder(node->left);    cout << node->data << " ";    inorder(node->right);}void postorder(TreeNode* node) {    if (!node) return;    postorder(node->left);    postorder(node->right);    cout << node->data << " ";}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);    cout << "前序遍历: ";    preorder(root);    cout << endl;    cout << "中序遍历: ";    inorder(root);    cout << endl;    cout << "后序遍历: ";    postorder(root);    cout << endl;    return 0;}

总结

通过本教程，你已经掌握了C++树数据结构的基本概念、如何定义节点、构建二叉树以及实现三种基本的遍历方法。这些知识是深入学习更复杂树结构（如二叉搜索树、AVL树、红黑树等）的基础。

记住，理解树结构入门的关键在于多画图、多写代码。建议你自己动手实现一遍上述代码，并尝试修改节点值或添加新节点，观察遍历结果的变化。

希望这篇关于C++树遍历和二叉树实现的教程对你有所帮助！继续加油，你离成为C++高手又近了一步！